home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4850 < prev    next >
Encoding:
Internet Message Format  |  1992-11-17  |  1.3 KB
  1. Xref: sparky sci.crypt:4850 sci.math:15024 comp.theory:2431
  2. Path: sparky!uunet!van-bc!cs.ubc.ca!unixg.ubc.ca!ramsay
  3. From: ramsay@math.ubc.ca (Keith Ramsay)
  4. Newsgroups: sci.crypt,sci.math,comp.theory
  5. Subject: Re: Cryptography and P=NP
  6. Date: 16 Nov 1992 06:43:57 GMT
  7. Organization: University of British Columbia, Vancouver, B.C., Canada
  8. Lines: 16
  9. Distribution: inet
  10. Message-ID: <1e7fvdINN87s@iskut.ucs.ubc.ca>
  11. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <PHR.92Nov15203840@napa.telebit.com>
  12. NNTP-Posting-Host: riemann.math.ubc.ca
  13.  
  14. In article <PHR.92Nov15203840@napa.telebit.com> phr@telebit.com 
  15. (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. Mathematics would also be placed in a surprising position by P=NP.
  22. P=NP implies that there is an algorithm which, given a theorem
  23. expressed formally in ZF, say, and a number n, either gives a formal
  24. proof of the theorem of length at most n, or shows that there is none,
  25. and which would take time bounded by some polynomial in n. It wouldn't
  26. *necessarily* put us all out of the math research business, but....
  27.  
  28. Keith Ramsay
  29. ramsay@unixg.ubc.ca
  30.