[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] fatorando RSA
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
=========================================================================