home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / crypt / 4846 < prev    next >
Encoding:
Internet Message Format  |  1992-11-15  |  1.3 KB
  1. Xref: sparky sci.crypt:4846 sci.math:15022 comp.theory:2429
  2. Newsgroups: sci.crypt,sci.math,comp.theory
  3. Path: sparky!uunet!telebit!phr
  4. From: phr@telebit.com (Paul Rubin)
  5. Subject: Re: Cryptography and P=NP
  6. In-Reply-To: unruh@physics.ubc.ca's message of 16 Nov 1992 04:52:56 GMT
  7. Message-ID: <PHR.92Nov15215202@napa.telebit.com>
  8. Sender: news@telebit.com
  9. Nntp-Posting-Host: napa.telebit.com
  10. Organization: Telebit Corporation; Sunnyvale, CA, USA
  11. References: <1992Nov15.110945.19939@ringer.cs.utsa.edu> <1e79f8INN80o@iskut.ucs.ubc.ca>
  12. Date: 15 Nov 92 21:52:02
  13. Lines: 16
  14.  
  15. Factoring is in both NP and co-NP; unless there's been some stunning
  16. recent developments, nobody knows if factoring is NP-hard.  So
  17. even if P!=NP, factoring might be in P.  Most theorists think
  18. P!=NP, but some very sharp mathematicians think factoring is in P.
  19. I don't understand the nature of the evidence.  But RSA might
  20. indeed be in worse trouble than cryptography in general.
  21.  
  22. On the other hand, I've heard that serious crypto spooks mostly
  23. laugh at all public key systems, other than RSA with very large
  24. keys (500 digit primes and 1000 digit modulus--that's -decimal- digits).
  25. Crypto schemes based on NPC problems have been broken.
  26.  
  27.     Remember that polynomial could be x^(10^10), in which case we still
  28.     don't have much to worry about.
  29.  
  30. Depends on the model of computation that you use.
  31.