On Tue, Aug 27, 2002 at 08:07:24PM +0000, Paulo Santa Rita wrote: > Agora, neste exato momento, tem um "Montao de Gente" me enviando e-mail's e > me perguntando como e o Algoritmo Genial que um grupo de estudantes indianos > descobriram e que pesquisa maravilhosamente os numeros primos ! Parece que e > uma revolucao ! Alguem sabe algo a respeito ? Foi disponibilizado algum > paper ? Parece que a descoberta foi divulgada ontem.
O paper já foi disponibilizado há algumas semanas. O título é 'PRIMES is in P', os autores são Manindra Agrawal, Neeral Kayal e Nitin Saxena. Ele pode ser obtido na home page do principal autor: http://www.cse.iitk.ac.in/users/manindra/index.html O paper tem 9 páginas e é bastante elementar. O algoritmo, escrito em pseudocódigo, tem apenas 13 linhas então lá vai: Input: integer n > 1 1. if ( n is of the form a^b, b > 1 ) output COMPOSITE; 2. r = 2; 3. while ( r < n ) { 4. if ( gcd(n,r) != 1 ) output COMPOSITE; 5. if ( r is prime ) 6. let q be the largest prime factor of r-1; 7. if ( q >= 4sqrt(r)log n ) and ( n^(r-1/q) != 1 (mod r)) 8. break; 9. r := r + 1; 10. } 11. for a = 1 to 2sqrt(r)log n 12. if ( (x-a)^n != (x^n - a) (mod x^r - 1,n) ) output COMPOSITE; 13. output PRIME; gcd significa mdc, sqrt significa raiz quadrada e pode ser interpretado como a parte inteira da raiz (assim todas as contas são em inteiros). O coração deste algoritmo (linhas 2 até 10) é, dado n, encontrar um primo r ~= (log n)^6 tal que r-1 tem um fator primo q >= 4sqrt(r)log n e com q um divisor da ordem de n módulo r (o Lemma 4.2 do paper demonstra a existência de um tal r). Uma vez encontrado este primo basta fazer as verificações nas linhas 11 e 12. O 'x' que aparece na linha 12 é uma variável mesmo, no sentido algébrico da palavra (e não o nome de um inteiro). As congruências que se deve verificar são portanto congruências entre polinômios; se n é primo elas valem sempre (Fermat) mas se n é composto elas não podem todas valer (seção 2 do paper). []s, N. ========================================================================= 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 é <[EMAIL PROTECTED]> =========================================================================
