From: pm@news.univie.ac.at (Peter Marksteiner)
Newsgroups: sci.math
Subject: Re: Need the Rabin strong pseodoprime test
Date: 23 Feb 1996 09:31:37 GMT
Kevin Nordt (kgn7e@fulton.seas.Virginia.EDU) wrote:
: I'm looking for the quickest way to determine whether an integer n is
: prime. I know that Mathematica uses the Rabin string pseudoprime test
: and the Lucas test for its built in "PrimeQ" function. This seems to be
: fast enough for my application but I can not locate any description of
: these tests in my algorithms books.
[...]
: I'll be dealing with numbers on the order of 10^6 and speed is key. If
: anyone can point me in a more enlightening direction, I'd be most
: grateful. Also if these tests are not the fastest way for primality
: testing on integers of the order I stated earlier please feel free to
: educate me on the subject (meaningful texts and/or papers on this subject
: would always be of help).
If your numbers are not much larger than 10^6 you can probably afford to
generate a table of prime numbers by the sieve of Erathostenes and keep
it in memory; primality testing by table lookup is definitely the fastest.
Otherwise check Richard Pinch's home page
http://www.dpmms.cam.ac.uk/home/emu/rgep/ where you can find a paper
"Some primality testing algorithms".
--
Peter Marksteiner e-mail: Peter.Marksteiner@univie.ac.at
Vienna University Computer Center Tel: (+43 1) 406 58 22 255