NÚMEROS PRIMOS
Indianos resolvem problema milenar
Problemas simples não têm, necessariamente, soluções simples ou rápidas. Uma questão aparentemente banal, abordada já no ensino fundamental, desafia os matemáticos desde a Grécia Antiga: determinar se um número é primo ou não com um algoritmo rápido e matematicamente preciso. A solução apareceu em agosto de 2002, quando o matemático indiano Manindra Agarwal, com dois de seus alunos de pós-graduação, Nitin Saxena e Neeraj Kayal, do Instituto Indiano de Tecnologia em Kanpur, apresentou uma solução até bastante simples. A grande novidade no trabalho dos indianos foi apresentar um algoritmo que é ao mesmo tempo rápido e com precisão absoluta ("determinístico"), sem nenhuma margem para erros.
Algoritmos para determinar se um número é primo existem, pelo menos, desde a Grécia Antiga; porém, tornam-se proibitivamente lentos para números muito grandes. Um algoritmo muito mais rápido foi proposto, em 1980, por Michael O. Rabin, mas ele não mostra, com certeza absoluta, se o número é primo ou não: diz apenas que o tal número tem uma probabilidade alta de ser (ou não) primo. Porém, a probabilidade é tão grande que, na prática, o método funcionava perfeitamente.
O pesquisador Walter Carnielli, diretor do Centro de Lógica, Epistemologia e História da Ciência da Unicamp, avalia: "a margem de erro pode ser a mesma da ocorrência dos seguintes eventos simultaneamente: ganhar na mega-sena, cair um raio no computador e ter um problema de hardware". Assim, o algoritmo de Rabin tornou-se o método mais usado para se testar se um número é primo.
]]> Para Carnielli, o método de Rabin continuará sendo usado nos cálculos práticos, pois é ainda mais rápido que o dos indianos e porque, mesmo fornecendo apenas probabilidades, as margens de erro são muitíssimo pequenas.O algoritmo dos indianos não terá conseqüências imediatas na criptografia. O método mais usado atualmente para criptografar informações usa números primos. Para quebrar um código desses é necessário encontrar os fatores de números primos muito grandes. Não há um método rápido para a determinação desses fatores, e o algoritmo de Agarwal-Saxena-Kayal não permite fazê-lo: ele só diz se um número é primo ou não; caso não seja, não diz nada sobre seus fatores.
Roberto Belisário
]]>