Re: Factoring integers on a classical computer

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 03/18/05 

Date: Fri, 18 Mar 2005 21:02:48 +0000 (UTC)

Craig Feinstein wrote:
>Has anyone tried to prove that factoring cannot be done in poly-time?

Tried? Or succeeded? Yes to the former, and no to the latter.
If anyone had succeeded in proving that factoring is hard, then we would
have heard of it by now, because if factoring cannot be done in poly-time,
then P != NP.

Come on. You'd be able to answer these questions yourself, if only
you took the time to study the subject on your own a little. This is
totally elementary stuff that is well-covered in basic textbooks (say,
a textbook on CS theory; a text on cryptography).

I would encourage you to do both of us a favor and go do some reading
before continuing this line of ill-informed posts on factoring.

Relevant Pages

  • Re: Factoring integers on a classical computer
    ... > "Since PRIMES is in P, it would seem logical that FACTORING should ... please explain your reasoning. ... I mean "If one can determine that a number is composite in poly-time, ...
    (comp.theory)
  • Re: Factoring integers on a classical computer
    ... > "Since PRIMES is in P, it would seem logical that FACTORING should ... please explain your reasoning. ... I mean "If one can determine that a number is composite in poly-time, ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... Craig Feinstein wrote: ... If anyone had succeeded in proving that factoring is hard, ... have heard of it by now, because if factoring cannot be done in poly-time, ... totally elementary stuff that is well-covered in basic textbooks (say, ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... if you can factor in poly-time, then you can solve this in poly-time, ... 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 ... Craig ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... if you can factor in poly-time, then you can solve this in poly-time, ... 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 ... Craig ...
    (comp.theory)