Re: [obm-l] Re: [obm-l] 1 é primo?
A consideracao de 1 como primo nao quebra o teorema da fatoracao unica?? 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] =
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] =
Re: [obm-l] Indianos solucionam problema matemáticomilenar
Ja vi este e outros textos semelhantes na net, mas cuidado com alguns erros de traducao ou comentarios errados. Este eh um dos mais grotescos: O sistema de encriptação usado para proteger transações pela Internet conta com o fato de ser extremamente difícil descobrir os fatores de grandes números primos. Fatorar numeros primos eh muito facil... ;-)) Varios dos artigos que li, principalmente aqueles provenientes de meios de comunicacao comuns(populares como revistas e jornais) falam que os criptossistemas como o RSA estao ameacados. Isto nao eh verdade! Pelo contrario, muitos desses criptossistemas precisam testar a primalidade de numeros para a construcao de chaves (ex. RSA) mas acabam se utilizando de algoritmos probabilisticos. O problema no qual a dificuldade eh utilizada como base para a contrucao de criptossistemas eh o problema da FATORACAO, para o qual ainda nao existe resposta eficiente. O temor de alguns pesquisadores (e que em alguns artigos que li foi traduzido de forma errada) eh que se possa utilizar tecnicas semelhantes aas dos indianos para resolver o problema da fatoracao de forma eficiente. Abracos, Rodrigo Alexandre Botelho MAGALHÂES de Oliveira wrote: Eu li a pouco na net esse artigo a respeito de testes de primalidade. Indianos solucionam problema matemático milenar Nicola Dixon Da New Scientist Três cientistas da computação chocaram a comunidade de matemáticos ao encontrar a solução para um problema que dura séculos: como dizer se um número é primo. A prova é impressionante em sua simplicidade, e fez os matemáticos se perguntarem o que mais eles podem ter deixado passar. Os números primos, que são divisíveis apenas por si mesmos e 1, são blocos de construção fundamentais da matemática e fascinam estudiosos desde os tempos antigos. Em 240 a.C., o matemático grego Eratóstenes apresentou a primeira forma à prova de falhas para saber se um número era primo. Mas o tempo que o método exige cresce exponencialmente com o tamanho do número, de forma que para números muito longos é necessário mais tempo que a idade do Universo para solucionar o problema. Desde então os matemáticos têm tentado encontrar um algoritmo de tempo polinomial, capaz de fornecer uma resposta em uma quantidade de tempo razoável. A busca se intensificou ao longo das últimas poucas décadas, desde que os números primos se tornaram vitais para a criptografia. O sistema de encriptação usado para proteger transações pela Internet conta com o fato de ser extremamente difícil descobrir os fatores de grandes números primos. Os algoritmos usados atualmente para ajudar a encontrar estes fatores são rápidos, mas eles apenas fornecem a probabilidade de um número ser primo ou não. Apesar da probabilidade ser muito alta, estes algoritmos não representam uma prova. Agora Manindra Agrawal e seus alunos ainda não formados, Neeraj Kayal e Nitin Saxtena, foram bem-sucedidos onde as melhores mentes da matemática fracassaram. O trio, do Departamento de Ciência da Computação e Engenharia do Instituto Indiano de Tecnologia em Kanpur, desenvolveram um algoritmo que dá uma resposta definitiva para o problema em tempo razoável. O sucesso deles está na nova abordagem que adotaram para o problema. Em vez de fazer a grande pergunta, este é um número primo?, eles geraram uma série de perguntas menores ou igualdades do número que está sendo testado. Se as igualdades se sustentarem, o número é primo, se alguma delas não se sustentar, então o número não é primo, explica Agrawal. Até o momento milhares de matemáticos verificaram as provas postadas atualmente no site do instituto na Internet. Todos os que me mandaram e-mails apreciaram o algoritmo e disseram que ele está correto, diz Agrawal para a New Scientist. Especialistas suspeitavam que um algoritmo de tempo polinomial fosse possível. Mas não previam a simplicidade da solução em 13 linhas que Agrawal e seus colegas apresentaram. É uma bela solução e estou muito feliz por eles, mas estou um pouco embaraçado por não ter visto isto eu mesmo, diz o especialista em números primos Carl Pomerance, dos Laboratórios Bell da Lucent, em Nova Jersey. A solução deles é simples. Isto não quer dizer que seja trivial; o que eles fizeram foi muito inteligente, acrescenta. O avanço teórico é significativo por si só, mas Ian Stewart da Universidade de Warwick disse que o método também deverá ajudar os matemáticos a solucionarem outros problemas, nos quais chegaram a um beco sem saída usando outras técnicas. A segurança na Internet ainda não está sob ameaça. A solução provavelmente terá um impacto muito pequeno, pois ela não oferece nenhuma vantagem real sobre os algoritmos probabilísticos já usados no setor, afirma Ben Hadley da nCipher, uma empresa de segurança por criptografia baseada em Cambridge. Mas Pomerance acredita que a existência da prova deixará os criptologistas preocupados. Se há um teste simples para saber se um
Re: [obm-l] RES: [obm-l] Numeros primos - solução
Ola, A classe de todas as linguagens polinomialmente decidíveis é denotada por P [P do inglês polinomial] e a classe de todas as linguagens que não pertecem a P é denotada por NP [NP do inglês no-polinomial]. NP vem do ingles nondeterministic polynomial time. Problemas (ou linguagens, como voce definiu) em NP nao sao necessariamente nao-polinomiais. Se fossem, teriamos resposta para o problema P=NP. NP representa a classe de problemas para os quais se consegue um algoritmo nao-deterministico que rode em tempo polinomial (equivalente a se conseguir verificar uma saida deterministicamente em tempo polinomial). Todo problema em P necessariamente esta em NP, mas o inverso ainda eh um problema em aberto. De acordo com o documento Primes in P, os autores apresentam um algoritmo que decide se um dado número n é primo ou composto [dei uma lida rápida] com uma complexidade computacional O([log(n)]^6), podendo futuramente chegar a O([log(n)]^3), desde que se prove a conjectura de Bhattacharjee-Pandey. Talvez minha olhada tenha sido mais rapida que a sua, mas eu havia lido o seguinte: We give a deterministic, O((log n)^12) time algorithm for testing if a number is prime. Heuristically, our algorithm does much better: under a widely believed conjecture on the density of Sophie Germain primes (primes p such that 2p+1 is also prime), the algorithm takes only O((log n)^6) steps. Mas realmente, no final do artigo, seguindo outras conjecturas os autores comentam a possibilidade de uma implementacao O((log n)^3). No entanto, enquanto a Conjectura 5 do artigo (Sophie Germain) ainda nao for provada, o algoritmo deles continua tendo complexidade deterministica O((log n)^12), o que, para numeros com 1000 bits por exemplo, nao eh muito viavel na pratica. Minhas referencias sao dos livros: Introduction to Algorithms. Thomas Cormen et al. Introduction to Algorithms - A creative approach. Udi Manber. e do artigo: PRIMES is in P. Agrawal, Kayal e Saxena. Abracos, Rodrigo = 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] Complexidades P e NP
Sim, todos os problemas em P. Por definicao, P eh um subconjunto de NP. Ou seja, todos os problemas em P tambem estao NP. Abraco, Rodrigo Edilon Ribeiro da Silva wrote: Gostaria de saber se existe algum problema que pertença simultaneamente à classe de complexidade P e à classe de compleidade NP. Edilon Ribeiro. = 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] Complexidades P e NP
Ola, Uma pequena correcao nas colocacoes do Vinicius... A classe P significa que a solução pode ser verificada em tempo polinomial. A classe NP significa que a solução pode ser verificada não-deterministicamente em tempo polinomial. A classe P eh a classe dos problemas que podem ser RESOLVIDOS por algoritmos deterministicos em tempo polinomial (e nao a classe dos problemas que tem sua resposta verificada em tempo polinomial). De forma semelhante, a classe NP eh a classe dos problemas que podem ser RESOLVIDOS por algoritmos nao-deterministicos em tempo polinomial no tamanho da entrada. Isto eh equivalente a dizer que uma resposta pode ser VERIFICADA deterministicamente em tempo polinomial. Abracos, Rodrigo = 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] o Livro dos Códigos
Oi, sejam, M,E,P e Q tal que P e Q sao primos e E é primo com (P-1)*(Q-1) entao calcule: (M representa a mensagem original e C a mensagem cifrada) C=M^E (mod P*Q) calcule D tal que: E*D=1 (mod (P-1)*(Q-1)) Supondo que D foi calculado. (mais adiante eu explico como) entao prove que: M=C^D (mod P*Q) alguém poderia me ajudar a demonstrar isso ?? Pelo Teorema de Euler: Se a e b sao primos entre si, entao a^k = a^(k mod phi(b)) (mod b) Entao, como phi(P*Q) = (P-1)*(Q-1) e C^D = M^(E*D) (mod P*Q) entao M^(E*D) = M (mod P*Q) no livro ele diz que D pode ser encontrado através do Algoritmo de Euclides .. alguém pode me dizer como é ?? O Algoritmo de Euclides serve para calcular o mdc de dois valores. Sua forma original eh a seguinte: funcao mdc(a,b) se (b = 0) retorne a senao retorne mdc(b,a mod b) Eh sabido que o mdc de dois valores eh uma combinacao linear dos mesmos. Existe um algoritmo conhecido como o algoritmo estendido de Euclides que retorna esta combinacao linear, ao inves de simplesmente o valor do mdc: mdc_estendido(a,b) retorna uma tripla d,x,y, onde d = mdc(a,b) e d=ax+by * no codigo abaixo, -- significa atribuicao de um valor a uma variavel funcao mdc_estendido(a,b) se (b=0) retorne a,1,0 fim se d',x',y' -- mdc_estendido(b,a mod b) d,x,y -- d',y',x' - piso(a/b) * y' retorne d,x,y A prova de corretude do 2o algoritmo sai por inducao: (supondo a corretude do algoritmo de euclides original) A base eh trivial (b = 0) passo: pela hipotese temos que d' = bx' + (a mod b)y' Como d = d' (pelo algoritmo original de Euclides) d = bx' + (a - piso(a/b) * b)y' = ay' + b(x' - piso(a/b) * y') = Como calcular D no RSA E*D=1 (mod (P-1)*(Q-1)) D eh calculado pelo algoritmo de euclides, pela invocacao 1,D,X -- mdc_estendido(E,(P-1)*(Q-1)) Sabe-se que E eh primo relativo de (P-1)*(Q-1), entao mdc = 1; e para os fins do RSA, o valor X retornado pode ser desprezado, ficando-se com o D. Espero ter ajudado, Rodrigo muito obrigado .. Mathematicus nascitur, non fit Matemáticos não são feitos, eles nascem --- Gabriel Haeser www.gabas.cjb.net -- Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.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] = = 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] Problemão que circulou em outra lista
Os numeros sao positivos ou podem ser negativos? Marcos Melo wrote: Para o caso de não ter circulado por esta lista: *** Texto do Problema * Dois amigos se encontram. Um tem o produto de dois numeros (Sr. P) e o outro tem a soma dos dois numeros (Sr. S). Nenhum dos dois sabe quais sao os numeros. Entao eles desenvolvem o seguinte dialogo: Sr. S: A soma eh menor que 99. Sr. P: Deste jeito, eu nao sei quais sao os numeros. Sr. S: Entao eu tambem nao sei quais sao os numeros. Sr. P: Se voce nao sabe ainda, eu tambem nao sei. Sr. S: Como voce nao sabe, eu tambem nao sei. Sr. P: Agora, eu sei quais sao os numeros. Sr. S: Eu tambem sei. Quais sao os numeros? * = 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] Somatorio de Combinacoes
Luis,
A resposta tambem pode ser:
S_n = 1 - \binom{n-3}{(n/2) - 1} (1/2)^{n-3}.
Interessante eh que as duas formas sao equivalentes.
Voce poderia me dizer como voce chegou na respota. Qual foi o seu
raciocinio??
Abraco,
Rodrigo
Luis Lopes wrote:
Sauda,c~oes,
Vc tem a resposta?
Encontrei
S_n = 1 - \binom{n-2}{(n/2) - 1} (1/2)^{n-2}.
[]'s
Luis
-Mensagem Original-
De: Rodrigo Malta Schmidt [EMAIL PROTECTED]
Para: [EMAIL PROTECTED]
Enviada em: sábado, 13 de abril de 2002 09:52
Assunto: [obm-l] Somatorio de Combinacoes
Ola pessoal,
Alguem sabe simplificar este somatorio, dado um numero par n:
Somatorio em i variando de (n/2)-1 ate n-3 de C[i,(n/2)-1] * (1/2)^i
onde C[i,j] eh o numero de combinacoes de i elementos agrupados j a j.
Eu ja tentei varias coisas em cima do Triangulo de Pascal mas nao obtive
bons resultados.
Obrigado,
Rodrigo
=
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] Somatorio de Combinacoes
Ola pessoal, Alguem sabe simplificar este somatorio, dado um numero par n: Somatorio em i variando de (n/2)-1 ate n-3 de C[i,(n/2)-1] * (1/2)^i onde C[i,j] eh o numero de combinacoes de i elementos agrupados j a j. Eu ja tentei varias coisas em cima do Triangulo de Pascal mas nao obtive bons resultados. Obrigado, Rodrigo = 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] Power!
Sim.
Voce quer calcular
a^(a^(a^(...a^a))) % 1
Agora vamos chamar a^(a^(a^(...a^a))) de a^^(n) certo??? So para nao
complicar ainda mais as coisas.
Por inducao vemos que
a^^(n) = a^(a^^(n-1))
Se a nao eh multiplo de 5 nem de 2 entao eh primo relativo de 1,
certo??
Se a eh primo relativo de 1, entao pelo teorema de Euler
a^^(n) = a^(a^^(n-1)%phi(1)) (mod 1)
phi(1) = 2/5(1) = 4000
a^^(n) = a^( a^^(n-1)%4000 ) (mod 1)
Fazendo tudo de novo...
Queremos calcular...
a^^(n-1) % 4000
como mdc(a,4000)=1
a^^(n-1) = a^(a^^(n-2)%phi(4000)) % 4000
phi(4000) = 2/5(4000) = 1600
E por ai vai ate que voce chega em
a^^{k} mod 1 que eh 0
Depois eh so voltar fazendo algumas exponenciacoes.
Voce precisa de algumas iteracoes mas eh bem mais rapido do que fazer
todas as exponenciacoes originais.
Se nao me fiz entender, posso ser mais detalhista.
Ab,
Rodrigo
Vinicius José Fortuna wrote:
Pessoal,
Existe alguma forma fácil de se calcular os 4 primeiros dígitos de
a^(a^(a^(...a^a))) (o 'a' aparece n vezes)
Sendo que a não é múltiplo de 2 nem de 5
Obrigado
Vinicius Fortuna
=
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] Logarítimo discreto
Vinicius, A questao original dizia que P era primo e comentava que a resposta dependia do teorema de Fermat (B^(P-1) = 1 (mod P)). Ab, Rodrigo Vinicius José Fortuna wrote: Dados P, P=2, B, 2=BP e N, 2=NP, existe uma forma fácil de calcular o menor L não negativo tal que: B^L == N (mod P) ??? Obrigado Vinicius Fortuna = 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: funções e fatorial
Argh!!! Eu escrevi sin ao inves de cos. :))) sin (x*PI) = 0 O certo entao seria: f(x) = cos(x * PI) g(x) = cos((x+1) * PI) Rodrigo Malta Schmidt wrote: 2)ache f(x) e g(x) para: f(x)g(x) , se x for par f(x)g(x) ,se x for impar Que tal: f(x) = sin(x * PI) g(x) = sin((x+1) * PI) Rodrigo
Re: funções e fatorial
Oooopss!!! Sera que escrevi alguma besteira alem de ter trocado as funçoes inicialmente. PI em radianos sao 180°. cos(0) = 1 e cos(PI) = -1. como a funçao cos tem um periodo de 2*PI. cos(k*PI) eh 0 para k par e -1 para k impar Ab, Rodrigo gabriel guedes wrote: Ola rodrigo, gostaria de saber como vc chegou a tal conclusão???poderia demonstrar o racicinio??? - Original Message - From: Rodrigo Malta Schmidt [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Friday, December 14, 2001 9:22 PM Subject: Re: funções e fatorial Argh!!! Eu escrevi sin ao inves de cos. :))) sin (x*PI) = 0 O certo entao seria: f(x) = cos(x * PI) g(x) = cos((x+1) * PI) Rodrigo Malta Schmidt wrote: 2)ache f(x) e g(x) para: f(x)g(x) , se x for par f(x)g(x) ,se x for impar Que tal: f(x) = sin(x * PI) g(x) = sin((x+1) * PI) Rodrigo
Re: funções e fatorial
Olha o sono... :))) cos(k*PI) eh 0 para k par e -1 para k impar ^ eh 1 para k par. :))
