TESTING PRIMES TO NINE QUADRILLION
Known Composites, Unknown Factors
Two properties are common to all prime numbers p and positive integers a < p. First is the fact that ap−1 % p = 1, which is refered to as the Fermat's little theorem (FLT). The second, if a2 % p = 1, then either a % p = p−1 or a % p = 1. So, suppose we know that 1234 % 35 = 9, instead of 1. Then we may conclude that 35 is composite, with or without the knowledge that 35 = 5 × 7. If that were not enough, another evidence that 35 cannot possibly be a prime is the truth that 62 % 35 = 1, where 6 is neither 1 nor 35−1.
Now given a large odd integer N, we compute the odd number d for which (N−1) ÷ d = 2e and then look at the following sequence of e+1 numbers,
ad, a2d, a22d, a23d, … , a2ed = aN−1
all reduced % N. Note that each term is succeeded by its square. Hence if we spot a 1 that is preceded by neither 1 nor N−1, then N is composite. Or, if the last number is not 1, then N is composite by FLT. This algorithm is what we call the Miller-Rabin test (MRT).
The bad news is MRT seems to catch only "some" composites, i.e., those which fail the test. The good news is, the composites that do pass MRT are quite rare. Moreover, why not we run the test with different values of a, further reducing the number of composites which possibly survive the multiple bases. And if these few so-called "strong pseudoprimes" have been predetermined within a given interval, then MRT becomes an absolute primality test.
Note that we are not concerned with finding the factors of a composite N. See our trial division page if you are looking for a factoring algorithm.
We initially check if N is divisible a small prime below 100 before we proceed with MRT. Then N is subjected to four rounds of MRT where the bases are chosen to be 2, 3, 5, and 7. If to any base N is recognized to be a composite, we immediately terminate the algorithm. Otherwise, N is either a prime or a strong pseudoprime.
Feel free to save or modify a copy of this file for your own use.
Do Not Repeat These Mistakes
Also, modular exponentiation is typically performed via successive squaring in order to keep the intermediate outputs smaller than N. Even so, when N > 226.5 squaring a number may violate the 53-bit limit. In such a case we resort to long-multiplication by the right-to-left binary digits. In other words, successive squaring will have to be downgraded to successive doubling! A similar caution applies to large modular addition.
It is possible to scan an array contents, such as the pseudoprimes we store, using the indexOf function, which returns the index of an element or −1 otherwise. We discovered that indexOf was originally written for string variables but was only recently extended to arrays. Beware that older browsers may not support this new feature unless we insert the extension subroutine. But again, all we really need is to know the existence, not the index.
Copyright © 20112022 Amin Witno
This page belongs to the personal folder of Amin Witno and does not necessarily represent the philosophy and values of Philadelphia University or the Department of Basic Sciences in particular.