[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]
=
[obm-l] Re: [obm-l] Re: [obm-l] 1 é primo?
É pura conveniência. Assim como 0!=1. Retas coincidentes são paralelas? Para quem está trabalhando com geometria analítica, é melhor considerar que sim. Retas perpendiculares são ortogonais? Qual é a raiz quadrada de 9? Quase todos desta lista dariam duas respostas: +3 e -3. Qual a definição de poliedro? Em f(x) = ax+b, se a=0, f ainda é uma função afim (polinomial do 1o grau)? É uma simples questão de conveniência. - Original Message - From: Eduardo Casagrande Stabel [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Tuesday, August 27, 2002 12:51 PM Subject: [obm-l] Re: [obm-l] 1 é primo? Com a definição desse livro: 1 é primo, sim! Mas o tradicional é considerar: um número natural p é primo se ele é divisível por exatamente dois números naturais. Daí, nessa definição: 1 não é primo, não! Como as definições matemáticas não são obras imutáveis da natureza (somos nós, seres humanos, que fazemos as definições), você pode definir do jeito que você quiser, de acordo com os seus propósitos matemáticos. Por exempo, se eu quiser chamar o dois de um e o um de dois e não cometer deslizes e sempre manter essa definição clara, eu estou fazendo a mais pura e correta matemática. Agora, você provavelmente nunca vai ver outra pessoa chamando dois de um e um de dois. O mais comum, sem dúvida, é 1 não é primo. Eduardo. From: Marcelo Roseira 1 é primo? Vi num livro uma definição que dizia que um número p é primo se é divisível por (+ou-p) e (+ou-)1. Logo 1 é primo. Correto? Grato. = 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] = = 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] =
[obm-l] Re: [obm-l] Re: [obm-l] 1 é primo?
From: Rodrigo Malta Schmidt [EMAIL PROTECTED] A consideracao de 1 como primo nao quebra o teorema da fatoracao unica?? Quebraria. Mas poderia ser corrigido alterando primo, por primo diferente de um. A questão de definir 1 como não sendo primo é conveniência. Muitos enunciados ficam mais limpos. Eduardo. Se 1 fosse primo, 10 teria infinitas fatoracoes: 1*2*5, 1^2*2*5, 1^3*2*5, Ab, Rodrigo Eduardo Casagrande Stabel wrote: Com a definição desse livro: 1 é primo, sim! Mas o tradicional é considerar: um número natural p é primo se ele é divisível por exatamente dois números naturais. Daí, nessa definição: 1 não é primo, não! Como as definições matemáticas não são obras imutáveis da natureza (somos nós, seres humanos, que fazemos as definições), você pode definir do jeito que você quiser, de acordo com os seus propósitos matemáticos. Por exempo, se eu quiser chamar o dois de um e o um de dois e não cometer deslizes e sempre manter essa definição clara, eu estou fazendo a mais pura e correta matemática. Agora, você provavelmente nunca vai ver outra pessoa chamando dois de um e um de dois. O mais comum, sem dúvida, é 1 não é primo. Eduardo. From: Marcelo Roseira 1 é primo? Vi num livro uma definição que dizia que um número p é primo se é divisível por (+ou-p) e (+ou-)1. Logo 1 é primo. Correto? Grato. = 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] = = 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] = = 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] =
[obm-l] Re: [obm-l] Re: [obm-l] 1 é primo?
Ola Leonardo e demais colegas desta lista, Esta discussao e deveras interessante ... O que caracteriza um numero primo e que ele nao admite fator primo alem dele mesmo, isto e, ele e divisivel somente por si mesmo e pela unidade. Agora, supondo que 1 e primo. Entao, todo numero p, primo, e divisivel por ele mesmo e por outro primo, no caso o 1 que estamos supondo que e primo : segue que, por definicao, tem um fator primo diferente de si mesmo, logo, nao e primo ... A sequencia a, a, a, ... e uma PA ? Alguns dizem que sim, outros, que nao. Isso e importante ? Depende ... Quando introduzimos o conceito de ordem, de forma a podermos tratar outros tipos de sequencias, passamos a diferenciar entre as PA's constantes ( Ex a,a,a,...) e as outras (Ex 1,3,5, ...). Dizemos que as primeiras sao de ordem zero e, as segundas, de ordem 1. Por que fazemos isso ? Nao e essa atribuicao arbitraria ? Nao. Nao neste contexto. Na teoria das sequencias aritmeticas existe um teorema que afirma que se a1, a2, a3, ... e uma sequencia de ordem P entao (a1)^q, (a2)^q,(a3)^q, (a4)^q, ... e uma sequencia de ordem P*Q ( P e Q naturais ). Esse teorema e falso se (a,a,a,...) for uma PA de ordem 1 e verdadeiro se nos atribuirmos a esta PA a ordem zero. Assim, para que possamos voar mais alto e abordar coisas que outrora nao abordavamos, precisamos introduzir inteligentemente modificacoes naquilo que lidamos cotidianamente sem maiores implicacoes. No caso das PA's, se nos limitarmos as de ordem 1 que sao ensinadas no NIvel medio, a distincao que fizemos e irrelevante e desnecessaria. O mesmo se diga dos numeros complexos. Se nos os retirarmos, muitos teorema que apresentam bela simetria ( Ex Teorema fundamental da algebra) ficaram tortos e de enunciado muito complexo. Parece que esse SENTIMENTO DAS NECESSIDADES INTERNAS DE COERENCIA E BELEZA NA MATEMATICA tem levado a belos e importantes desenvolvimentos ... Talvez seja esta a situacao inusitada do 1. POR ENQUANTO, dizer que ele e primo ou nao nao leva a nenhuma complicacao forte e a sua verdadeira natureza e condicao, a funcao que ele deve desempenhar, quando ousarmos e mais, a ponto desta situacao dubia do 1 se tornar insustentavel ... Isso tambem e uma prova indireta de nossa imensa ignorancia acerca da verdadeira natureza dos numeros primos ... Nem falar direito sobre eles nos sabemos ... Outro fato digno de nota e com respeito aos numeros perfeitos. Um numero e perfeito se ele e igual a soma de seu divisores proprios. 6 e perfeito, pois 6=1+2+3. O que ha de especial em todos os numeros perfeitos ? Isso : a razao entre eles e a soma de seus divisores proprios e sempre 1 ( Ex : 6/(1+2+3)=1 ). Se, todavia, incluirmos todos os divisores, incluindo o proprio numero, podemos definir os numeros perfeitos assim: Um numero e perfeito se a razao entre ele e seus divisores e 1/2. Por que vamos privilegiar esta razao ? Por que nao damos um nome bonito, numero superfeito, aqueles numeros em que a razao entre eles e a soma de seus divisores sera 1/4 ? Quais sao esses numeros ?Eles sao em numero finito ? O que falar dos numeros cuja nrazao entre ele e seus divisores e p/q ? Existe uma bijecao entre esses numeros e os racionais ? Sera que com essa caracterizacao nao ficaria mais facil falar dos numeros perfeitos, inclusive ? Vamos, entao, chamar de CARACTERISTICA de um numero a razao entre ele proprio e seus divisores positivos. Os nemeros perfeitos serao aqueles de caracteristica 1/2. From: leonardo mattos [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Re: [obm-l] 1 é primo? Date: Tue, 27 Aug 2002 17:34:15 + From: Marcelo Roseira [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] 1 é primo? Date: Tue, 27 Aug 2002 12:03:54 -0300 1 nao é primo.p é primo se divisivel por (+ou-)p sendo p diferente de 1. 1 é primo? Vi num livro uma definição que dizia que um número p é primo se é divisível por (+ou-p) e (+ou-)1. Logo 1 é primo. Correto? Grato. = 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] = _ Tenha você também um MSN Hotmail, o maior webmail do mundo: http://www.hotmail.com/br = 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] =
[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] 1 é primo?
Ola Carissimo Prof Nicolau e demais colegas desta lista ... OBM-L, Esta observacao do Prof Nicolau so reforca a tese de que, em verdade, nos conhecemos muito pouco sobre os numeros primos. Veja que o status do numero 1 e ad hoc, sem nenhum principio maior que nos diga o que ele e e qual a sua natureza autentica. Quando eu comecei a estudar os primos gaussianos fiquei felicissimo. De cara descobri que 5=(2-i)(2+i) e que, portanto, por este angulo, 5 nao e primo. Pensava que a balburdia ia acabar ... Ledo engano ! Afinal, em que sentido os inteiros gaussianos esclarecem melhor a natureza dos numeros primos ? O livro nao dizia ! Ninguem me respondeu ! MUDANCA DE 360 GRAUS ! 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. Um abraco (Vou correr atras desta noticia) Paulo Santa Rita 3,1706,270802 From: Nicolau C. Saldanha [EMAIL PROTECTED] Reply-To: [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] 1 é primo? Date: Tue, 27 Aug 2002 16:32:47 -0300 On Tue, Aug 27, 2002 at 06:47:56PM +, Paulo Santa Rita wrote: Ola Leonardo e demais colegas desta lista, Esta discussao e deveras interessante ... Já falaram muita coisa sobre esta pergunta mas gostaria de acrescentar uma curiosidade histórica. Se você der uma olhada em tabelas de primos impressas no início do século XX o número 1 sistematicamente aparece como primo mas se você olhar em livros de teoria de números do meio para o fim do mesmo século o número 1 sistematicamente aparece como não primo. Ou seja, a definição 'usual' mudou... []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] = = 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] =
