Euler Pseudoprime

Author

Eric W. Weisstein
July 8, 2008

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

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

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

Enumeration

Eric

Length[l1=With[{n=10^5,a=2},Select[Range[3,n,2],!PrimeQ[#]&&!Unequal[PowerMod[a,(#-1)/2,#],1,#-1]&]]]//Timing

Length[l1=With[{n=10^6,a=2},Select[Range[3,n,2],!PrimeQ[#]&&!Unequal[PowerMod[a,(#-1)/2,#],1,#-1]&]]]//Timing

Maxim

EulerPseudoprimes[a_,n_]:=Module[{L=Range[3,n,2]},L=Pick[L,Thread[Thread[!PrimeQ[L]]&&OddQ[L]&&CoprimeQ[a,L]]];
Pick[L,Abs[Mod[PowerMod[a,Quotient[L-1,2],L],L,-1]],1]]

Length[l2=EulerPseudoprimes[2,10^5]]//Timing

l1==l2

Length[l=EulerPseudoprimes[2,10^6]]//Timing

l