[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] 1 é primo?

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

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 é <nicolau@mat.puc-rio.br>
=========================================================================