PGP crackable? PGP secure?

PGP crackable? PGP secure?

Post by Boudewijn W. Ch. Viss » Fri, 14 Mar 1997 04:00:00

>> >In Papadimitriou's _Computational Complexity_, he shows on
>> >p. 222 that determining whether a number is prime or not is
>> >in NP.  It follows trivially from that that factoring is in
>> >NP (it's talked about elsewhere in the same book).  This
>> >result is not obvious, but it is known.

>> I think there must be a mistake somewhere.
>> Your/Papadimitriou's statement would also imply that the Extended Riemann
>> Hypothesis is false, which would be -very- great news.
>I'm not sure what the mistake is, but I'm fairly sure it's not
>in Papadimitriou.  Judging from your remark about the Extended
>Riemann Hypothesis, it may be a terminological problem.  "NP",
>as used by complexity theorists, does not stand for "NonPolynomial".
>"NP" stands for "Nondeterministic Polynomial".  A problem being in
>NP means it can be solved in polynomial time by a nondeterministic
>Turing machine.  The class "P" is the class of problems solvable
>in polynomial time by a _deterministic_ Turing machine.  A
>problem being in NP doesn't mean it's _not_ in P: P is a subset
>of NP.

Ah, well I knew that NP was a superset of P, but IMHO your statement
was phrased a bit misleading then. Usually it is only mentioned
that a problem is NP when it is NOT  in P, which is how I read your
posting. In that case, ERH would have been false.

Now that I think of it, I recall that there is a class of problems
that are even harder than those in NP, so proving that a problem is
at least in NP is indeed not useless.

I guess we can conclude for the status of factoring and primality testing
the following : Both are proven to be in NP at least, we have good reason
to believe that primality testing is in P, and the question on factoring
is still open.


|Dep. of Applied Physics,Delft University of Technology |PGP-key    |
+-- my own opinions etc --------------------------------------------+