home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15356 < prev    next >
Encoding:
Text File  |  1992-11-21  |  1.9 KB  |  38 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  3. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  4. Subject: Re: RSA Encryption
  5. Message-ID: <1992Nov22.011016.6268@CSD-NewsHost.Stanford.EDU>
  6. Keywords: cryptography, primes
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: Computer Science Department,  Stanford University.
  9. References: <avatarp.722363576@well.sf.ca.us>
  10. Date: Sun, 22 Nov 1992 01:10:16 GMT
  11. Lines: 25
  12.  
  13. In article <avatarp.722363576@well.sf.ca.us> avatarp@well.sf.ca.us (Peter Rothman) writes:
  14. >Originally, I had supposed that algorithm would perform poorly on this  data
  15. >set, but in fact we found that we were able to predict the digits of prime
  16. >numbers with a success rate much greater than chance.  Although this work
  17. >was not taken any  further, I suspect that similar techniques could be used
  18. >to develop statistical algorithms which could make RSA useless.
  19.  
  20. If RSA depended on primality testing being hard it would have been
  21. still-born.  If you are presented with a 1000-digit composite, the
  22. Miller-Rabin or Strassen-Solovay testers can be arranged to *guarantee*
  23. to find you a proof of its compositenes, in a random time whose mean is
  24. a few minutes and whose tail vanishes exponentially.  Finding a
  25. *factor* of that composite however can keep you occupied for
  26. centuries with present algorithms and computers.
  27.  
  28. Apropos of which, here is my proof that P=NP.  (I came up with it
  29. around 1972, if you have an earlier source then it's not mine after
  30. all.)  Computers double in speed every 18 months or so, whence any
  31. exponential time problem can be solved in linear time by waiting the
  32. requisite number of months for the problem to become solvable in one
  33. month and then starting the computation.  This counts the waiting time,
  34. and has the additional advantage that you can use your computer on
  35. something else while waiting.
  36. -- 
  37. Vaughan Pratt              A fallacy is worth a thousand steps.
  38.