the reason we need to factor n into p*q is so that we can calculate phi(n)=(p-1)*(q-1), right? well, what if, instead of trying to find a better factoring algorithm, we try to find a fast way to compute the totient without knowing the factors.....
No. Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.
Okay, well take any n which is a semiprime and do mod 4 of it. eg, the remainder when it is divided by 4. So if I have p=13 and q=19, that means p mod 4=1 and q mod 4=3, so pq mod 4=3. That means that if we have an n, where n mod 4=3, it either means the p mod 4=3 or q mod 4=3, and the other mod 4 =1.
There is one thing I messed up, though. It is supposed to be (4x+1)(4y+3)=16xy2+12x+4y+3. I'll go fix that in my last post... Basically, though, if you solve that over the integers, it yields the factors. There is only one solution.
Why 16*x*y^2? I think its 16xy.
---------------------------------------------------------------------------------------------------------------------
I believe the factorization of RSA-768 used the NFS. If we were really crazy, we could try writing an implementation of the NFS that is faster than what we currently have (GGNFS + Msieve).
Number field sieves are hard to write
It would be an interesting community project, though.
Powered by SMF 1.1.18 |
SMF © 2013, Simple Machines
