home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / alt / hackers / 1341 < prev    next >
Encoding:
Text File  |  1992-08-31  |  2.6 KB  |  75 lines
  1. Newsgroups: alt.hackers
  2. Path: sparky!uunet!think.com!spdcc!das-news.harvard.edu!cantaloupe.srv.cs.cmu.edu!bsy
  3. From: bsy+@cs.cmu.edu (Bennet Yee)
  4. Subject: Re: Prime Number Generator
  5. Message-ID: <Btv3L1.4oC.2@cs.cmu.edu>
  6. Sender: news@cs.cmu.edu (Usenet News System)
  7. Nntp-Posting-Host: play.trust.cs.cmu.edu
  8. Organization: Cranberry Melon, School of Cucumber Science
  9. References: <grtyj5-@rpi.edu> <1992Aug31.160225.26724@gateway.novell.com>
  10. Date: Mon, 31 Aug 1992 19:02:59 GMT
  11. Approved: bsy@play
  12. Lines: 61
  13.  
  14. In article <1992Aug31.160225.26724@gateway.novell.com> alex@otis (The Console DJ) writes:
  15. >In article <grtyj5-@rpi.edu> cleggp@aix.rpi.edu (Paul Jason Clegg) writes:
  16. >>I'm interested in generating large prime numbers for use in some public key
  17. >>code encryption schemes, and I'm looking for the fastest way to generate all
  18. >>the primes from 2 up to as high as I can go on my 386/25 (Using BC++ 3.1, I
  19. >
  20. >Someone correct me if I am wrong but the whole idea behind the encryption is
  21. >the large prime numbers are difficult to  calulate??? Actually there should
  22. >be no known algorithm (except brute force try every number thingy).
  23.  
  24. There are polynomial time algorithms for testing primality assuming
  25. Generalized Reimann Hypothesis (GRH).  W/o assuming GRH, there are
  26. probabilistic polynomial time algorithms (one-sided error, i.e., in R)
  27. for testing primality.  It is easy to test the primality of numbers
  28. that have hundreds or even thousands of decimal digits.  This, of
  29. course, is feasible on 386's.
  30.  
  31. Note that the seive is exponential time, since you are creating a
  32. table that is exponential in size on the _size_ of the number that you
  33. want to test (size measured in number of bits required to represent
  34. it).
  35.  
  36. *Factoring* is what's hard.  Or so number theorists believe.
  37.  
  38. These sort of questions are more appropriately posted to sci.crypt.
  39.  
  40. No ObHack.
  41.  
  42. -bsy
  43.  
  44.  
  45. @article(MillerPrime,
  46.     Key="Miller",
  47.     Author="G. L. Miller",
  48.     Title="Riemann's Hypothesis and a Test for Primality",
  49.     Year=1976,
  50.     Volume=13,
  51.     Journal="Journal of Computing and Systems Science",
  52.     Pages="300--317")
  53.  
  54. @article(SolovayStrassen,
  55.     Key="Solovay and Strassen",
  56.     Author="R. Solovay and V. Strassen",
  57.     Title="A Fast {Monte-Carlo} Test for Primality",
  58.     Month="March",
  59.     Year=1977,
  60.     Volume=6,
  61.     Journal="SIAM Journal on Computing",
  62.     Pages="84--85")
  63.  
  64. @article(RabinPrime,
  65.     Key="Rabin",
  66.     Author="Michael O. Rabin",
  67.     Title="Probabilistic Algorithm for Testing Primality",
  68.     Year=1980,
  69.     Volume=12,
  70.     Journal="Journal of Number Theory",
  71.     Pages="128--138")
  72. -- 
  73. Bennet S. Yee        Phone: +1 412 268-7571        Email: bsy+@cs.cmu.edu
  74. School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890
  75.