home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / programm / 3635 < prev    next >
Encoding:
Internet Message Format  |  1993-01-28  |  979 b 
  1. Path: sparky!uunet!ukma!gatech!concert!duke!news.duke.edu!quirky.phy.duke.edu
  2. From: phusek@quirky.phy.duke.edu (Paul Husek)
  3. Newsgroups: comp.programming
  4. Subject: Re:how about Prime Numbers?
  5. Message-ID: <9201@news.duke.edu>
  6. Date: 28 Jan 93 16:55:13 GMT
  7. Sender: news@news.duke.edu
  8. Lines: 14
  9. Nntp-Posting-Host: quirky.phy.duke.edu
  10.  
  11.  
  12. I thought the way they came up with large prime numbers was to perform a  
  13. test on them which had a 1/x probability of revealing a prime number if it  
  14. were prime, where x is of the order of 2.  If you perform this test (with  
  15. varying parameters) n times then you have a 1/x^n chance of mistaking a  
  16. nonprime number for a prime.  Do it 100 times and your pretty damn certain  
  17. if it passes all these tests its prime.
  18.  
  19.     I think Corman, Rivest, etc in Intro to Algorithms has a  
  20. discussion on this.
  21. --
  22.     Paul Husek                 1-919-383-3535                             
  23.     Duke University Dept. of Physics    phusek@phy.duke.edu    
  24.     Durham, N.C.      27706            
  25.