Re: Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/18/05 

Date: 18 Mar 2005 09:25:34 -0800

Also, as for the problem that you mentioned

"find the orders of numbers mod N (i.e. given x and N, find the least
r>0 such that x^r = 1 (mod N))"

if you can factor in poly-time, then you can solve this in poly-time,
since the only candidates for r are the factors of phi(N) and there are
only polynomially many factors of phi(N).

Has anyone tried to prove that factoring cannot be done in poly-time?
After I read about the algorithm using the FFT which ran in O(n^{1/4})
time, I thought there could be no way to beat it - it was so darn
clever. But then I read that there was an algorithm that could run in
O(n^{1/5}) time, which caused me to think that maybe there is a
poly-time algorithm for factoring. Now I'm not so sure.

Craig

Relevant Pages