[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>
=========================================================================