home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / math / 15330 < prev    next >
Encoding:
Text File  |  1992-11-20  |  2.2 KB  |  55 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!think.com!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: Prime test algorithm
  5. Message-ID: <1992Nov19.170217.9466@linus.mitre.org>
  6. Sender: news@linus.mitre.org (News Service)
  7. Nntp-Posting-Host: gauss.mitre.org
  8. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  9. References: <1992Nov14.154528.17440@husc15.harvard.edu> <BxuIp4.3ss@iat.holonet.net>
  10. Date: Thu, 19 Nov 1992 17:02:17 GMT
  11. Lines: 42
  12.  
  13. In article <BxuIp4.3ss@iat.holonet.net> rkinder@iat.holonet.net (Robert J. Kinder) writes:
  14. :blom@husc15.harvard.edu writes:
  15. :: Does anyone have C source code for an algorithm to determine whether an
  16. :: enormous number (over 1000 decimal digits) is prime or composite?  I have
  17. :: Derive and Mathematica for my 486, but they run slowly on some of my large
  18. :: prime-test problems (546!-1) and I would like to be able to use my VAXstation
  19. :: 4000-90.  I think I may also be able to compile Fortran, and maybe Pascal.  I
  20. :: have the best luck with C programs because they are so portable.
  21. :: 
  22. :: Thanks in advance.
  23. :: --Eric Blom
  24. ::   Harvard
  25. :
  26. :The best package seems to be Arjen Lenstra's arbitrary precision
  27. :arithmethic package written in C, based on what I've read.
  28. :
  29.  
  30. Actually, no. Arjen's package (unless he has improved it) works in 15
  31. bit arithmetic as the RADIX. There are faster packages. PARI, Dik Winter's
  32. package, mine, Peter Montgomery's are all faster than the version I have
  33. of Arjen's code. (But they are less portable, having assembler code)
  34.  
  35. This is NOT to denigrate Arjen's code. It was written with portability, not 
  36. speed, in mind.
  37.  
  38.  
  39. :BigNum directory.  The file should be about 91KB in size.  This package
  40. :has -, +, *, /, mod, primality testing, and exponentiation plus other
  41.               ^^^^^^^^^^^^^^^^^^  
  42.  
  43. You mean "probable prime testing". The code doesn't actually do primality
  44. PROOFS. 
  45.  
  46. If you really want proofs, it is best to write to Francois Morain, or
  47. Wieb Bosma and ask them for their code.
  48.  
  49. I will send my MPP code to anyone who writes *personally* and asks for it.
  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.