[obm-l] Indianos solucionam problema matem�tico milenar

[Alexandre Botelho MAGALH�ES de Oliveira <abmo@xxxxxxxxxxxxx>]

Eu li a pouco na net esse artigo a respeito de testes de primalidade.

Indianos solucionam problema matem�tico milenar

Nicola Dixon
Da New Scientist

Tr�s cientistas da computa��o chocaram a comunidade de matem�ticos ao
encontrar a solu��o para um problema que dura s�culos: como dizer se um
n�mero � primo. A prova � impressionante em sua simplicidade, e fez os
matem�ticos se perguntarem o que mais eles podem ter deixado passar.

Os n�meros primos, que s�o divis�veis apenas por si mesmos e 1, s�o blocos
de constru��o fundamentais da matem�tica e fascinam estudiosos desde os
tempos antigos. Em 240 a.C., o matem�tico grego Erat�stenes apresentou a
primeira forma � prova de falhas para saber se um n�mero era primo. Mas o
tempo que o m�todo exige cresce exponencialmente com o tamanho do n�mero, de
forma que para n�meros muito longos � necess�rio mais tempo que a idade do
Universo para solucionar o problema. Desde ent�o os matem�ticos t�m tentado
encontrar um algoritmo de tempo polinomial, capaz de fornecer uma resposta
em uma quantidade de tempo razo�vel.

A busca se intensificou ao longo das �ltimas poucas d�cadas, desde que os
n�meros primos se tornaram vitais para a criptografia. O sistema de
encripta��o usado para proteger transa��es pela Internet conta com o fato de
ser extremamente dif�cil descobrir os fatores de grandes n�meros primos. Os
algoritmos usados atualmente para ajudar a encontrar estes fatores s�o
r�pidos, mas eles apenas fornecem a probabilidade de um n�mero ser primo ou
n�o. Apesar da probabilidade ser muito alta, estes algoritmos n�o
representam uma prova.

Agora Manindra Agrawal e seus alunos ainda n�o formados, Neeraj Kayal e
Nitin Saxtena, foram bem-sucedidos onde as melhores mentes da matem�tica
fracassaram. O trio, do Departamento de Ci�ncia da Computa��o e Engenharia
do Instituto Indiano de Tecnologia em Kanpur, desenvolveram um algoritmo que
d� uma resposta definitiva para o problema em tempo razo�vel.

O sucesso deles est� na nova abordagem que adotaram para o problema. Em vez
de fazer a grande pergunta, "este � um n�mero primo?", eles geraram uma
s�rie de perguntas menores ou "igualdades" do n�mero que est� sendo testado.
"Se as igualdades se sustentarem, o n�mero � primo, se alguma delas n�o se
sustentar, ent�o o n�mero n�o � primo", explica Agrawal.

At� o momento milhares de matem�ticos verificaram as provas postadas
atualmente no site do instituto na Internet. "Todos os que me mandaram
e-mails apreciaram o algoritmo e disseram que ele est� correto", diz Agrawal
para a New Scientist.

Especialistas suspeitavam que um algoritmo de tempo polinomial fosse
poss�vel. Mas n�o previam a simplicidade da solu��o em 13 linhas que Agrawal
e seus colegas apresentaram. "� uma bela solu��o e estou muito feliz por
eles, mas estou um pouco embara�ado por n�o ter visto isto eu mesmo", diz o
especialista em n�meros primos Carl Pomerance, dos Laborat�rios Bell da
Lucent, em Nova Jersey. "A solu��o deles � simples. Isto n�o quer dizer que
seja trivial; o que eles fizeram foi muito inteligente", acrescenta.

O avan�o te�rico � significativo por si s�, mas Ian Stewart da Universidade
de Warwick disse que o m�todo tamb�m dever� ajudar os matem�ticos a
solucionarem outros problemas, nos quais chegaram a um beco sem sa�da usando
outras t�cnicas.

A seguran�a na Internet ainda n�o est� sob amea�a. "A solu��o provavelmente
ter� um impacto muito pequeno, pois ela n�o oferece nenhuma vantagem real
sobre os algoritmos probabil�sticos j� usados no setor", afirma Ben Hadley
da nCipher, uma empresa de seguran�a por criptografia baseada em Cambridge.
Mas Pomerance acredita que a exist�ncia da prova deixar� os criptologistas
preocupados. "Se h� um teste simples para saber se um n�mero � primo, tamb�m
pode haver uma forma simples de determinar os fatores primos que estamos
atualmente investigando", disse ele.

Esta � a verdadeira import�ncia do trabalho do trio. O fato de estudantes
n�o formados, trabalhando em seu projeto de fim de ano, poderem solucionar
um enigma t�o antigo levanta a possibilidade de que outras solu��es simples
para grandes problemas matem�ticos podem ter sido ignoradas. "� um lembrete
de como podemos ignorar as coisas simples", disse Pomerance.


Tradu��o: George El Khouri Andolfato


Comente esta not�cia: UOL Inova��o - Computa��o


-----Mensagem Original-----
De: "Fernando Henrique Ferraz P. da Rosa" <mentus@gmx.de>
Para: <obm-l@mat.puc-rio.br>
Enviada em: ter�a-feira, 27 de agosto de 2002 19:38
Assunto: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l]
1 � primo?


Humm. tamb�m queria ler a respeito disso mas n�o achei *NADA* nos arquivos
da lista.. somente uma �nica mensagem...  essa aqui:
[obm-l] Re: [obm-l] Indianos criam f�rmula infal�vel para achar n�mero
primo, ghaeser
url: http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200208/msg00115.html


At 17:56 8/27/2002 -0300, you wrote:

>Voce esta falando do algoritmo para testar a primalidade de um numero??
>
>Se for, eh so olhar os arquivos da lista...
>Ele ja foi bem discutido por aqui.

"... a perfect formulation of a problem is already half
    its solution."
          David Hilbert.
-
[]'s
Fernando Henrique Ferraz Pereira da Rosa
USP, IME, Estat�stica
http://www.linux.ime.usp.br/~feferraz



----------------------------------------------------------------------------
----


>
> ---
> Outgoing mail is certified Virus Free.
> Checked by AVG anti-virus system (http://www.grisoft.com).
> Version: 6.0.384 / Virus Database: 216 - Release Date: 8/21/2002
>

=========================================================================
Instru��es para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista � <nicolau@mat.puc-rio.br>
=========================================================================