Re: Factoring integers on a classical computer

tchow_at_lsa.umich.edu
Date: 03/16/05 

Date: 16 Mar 2005 18:22:09 GMT

In article <1110993675.236875.97690@z14g2000cwz.googlegroups.com>,
 <cafeinst@msn.com> wrote:
>I don't understand why anyone would suggest that factoring could be
>NP-complete. It is not even in NP.

Factoring is polynomially equivalent to the question, "Given n and k,
does n have a factor in the interval [2,k]?" This decision problem could
conceivably be NP-complete, and so loosely people say that factoring
could be NP-complete. This is similar to saying that finding an optimal
traveling salesman tour is NP-complete. Strictly speaking it is the
decision problem "Given a distance matrix and a number k, does there
exist a tour with cost less than k?" that is NP-complete. But once this
is understood, fussing over semantics can become tedious and pedantic.

>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?

It doesn't *follow* if by "follow" you mean a rigorous argument.

>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.

What factor are you talking about? Prime numbers don't have nontrivial
factors. Are you saying that it's not possible to show that a number is
prime other than by searching the possible factors by brute force?

>Of course, I could be wrong. Dik 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 Dik's argument or not.

The argument is correct. What do you think is wrong with it? 

-- 
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

Relevant Pages

  • Re: TSP approximation algorithms
    ... >Recently I found out that even the Euclidean TSP is an NP-complete ... >conjectured that PRIMES would be in P. ... >some day we might find a definite polynomial-time algorithm for ...
    (comp.theory)
  • Re: Seeking an algorithm
    ... actually a multiset problem rather than a set problem, ... A problem is NP-complete if it is as hard as any problem in NP -- the ... resolve a long-standing open question in complexity theory (the ... algorithm that solves all the other know NP-complete problems as well. ...
    (sci.math)
  • Re: Question about the minesweeper consistency problem (NP-complete problems)
    ... >> There's also a result that says that every NP-complete ... >> whose EXPECTED running time is polynomial. ... > time of the algorithm is the worst-case time of these. ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... Factoring is polynomially equivalent to the question, "Given n and k, ... conceivably be NP-complete, and so loosely people say that factoring ... traveling salesman tour is NP-complete. ... >don't work by magic, so somewhere within the AKS algorithm, at least ...
    (comp.theory)
  • Re: 1M prize P, NP and factorization and other invaluable things
    ... decision problems. ... Factoring is known NOT to be ... factoring can not be NP-hard if P!= NP; ... either P or NP-complete. ...
    (sci.crypt)