Re: Primos

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

On Thu, 1 Jul 1999, Alexandre Stauffer wrote:

> > Sem querer tirar o merito de achar numeros primos tao grandes, mas qual a
> > utilidade disso?
> O RSA, sistema mais eficiente de criptografia de chave publica, eh 
> baseado em numeros primos grandes.
> 
> Voce pega dois numeros primos: "p" e "q". E distribui o produto 
> deles. Com esse produto voce pode codificar um texto, mas so 
> podera decodifica-lo se souber os primos p e q.

Mais precisamente, você distribui além dos produtos um número b
e guarda secretamente um número c tais que bc = 1 mod (p-1)(q-1).
Para encodificar, elevamos x aa potencia b modulo pq, ou seja,
transmitimos y = x^b mod pq. Decodificamos elevando a c, pois
y^c = x^(bc) = (pelo Teorema de Euler) x mod pq.

> Assim sendo, quanto maiores forem os primos p e q, mais dificil 
> sera fatorar o produto entre esses primos.... estima-se que um 
> super-computador levaria 10^31 anos para fatorar um numero 
> desses. Estima-se tambem que a terra possui 10^11 anos desde o 
> big-bang (se escreve assim?)

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.

Note que é muito mais fácil testar primalidade do que fatorar,
ou pelo menos é isso que *parece* ser verdade dados os conhecimentos
atuais sobre o assunto. Se P=NP tudo muda, se computadores quanticos
de medio porte forem viaveis tambem...

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