[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] 1 é primo?
On Tue, Aug 27, 2002 at 08:07:24PM +, 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]
=
Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re:[obm-l] 1 é primo?
Eu nao cheguei olhar nos arquivos da lista. Estou mandando os titulos de algumas mensagens que salvei em meu computador. Sei que houveram outras de conteudo similar e que, por causa disso, eu simplesmente apaguei. Se mesmo assim voces nao encontrarem nada eu posso procurar por la ou mandar as mensagems diretamente para voces: A ultima mensagem do Vinicius eh uma das que contem a melhor explicacao e referencias. * [obm-l] Indianos criam fórmula infalível para achar número primo; Igor GomeZZ; 10/08/2002 23:18 * [obm-l] En:[teoremalista] PRIMES is in P; Paulo Jose Rodrigues; 11/08/2002 10:50 * Re: [obm-l] Numeros primos - solução; [EMAIL PROTECTED]; Ultimo domingo 15:15 * [obm-l] RES: [obm-l] Numeros primos - solução; Edilson Ribeiro da Silva; Ultimo domingo 17:13 * Re: [obm-l] RES: [obm-l] Numeros primos ; Rodrigo Malta Schmidt; Ultimo domingo 18:17 * [obm-l] Re: [obm-l] RES: [obm-l] Numeros primos ; iver; Ontem 00:21 * [obm-l] Re: [obm-l] RES: [obm-l] Numeros primos ; Vinicius Jose Fortuna; Ontem 23:42 Abracos, Rodrigo Fernando Henrique Ferraz P. da Rosa wrote: Humm. também queria ler a respeito disso mas não achei *NADA* nos arquivos da lista.. somente uma única mensagem... essa aqui: [obm-l] Re: [obm-l] Indianos criam fórmula infalível para achar número primo, ghaeser url: http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200208/msg00115.html At 17:56 8/27/2002 -0300, you wrote: Voce esta falando do algoritmo para testar a primalidade de um numero?? Se for, eh so olhar os arquivos da lista... Ele ja foi bem discutido por aqui. ... a perfect formulation of a problem is already half its solution. David Hilbert. - []'s Fernando Henrique Ferraz Pereira da Rosa USP, IME, Estatística http://www.linux.ime.usp.br/~feferraz --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.384 / Virus Database: 216 - Release Date: 8/21/2002 = 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] =
