Miller Rabin Primality Testing

In the course of developing C code to run a Miller Rabin primality test, I came across two variants of the test. Most web sites describe the same test, but Wikipedia includes an additional test, essentially identifying a square root of 1 (mod n) that is not equal to $\pm 1 \,\,(mod \,\,n)$ .

I ran a few experiments how useful this variant was in practice, concluding that the additional test is of no practical benefit.

Main test

From Fermat’s Little Theorem, a necessary condition for n to be prime is that

$a^{n-1}=1 \,(mod\,\, n)\,\, for\, 1\le a \lt n$                            (1)

Miller Rabin tests an odd number, n, for primality by expressing n-1 = 2^sd, where d is odd, (so s>0), and then, for several “witnesses”, a, $(2 \le a \lt n )$ testing the values of the sequence

$a^d,\,a^{2d},\,\dots,a^{2^{s-1}d}$ (all modulo n)                                 (2)

If

$a^d=±1 \,(mod\,\, n)\,\, or \,\,a^{2^k d}=-1\, (mod\,\, n) \,\,(1 \le k \lt s)$         (3)

then $a^{2^s d}=a^{n-1}=1 \,\,(mod \,\, n)$ If (3) is not encountered, then n is composite. If (3) is encountered for all the witnesses tested, then n is “probably prime”.

Additional test

The Wikipedia article on Miller Rabin includes an additional test on sequence (2), testing for 

 $a^{2^k d}=+1\,\, (mod\,\, n) \,\,\,(1 \le k \lt s)$             (4)

If this situation occurs in the sequence before (3) is encountered, then n is a composite. Wikipedia explains this by saying that n divides $(a^{2^{k-1} d}-1)(a^{2^{k-1} d}+1)$ but not each term, and is therefore composite. 

Another explanation is that encountering condition (4) before (3) implies that there is a square root of 1 that is not equal to $\pm 1$, hence n cannot be prime.

Is the additional test useful?

Is test (4) of any practical benefit? In order to find out, I performed a trial to see how many times early detection of composites was actually encountered in practice. Source code can be found here.

The following table shows several runs of a deterministic Miller Rabin test, each run testing 1,000,000 random odd numbers uniformly distributed between 1 and 10ⁿ. Pink columns show the results for a “pure” algorithm, where all odd numbers are subjected to tests (3) and (4). The tests show that a small proportion of composites are detected using (4), predominantly below 10⁸.

The “hybrid” algorithm uses trial division to test primality for numbers below 9,080,191 (to avoid the need for the deterministic Miller Rabin test for witnesses 31 and 73) and also uses trial division to eliminate multiples of small primes below 100. If the trial division tests have not determined the primality of the number, Miller Rabin tests are then used. Green columns show the results for this hybrid algorithm.

			Pure Miller Rabin			Hybrid
Limit	Number of primes	Number of composites	Composites detected early	% composites detected early	Time taken (s)	Composites detected early	Time taken (s)
102	479,844	520,156	0	0.0%	0.3	0	0.2
103	334,223	665,777	4,056	0.6%	0.4	0	0.2
104	246,488	753,512	1,759	0.2%	0.7	0	0.2
105	191,283	808,717	632	0.1%	0.8	0	0.4
106	157,215	842,785	208	0.0%	1.0	0	0.7
107	132,585	867,415	44	0.0%	1.1	1	1.7
108	115,154	884,846	23	0.0%	1.4	7	1.8
109	101,831	898,169	2	0.0%	1.5	1	1.8
1010	91,394	908,606	1	0.0%	16.8	0	9.2
1011	82,251	917,749	0	0.0%	26.5	0	15.2
1012	74,980	925,020	0	0.0%	38.4	0	16.2
1013	68,926	931,074	0	0.0%	69.9	0	15.3
1014	64,327	935,673	0	0.0%	56.5	0	18.3
1015	59,752	940,248	0	0.0%	96.3	0	16.6
1016	55,732	944,268	0	0.0%	83.1	0	18.6
1017	52,473	947,527	0	0.0%	76.8	0	20.8
1018	49,637	950,363	0	0.0%	106.2	0	23.1
1019	45,300	954,700	0	0.0%	125.3	0	24.5

Table 1, Primality testing for 1,000,000 random odd numbers up to specified limit

 Conclusions

Even for a pure Miller Rabin test, the additional test (4) only identifies a very small proportion of composites, mostly below 10⁸. Using a hybrid approach of trial division and Miller Rabin testing, the proportion of composites found by test (4) becomes negligible. 

As primality testing by trial division is faster than Miller Rabin for numbers below 10⁸, test (4) provides no practical benefit.