Re: Factoring integers on a classical computer

cafeinst_at_msn.com
Date: 03/16/05 

Date: 16 Mar 2005 09:21:15 -0800

t...@lsa.umich.edu wrote:
> In article <1110987192.055030.165180@l41g2000cwc.googlegroups.com>,
> Pubkeybreaker <Robert_silverman@raytheon.com> wrote:
> >If P != NP (and everyone competent who works in this area
believes
> >that it does), then there will exist an entire hierarchy of
algorithm
> >complexity ranging from P to EXP. We *already* have algorithms
for
> >factoring that are sub-exponential time; factoring is not
exponential
> >time and thus extremely unlikely to be NPC.
>
> There are several misleading statements here.
>
> (a) Not everyone competent believes that P != NP. See William
Gasarch's
> poll at http://www.cs.umd.edu/~gasarch/papers/poll.ps
>
> (b) We already know that there exists an entire hierarchy of
algorithm
> complexity ranging from P to EXP; this doesn't depend on assuming P
!= NP.
>
> (c) Even if (say) SAT takes exponential time, factoring could be
> NP-complete. Many-to-one Karp reductions can bump things up in the
time
> hierarchy to a certain extent.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however
great, will
> never exceed four of those miles of which as many thousand separate
us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New
Sciences

I don't understand why anyone would suggest that factoring could be
NP-complete. It is not even in NP. In order for a problem to be in NP,
it must have a yes-no answer, which factoring does not. PRIMES is in
NP, because it has a yes-no answer and can be checked in poly-time. It
is also in P (which is in NP), as proven in 2002 with the AKS
algorithm.

Back to my argument: If primes is in P, then why doesn't it follow that
there is an algorithm which factors in poly-time? After all, algorithms
don't work by magic, so somewhere within the AKS algorithm, at least
one of the factors had to have been computed indirectly; otherwise, how
could we trust the algorithm? That factor might be hidden within the
structure of the algorithm, but it has to be there; otherwise, the
algorithm would work by magic.

Of course, I could be wrong. *** Winter gave a counter-argument with
Fermat's Little Theorem as a way of proving that a number is composite.
I'm not sure if I buy ***'s argument or not.

Craig

Quantcast