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