home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / crypt / 3713 < prev    next >
Encoding:
Text File  |  1992-10-11  |  1.7 KB  |  40 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!math.fu-berlin.de!unidui!rrz.uni-koeln.de!Germany.EU.net!mcsun!fuug!funic!news.cs.hut.fi!cs.hut.fi!Ari.Huttunen
  3. From: Ari.Huttunen@hut.fi (Ari Huttunen)
  4. Subject: Re: Prime generation, a possible weakness in PGP?
  5. In-Reply-To: ahaley@eo17's message of Fri, 9 Oct 1992 16:01:50 GMT
  6. Message-ID: <ARI.HUTTUNEN.92Oct11211134@cardhu.cs.hut.fi>
  7. Lines: 25
  8. Sender: usenet@cs.hut.fi (Uutis Ankka)
  9. Organization: Helsinki University of Technology, Finland
  10. References: <ARI.HUTTUNEN.92Sep27174550@laphroaig.cs.hut.fi>
  11.     <1992Oct9.160150.13377@eoc.com>
  12. Distribution: alt
  13. Date: Sun, 11 Oct 1992 19:11:37 GMT
  14.  
  15. In article <1992Oct9.160150.13377@eoc.com> ahaley@eo17 (Andrew Haley) writes:
  16.  
  17. ! Large pseudoprimes (of any base) are very rare indeed. 
  18.  
  19. Are pseudoprimes to base X, where X is large more rare than
  20. pseudoprimes to base Y, where Y is small.
  21.  
  22. ! wrong.)  In any case, it is likely that a composite p or q would cause
  23. ! messages to not decrypt correctly, a fact that you'd soon notice.
  24.  
  25. Perhaps, but I wouldn't bet on it, unless I got some proof.
  26.  
  27. ! It might be worth using the Miller-Rabin test, in which no analogues
  28. ! of Carmichael numbers exist, as a backup.  This would be easy to add
  29. ! to the search procedure, but I don't think that it's really necessary.
  30.  
  31. I have some code that does exactly that (uses the Miller test). The 
  32. reason I became worried was that Kenneth Rosen incorrectly states
  33. in his book that "If n is composite the probability that n passes
  34. all k tests is less than (1/4)^k." This is incorrect as was pointed out.
  35. --
  36. ...............................................................................
  37. Ari Huttunen                      Any similarity to other alien life forms
  38.                           is purely coincidental.
  39.                           <Alien 3 misquote>
  40.