[obm-l] fatorando RSA

["Qwert Smith" <lord_qwert@xxxxxxxxxxx>]

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.  Como nao 
sei matematica mas estava com tempo de sobra resolvi procurar substituir o 
teste de primaridade por outro que na minha ignorancia parece mais simples e 
rapido.  Acabei com algo assim:

1) se N = pq entao p e q sao as solucoes da equacao x^2 - (p+q)x + N = 0.
2) De N(mod 10^t) da pra achar os valores possiveis de (p+q) (mod 10^t)
3) Consideracoes de um leigo:
3.1) o conjunto de valores possiveis em (2) e menor que o numero de primos 
em um  intervalo
de 10^t numeros.
3.2) testar se ((p+q)^2 - 4N) e quadrado perfeito eh mais rapido que testar 
a primaridade de um dos primos de (3.1)

Pergunta: Ja da pra eu ir buscar minha Fields ou devo manter meu day job por 
enquanto?

[],
Auggy


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