Re: [obm-l] fatorando RSA

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

On Tue, Dec 07, 2004 at 03:59:35PM -0500, Qwert Smith wrote:
> A algum tempo atraz tinha um maluco (adjetivo carinhoso) aqui na lista que 
> dizia que tinha revolucionado a fatoracao de numeros RSA.  Estou chamando 
> de numeros RSA o produto de 2 primos grandes.  Na epoca me interessei pelo 
> problema e agora que o trabalho diminuiu de ritmo volto a me interessar. 
> Tendo em consideracao que o numero de fatores eh sempre 2 me parece que 
> Quadratic Sieve seja o metodo mais logico de fatoracao, mas ociosidade, ou 
> mesmo falta de juizo me fazem pensar que achar um metodo mirabolante e 
> rapido seja possivel.  Me parece que a maior parte do tempo eh gasto 
> tentando determinar se um dos possiveis fatores eh de fato primo.

Existem algoritmos bem sofisticados para fatorar inteiros.
Alguns especialistas no assunto acham provável que o problema
de fatorar um inteiro admita um algoritmo de tempo polinomial
mas os algoritmos conhecidos são bem mais lentos.
E não estamos falando de computação quântica:
com computadores quânticos é *sabido* que é possível fatorar
em tempo polinomial; com computadores convencionais (ou com
máquinas de Turing), ninguém sabe.

Quanto a testar se um múmero é primo, isto é bem mais fácil.
Agora sabemos que existe um algoritmo polinomial que faz este teste.
Se você não fizer questão de *demonstrar* que o número é primo
e ficar satisfeito em saber que o número é quase certamente primo
então é muito fácil mesmo.

Resumindo, você está tentando melhorar a parte errada do algoritmo.

[]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
=========================================================================