Expand Messages
• Extending this debate, if it could be shown that factoring is in P, do we have a direct line to establishing primality testing is in P? Jon Perry
Message 1 of 10 , Apr 2, 2003
Extending this debate, if it could be shown that factoring is in P, do we
have a direct line to establishing primality testing is in P?

Jon Perry
perry@...
http://www.users.globalnet.co.uk/~perry/maths/
BrainBench MVP for HTML and JavaScript
http://www.brainbench.com
• --On Wednesday, April 02, 2003 7:05 PM -0500 Jud McCranie ... Is factoring NP-HARD? Nathan
Message 2 of 10 , Apr 2, 2003
--On Wednesday, April 02, 2003 7:05 PM -0500 Jud McCranie
<judmccr@...> wrote:

> At 06:22 PM 4/2/2003, you wrote:
>
>> Not necessarily.
>
> Yes, I should have said that the original question "It is true that if
> finding primes is P then so is finding factors of composites?" is not
> known to be true. That is, PRIMES being in P doesn't imply that
> factoring is too. Personally, I think factoring is not in P.

Is factoring NP-HARD?

Nathan
• Thanks for that clarification, Jud. My understanding is that this question is indeed open. Moreover, I recall voting for the proposition that ... in the poll
Message 3 of 10 , Apr 2, 2003
Thanks for that clarification, Jud.
My understanding is that this question is indeed open.
Moreover, I recall voting for the proposition that
> factoring is in NP not P
in the poll (still open?) at
conducted by our dear departed not-the-mod Phil.
David
• ... If I knew that... Factoring seems so much harder than proving primality that I doubt that it is in P. The NP-Complete problems are optimization problems
Message 4 of 10 , Apr 2, 2003
At 07:13 PM 4/2/2003, Nathan Russell wrote:

>Is factoring NP-HARD?

If I knew that...

Factoring seems so much harder than proving primality that I doubt that it
is in P. The NP-Complete problems are optimization problems (what is the
shortest path) and their corresponding decision problem (is there a path
shorter than x). I don't know if factoring can be stated as an appropriate
optimization or decision problem, so I doubt that it is NP-complete. But
it could be at least as hard as the NP-complete problems (i.e. NP-hard) or
it could be between P and NP-hard. If I had to guess between those two
right now, I might slightly favor its being in between. That's just a
guess though.
• ... The integer factorization problem can indeed be reduced to a decision problem, namely, given positive integers n and k, does n have a factor d such that
Message 5 of 10 , Apr 3, 2003
--- Jud McCranie <judmccr@...> escribió:
---------------------------------

>The NP-Complete problems are optimization problems
>(what is the shortest path) and their corresponding
>decision problem (is there a path shorter than x). I
>don't know if factoring can be stated as an
>appropriate optimization or decision problem, so I
>doubt that it is NP-complete.

The integer factorization problem can indeed be
reduced to a decision problem, namely,
given positive integers n and k, does n have a factor
d such that 2<= d <= k?

The problem of finding a factor of n can be reduced to
this decision problem in polynomial time by means
of a "binary search" that will find the bits of a
factor one at a time, starting with the leading one.

On the other hand, it is not known whether the
factorization problem is NP-complete but it
seems that it is widely regarded as "easier" than
NP-complete. By a well-known result of Peter Shor, a
quantum computer can factor integers in polynomial
time but, on the other hand, there are results (see
C.H. Bennet, E. Bernstein, G. Brassard, U. Vazirani,
Strengths and weaknesses of quantum computing, SIAM J.
Computing 26 (1997), 1510-1523) that suggest that even
quantum computers might not be able to solve
NP-complete problems.

In the last paragraphs of his paper "Polynomial-time
algorithms for prime factorization and discrete
logarithms on a quantum computer", Peter Shor says it
best:

"... quantum computers will likely not become
widely useful unless they can solve NP-complete
problems. Solving NP-complete problems efficiently
is a Holy Grial of theoretical computer science which
very few people expect to be possible on a classical
computer. Finding polynomial-time algorithms for
solving these problems on a quantum computer would be
a momentous discovery. There are some weak indications
that quantum computers are not powerful enough to
solve
NP-complete problems [Bennet et al, cf. above], but I
do not believe that this potentiality should be ruled
out as yet".

Best,

Jose Luis.

___________________________________________________
Yahoo! Messenger - Nueva versión GRATIS
Super Webcam, voz, caritas animadas, y más...
http://messenger.yahoo.es
• ... Yes, but primality testing is already proven to be in P.
Message 6 of 10 , Apr 3, 2003
At 06:29 AM 4/2/2003, Jon Perry wrote:
>Extending this debate, if it could be shown that factoring is in P, do we
>have a direct line to establishing primality testing is in P?

Yes, but primality testing is already proven to be in P.
• ... Hash: SHA1 ... If we can factor in polynomial time, in particular we can obtain the factorization of a prime number (only the prime itself, obviously) in
Message 7 of 10 , Apr 3, 2003
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Wednesday 02 April 2003 08:29, Jon Perry wrote:
> Extending this debate, if it could be shown that factoring is in P, do we
> have a direct line to establishing primality testing is in P?
>

If we can factor in polynomial time, in particular we can obtain the
factorization of a prime number (only the prime itself, obviously) in
polynomial time.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+jE7wce3VljctsGsRArR2AKCYC9XS1ccRKYFi6bTY4iFXc72oOwCcDKTA
0YTI6FGjUoQ4nex5i2ZIkCc=
=GCsB
-----END PGP SIGNATURE-----
Your message has been successfully submitted and would be delivered to recipients shortly.