home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4875 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.7 KB
  1. Xref: sparky sci.crypt:4875 sci.math:15069 comp.theory:2440
  2. Path: sparky!uunet!mcsun!uknet!edcastle!dcs.ed.ac.uk!pdc
  3. From: pdc@dcs.ed.ac.uk (Paul Crowley)
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Message-ID: <Bxtowv.246@dcs.ed.ac.uk>
  7. Date: 16 Nov 92 19:02:55 GMT
  8. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com> <1992Nov16.152501.22172@CSD-NewsHost.Stanford.EDU>
  9. Sender: cnews@dcs.ed.ac.uk (UseNet News Admin)
  10. Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
  11. Organization: Do they make a washing powder called Caliban Automatic?
  12. Lines: 20
  13.  
  14. In article <1992Nov16.152501.22172@CSD-NewsHost.Stanford.EDU> pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes:
  15. >In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com (Paul Rubin) writes:
  16. >>It is true that if P=NP then all cryptography everywhere (not just RSA)
  17. >>is dead; but at this point I wouldn't take Swart's claims seriously
  18. >>without seeing some consensus among complexity efforts that unlike
  19. >>his previous attempts, his latest effort is free of bugs.
  20. >
  21. >To rephrase Herman Rubin's point: an O(n^1000) algorithm for an NP-hard
  22. >problem will show P=NP without compromising cryptography in the
  23. >slightest.
  24.  
  25. If such an algorithm was found, I wouldn't trust RSA further than I
  26. could throw it without a proof that factoring is something on this
  27. order of hardness, and such a proof doesn't exist at the moment.  If
  28. it's O(n^1000) today, then people will be bringing Fibonacci heaps and
  29. hash tables and all sorts of odd things to bear on it until it's beaten
  30. down to something smaller; and "something smaller" might be O(n^3).
  31.   __                                ____
  32. \/ o\ Paul Crowley pdc@dcs.ed.ac.uk \  /
  33. /\__/ "I'm the boy without a soul"   \/
  34.