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