home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15257 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  2.2 KB
  1. Path: sparky!uunet!wupost!uwm.edu!biosci!agate!linus!linus.mitre.org!gauss!bs
  2. From: bs@gauss.mitre.org (Robert D. Silverman)
  3. Newsgroups: sci.math
  4. Subject: Re: Prime test algorithm
  5. Message-ID: <1992Nov18.204334.12453@linus.mitre.org>
  6. Date: 18 Nov 92 20:43:34 GMT
  7. References: <1992Nov14.154528.17440@husc15.harvard.edu>
  8. Sender: news@linus.mitre.org (News Service)
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. Lines: 42
  11. Nntp-Posting-Host: gauss.mitre.org
  12.  
  13. In article <1992Nov14.154528.17440@husc15.harvard.edu> blom@husc15.harvard.edu writes:
  14. >Does anyone have C source code for an algorithm to determine whether an
  15. >enormous number (over 1000 decimal digits) is prime or composite?  I have
  16. >Derive and Mathematica for my 486, but they run slowly on some of my large
  17. >prime-test problems (546!-1) and I would like to be able to use my VAXstation
  18. >4000-90.  I think I may also be able to compile Fortran, and maybe Pascal.  I
  19. >have the best luck with C programs because they are so portable.
  20. >
  21. >Thanks in advance.
  22. >--Eric Blom
  23. >  Harvard
  24.  
  25. You are not going to be able to prove 1000+ digit *general* numbers prime on a
  26. single workstation in a reasonable time, regardless of whether you
  27. use the Goldwass-Killian-Atkin-Morain elliptic curve method, or the
  28. Cohen-Lenstra-Bosma cyclotomic ring method. 
  29.  
  30. Do you really need prime proofs? Are you willing to settle for probable
  31. primes? If you are testing n!+1  or n!-1, once you know it is a prp,
  32. proving it prime is trivial, because N-1 or N+1 factors readily. In the
  33. first case you can find a primitive root. In the second, a Lucas-Lehmer
  34. test will suffice.
  35.  
  36. Others have already looked at when n!-1,  n!+1,  n#+1, n#-1 are prime.
  37. [n# = product of distinct primes up to n]  Have you checked the
  38. literature?
  39.  
  40. See, for example, 
  41.  
  42. Buhler, Crandall, & Penk
  43. Primes of the form n!+/- 1  and 2*3*5...p +/- 1
  44.  
  45. Mathematics of Computation vol. 38, 1982 pp 639-645
  46.  
  47. Be aware that the computations have been carried much further
  48. than given in that article by H. Dubner (and others).
  49.  
  50. --
  51. Bob Silverman
  52. These are my opinions and not MITRE's.
  53. Mitre Corporation, Bedford, MA 01730
  54. "You can lead a horse's ass to knowledge, but you can't make him think"
  55.