HP researcher claims proof that P != NP

[David Biggins]

http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf

 

I understand that some mathematicians are already questioning it - which
of course is right, whether the proof is correct or not.  Mathematics
and science are based on scepticism and on the requirement for claims of
proof to be tested.

 

The math is somewhat over my head, I'm afraid.

 

So here is my basic understanding of what this means.

 

Proving P != NP means that it can be proved that there are classes of
problem for which no algorithm can solve them in polynomial time.

 

For the non-mathematicians among us, a vast-over simplification is that
as the core number in a problem gets bigger, there is no possible
solution where the number of steps needed to guarantee a result can be
expressed as a polynomial of the number (n) of digits in that number. 

 

Eg    a * n^3 + b * n^2 + c * n + d  

 

But only in terms of a much faster-rising function like an exponential 

 

Eg    a ^ (b * n)

 

Even more roughly, this might be interpreted to mean that the difficulty
of solution has to relate to how many different values a number of that
length could take, rather than of the length of the number.   E.g., how
many possible keys there could be, rather than the key length.

 

And in general, that means that there is no method of solution that is
significantly faster than brute-force testing all the alternatives.

 

So if factoring a large number that is the product of two primes, to get
back the factors,  is a problem that is NP, and also P != NP,  then
there can be no solution that is any significant order of magnitude
faster than dividing it by every prime less than it's square root and
testing the remainder.

 

The question of P = NP or P != NP arises because a 'P' problem that has
a shorter algorithmic solution can of course still be solved by brute
forcing.   There are efficient ways of obtaining a square root, but you
can still do it by dividing by squaring all numbers up to the square
root and comparing.

 

So P problems have NP solutions (always?) but it's not previously been
proved that there are NP problems that cannot have P solutions

 

Which means that RSA users get to breathe a small sigh of relief,
compared to the position if the author had proved P = NP.

 

I'm sure we have some real mathematicians here, so how am I doing so
far?

 

So I get a couple of questions.

 

1)  Has it actually been proven that such factorisation is actually NP?


 

Or is this still a "most of us believe that... but haven't proved it
yet"  like P!= NP has been for the last many years?

 

2) If so, then this does of course preclude there from being any
algorithmic solution that can reliably factor any arbitrary product
quickly.  

 

However, does it provably preclude probabilistic solutions that often
(for some value of often) work but sometimes fail?  Perhaps for cases
where one of the primes has other constraints, like being one of the
Mersenne primes, or some other such case?

 

In other words, is P != NP a guaranteed strong mathematical safety net
for RSA, or could it become a weak one?

 

 

D.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.chiark.greenend.org.uk/pipermail/ukcrypto/attachments/20100811/99f3ab20/attachment-0001.htm>