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