🚀 go-pugleaf

In article <1992Nov16.152501.22172@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
>In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
>>It is true that if P=NP then all cryptography everywhere (not just RSA)
>>is dead; but at this point I wouldn't take Swart's claims seriously
>>without seeing some consensus among complexity efforts that unlike
>>his previous attempts, his latest effort is free of bugs.
>
>To rephrase Herman Rubin's point: an O(n^1000) algorithm for an NP-hard
>problem will show P=NP without compromising cryptography in the
>slightest.

If such an algorithm was found, I wouldn't trust RSA further than I
could throw it without a proof that factoring is something on this
order of hardness, and such a proof doesn't exist at the moment.  If
it's O(n^1000) today, then people will be bringing Fibonacci heaps and
hash tables and all sorts of odd things to bear on it until it's beaten
down to something smaller; and "something smaller" might be O(n^3).
  __                                ____
\/ o\ Paul Crowley pdc@dcs.ed.ac.uk \  /
/\__/ "I'm the boy without a soul"   \/