Testing word-sized numbers for primality
A. C. Norman · ACM SIGSAM Bulletin · 1979
Modular based algorithms, such as those used to compute GCDs, generally require a supply of word-sized primes. Such primes can, of course, be provided statically: it is easy to precompute and store a list of a dozen or so suitable numbers. It nevertheless seems attractive to generate them randomly, for instance by considering a sequence of random numbers until one of them is found to be prime. This strategy leads to a consideration of the cost of testing if a number is composite. This cost clearly depends on the typical size of numbers being used. For use with the arithmetic package I have, it is convenient to use a modulus in the range 2**23 to 2**24, and so the remarks and timings given here are relevant to that range.