<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0cm;
margin-right:0cm;
margin-bottom:0cm;
margin-left:36.0pt;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:72.0pt 72.0pt 72.0pt 72.0pt;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:685793426;
mso-list-type:hybrid;
mso-list-template-ids:-1361272058 134807569 134807577 134807579 134807567 134807577 134807579 134807567 134807577 134807579;}
@list l0:level1
{mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-18.0pt;}
ol
{margin-bottom:0cm;}
ul
{margin-bottom:0cm;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-GB link=blue vlink=purple>
<div class=WordSection1>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><a
href="http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf">http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf</a><o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>The math is
somewhat over my head, I’m afraid.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>So here is my
basic understanding of what this means.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>Eg a
* n^3 + b * n^2 + c * n + d <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>But only in terms
of a much faster-rising function like an exponential <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>Eg
a ^ (b * n)<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>And in
general, that means that there is no method of solution that is significantly
faster than brute-force testing all the alternatives.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>So P problems
have NP solutions (always?) but it’s not previously been proved that there
are NP problems that cannot have P solutions<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>Which means
that RSA users get to breathe a small sigh of relief, compared to the position
if the author had proved P = NP.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>I’m
sure we have some real mathematicians here, so how am I doing so far?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>So I get a
couple of questions.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>1) Has
it actually been proven that such factorisation is actually NP? <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>2) If so,
then this does of course preclude there from being any algorithmic solution
that can reliably factor any arbitrary product quickly. <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>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?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>In other words,
is P != NP a guaranteed strong mathematical safety net for RSA, or could it become
a weak one?<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:"Arial","sans-serif"'>D.<o:p></o:p></span></p>
</div>
</body>
</html>