Miller's Primary Test

Author

Eric W. Weisstein
February 7, 2009

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/MillersPrimalityTest.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/MillersPrimalityTest.html.

©2009 Wolfram Research, Inc. except for portions noted otherwise

Code

StrongPseudoprimeQ[a_,n_Integer]:=Module[{s,d},
n>2&&Mod[n,2]==1&&!PrimeQ[n]&&(PowerMod[a,d=(n-1)/2^(s=IntegerExponent[n-1,2]),n]==1||If[s==1,PowerMod[a,d,n]==n-1,(PowerMod[a,d #,n]==n-1)&/@(Or@@(2^Range[0,s-1]))
]
)
]

Small Examples

http://www.research.att.com/~njas/sequences/A074773

3215031751, 118670087467, 307768373641, 315962312077, 354864744877, 457453568161, 528929554561, 546348519181, 602248359169

Select[Range[10^8],Function[a,StrongPseudoprimeQ[a,#]]/@(And@@{2,3,5,7})&]//Timing

Select[Range[10^9],Function[a,StrongPseudoprimeQ[a,#]]/@(And@@{2,3,5,7})&]//Timing

With[{p=118670087467},{PrimeQ[p],StrongPseudoprimeQ[#,p]&/@{2,3,5,7}}]

With[{p=3215031751},{PrimeQ[p],StrongPseudoprimeQ[#,p]&/@{2,3,5,7}}]