Pseudoprime

Author

Eric W. Weisstein
November 17, 2005

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

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

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

Code

StrongPseudoprimeQ[a_,n_Integer?EvenQ]:=False
StrongPseudoprimeQ[a_,n_Integer?PrimeQ]:=False
StrongPseudoprimeQ[a_,n_Integer]:=Module[{d=OddPart[n-1],s=IntegerExponent[n-1,2],r},
PowerMod[a,d,n]==1||Or@@Table[PowerMod[a,d 2^r,n]==n-1,{r,0,s-1}]
]

GuyStrongPseudoprimeQ[a_,n_Integer?EvenQ]:=False
GuyStrongPseudoprimeQ[a_,n_Integer?PrimeQ]:=False
GuyStrongPseudoprimeQ[a_,n_Integer]:=Module[{d=OddPart[n-1],s=IntegerExponent[n-1,2],r},PowerMod[a,d,n]==1
]

Counts

Fermat Pseudoprimes

(psp2=Select[Flatten[Position[Table[PowerMod[2,n-1,n],{n,10^8}],1]],!PrimeQ[#]&]);//Timing

Table[Count[psp2,_?(#<10^n&)],{n,6}]

Strong Pseudoprimes

Select[Range[2,10^4],StrongPseudoprimeQ[2,#]&]

spsp=Select[Range[2,10^5],StrongPseudoprimeQ[2,#]&]

Table[Count[spsp,_?(#≤10^n&)],{n,5}]

pseudop=Transpose@{{0,0,0,0},{0,0,0,0},{3,1,0,1},{22,12,5,7},{78,36,16,16},{245,114,46,43},{750,375,162,105},{2057,1071,488,255},{5597,2939,1282,646},{14884,7706,3291,1547},{38975,20417,8607,3605},{101629,53332,22407,8241},{264239,124882,58897,19279}};

spsp=Select[Range[2,10^5],StrongPseudoprimeQ[2,#]&]

Table[Count[spsp,_?(#≤10^n&)],{n,5}]

guyspsp=Select[Range[2,10^5],GuyStrongPseudoprimeQ[2,#]&]