Re: Primos

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

On Sun, 4 Jul 1999, Alexandre Stauffer wrote:

> > > Testar primalidade realmente eh muito mais facil (ate porque 
> > > existem algoritmos bem eficientes nesse ponto). Eu ja ouvi dizer 
> > > que usaram pseudo-primos em sistemas que nao exigem muita 
> > > seguranca....
> > Não é propriamente verdade que usem pseudo-primos, usam números
> > que quase certamente são primos mas podem (com uma probabilidade muito
> > muito pequena) ser pseudo-primos.
> > 
> > Um teste deste tipo é o seguinte: seja n um número ímpar maior do
> Esse nao é o chamado Teste de Miller?

Quase. Pela terminologia que eu conheço, o teste de Miller consiste
em dizer que se valer a Hipótese de Riemann Generalizada, então
para verificar a primalidade de n basta fazer este teste para todos os
valores de x menores do que C*(log x)^2 (ou algo do gênero).
De qualquer forma, muito mais testes do que se faria para aplicações
"tecnológicas" onde ninguém faz muita questão de ter uma demonstração
mas mesmo assim você não tem propriamente uma demonstração, só se 
a dita hipótese for verdadeira.

A hipótese de Riemann é um dos problemas em aberto mais famosos
da matemática.
> 
> > > Se alguem descobrir uma maneira eficiente de fatorar um numero 
> > > grande; voce acha que essa pessoa vai contar como fatora-los ou 
> > > vai tentar quebrar codigos de RSA por ai???
> > Acho que vai contar e ficar muito famoso.
> Depende do caracter e dos interesses da pessoa, ne???? Ainda 
> mais aqui no Brasil, onde a pesquisa nao eh valorizada....
> 

http://www.mat.puc-rio.br/~nicolau