Euler-Jacobi Pseudoprime

Author

Eric W. Weisstein
July 8, 2008

This notebook downloaded from http://mathworld.wolfram.com/notebooks/NumberTheory/Euler-JacobiPseudoprime.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Euler-JacobiPseudoprime.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],CoprimeQ[a,#]&&!PrimeQ[#]&& Mod[PowerMod[a,(#-1)/2,#]-JacobiSymbol[a,#],#]==0&]]]//Timing

Maxim

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

l1

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

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

l1==l2

l1

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

l