Re: Primos

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

On Fri, 2 Jul 1999, Alexandre Stauffer wrote:

> > Uma estimativa destas só faz sentido se mencionarmos o tamanho dos
> > primos. Mas é muito rápido gerar primos de, digamos, 200 algarismos
> > e fatorar um inteiro de 400 algarismos é inviável com a tecnologia
> > atual.

> 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
que 1 e desejamos saber se n é primo. Escrevemos n-1 = 2^a b,
onde b é ímpar. Seja agora x um inteiro tomado ao acaso entre 1 e n-1.
Calculamos o mdc entre x e n: se for maior do que 1 n é composto e
acabou-se. Senão calculamos y0 = x^b mod n, y1 = y0^2 mod n, ...,
ya = y(a-1)^2 = x^(n-1) mod n. Se ya for diferente de 1, n é composto
(pelo pequeno teorema de Fermat; se n é primo e mdc(x,n) = 1 então
x^(n-1) = 1 mod n) e acabou-se. Se ya for igual a 1, procuramos
na seqüência y0, y1, ..., ya o último elemento diferente de 1.
Se este elemento for diferente de -1, n é composto e acabou-se pois,
se n é primo, as únicas soluções para a congruência x^2 = 1 mod n
são 1 e -1. Se tudo isto deu certo, dizemos que n é ou primo ou
pseudo-primo forte na base x. Se testarmos com vários valores de x
acabaremos detetando os pseudo-primos pois demonstra-se que um número
composto tem probabilidade no máximo 1/4 de enganar o teste acima
(em uma tentativa). Se repetirmos o teste, digamos, 20 vezes,
a probabilidade de termos um falso primo é menor do que 10^(-12).

> 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.

[]s, N.
http://www.mat.puc-rio.br/~nicolau