Re: Factoring integers on a classical computer

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

  • Next message: Craig Feinstein: "Re: Factoring integers on a classical computer" 
    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

  • Next message: Craig Feinstein: "Re: Factoring integers on a classical computer"

    Relevant Pages