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