Será que o passo (2) não vai demorar muito?
Na prática, N = pq tem pelo menos uns 200 algarismos.
| De: |
owner-obm-l@mat.puc-rio.br |
| Para: |
obm-l@mat.puc-rio.br |
| Data: |
Tue, 07 Dec 2004 15:59:35 -0500 |
| Assunto: |
[obm-l] fatorando RSA |
> 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
> =========================================================================
>