home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / alt / hackers / 1337 < prev    next >
Encoding:
Text File  |  1992-08-31  |  1.7 KB  |  42 lines
  1. Newsgroups: alt.hackers
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!menudo.uh.edu!nuchat!taronga!peter
  3. From: peter@taronga.com (Peter da Silva)
  4. Subject: Re: Prime Number Generator
  5. Message-ID: <46UIP4L@taronga.com>
  6. Organization: Taronga Park BBS
  7. References: <grtyj5-@rpi.edu>
  8. Date: Mon, 31 Aug 1992 11:03:15 GMT
  9. Approved: you could have looked all this up in your local library
  10. Lines: 30
  11.  
  12. In article <grtyj5-@rpi.edu> cleggp@aix.rpi.edu (Paul Jason Clegg) writes:
  13. >I'm interested in generating large prime numbers for use in some public key
  14. >code encryption schemes, and I'm looking for the fastest way to generate all
  15. >the primes from 2 up to as high as I can go on my 386/25 (Using BC++ 3.1, I
  16. >figured this is somewhere in the what, 4 billion range?)
  17.  
  18. 1. These are unlikely to be large enough.
  19. 2. Try the Seive of Eratosthenes. That's the greek dude you're thinking of.
  20.    You only need to test the *primes* up to the square root of the number
  21.    in question, and since you're generating all the primes you already
  22.    *know* them all. Just use the standard seive up to 64K (no sweat) and
  23.    use the primes in this array to test the rest of the number space.
  24.  
  25.    There is code for the seive all over the place, since Byte used it as a
  26.    numerical benchmark for many years.
  27.  
  28. >But.  Does anyone know of even more efficient algorithm for determining the
  29. >primeness of numbers?
  30.  
  31. See above.
  32.  
  33. >Has anyone ever come up with a O(n) algorithm for it?
  34.  
  35. If anyone does, there won't be any point in using primes for cryptosystems
  36. any more.
  37. -- 
  38.                                                                 `-_-'
  39.                          Have you hugged your wolf today?        'U`
  40.  
  41. Peter da Silva, Taronga Park BBS, Houston, TX  +1 713 568 0480/1032
  42.