Pseudoprimes
Roland Engdahl
University of Kalmar
Sweden
mr.engdahl@telia.com
Introduction
In order to prove primality of a number, previously we required a list of primes. Eratosthenes, about 230 B.C., created his famous sieve, The Sieve of Eratosthenes. Nowadays we have methods to perform sieve and store a table of primes on a computer system.
Fermat, 1640 , described one characteristic of primes in his famous theorem. The converse of this theorem is however not true. There are composite numbers which comply with this characteristic These numbers are called pseudoprimes.
This application provides examples and programs about primes, pseudoprimes, Carmichael numbers, strong pseudoprimes and primality testing. Only definitions of the concepts are included.
Proofs and deeper studies in the theory are to be found in books on number theory e g Kumanduri and Romero, Number theory with computer applications.
A new paradigm in mathematics is experimenting. Consult these sources: Borwein and Bailey and Girgensohn, (vol 1) Mathematics by Experiment, Plausible Reasoning in the 21 st Century, 2004. (vol 2) Experimentation in Mathematics, Computational Paths to Discovery, 2004.
Perhaps experiments with these programs will increase the esteem of number theory.
Fermat's Theorem
If p is prime then 
Example
5 is a prime. Divide 
To calculate 
a&^b mod n calculates 
Example in Maple
97 is a prime Calculate 
Solution
Issue 341
Calculate 
Solution
Comments
From the example above we see that the conversion of Fermat's theorem is false.
341 has a characteristic for a prime but is composite
341 is called a pseudoprime to base 2
Definition of pseudoprime and Maple example
A composite number n is called a pseudoprime to base a if 
Example
| > |
restart: a:=2:lim:=1000:
the program calculates all pseudoprimes less than lim to base a
for n from 5 by 2 to lim do
if
a&^(n-1) mod n = 1 and isprime(n)=false
satisfies Fermat's theorem and 'isprime(n)=false' means primes excluded
then print(n);
end if;
end do; |
Compare the number of primes and the number of pseudoprimes to a given base
Program
| > |
restart:
the program calculates the number of primes and pseudoprimes between limits to a given base
stt:=10000:stp:=30000:a:=2:
choose start >2 stt and stop stp and base a |
| > |
ps:=0:pr:=0:if type(stt,even) then stt:=stt+1: end if:
start with odd number
for n from stt by 2 to stp do
if isprime(n)=true then pr:=pr+1: end if:
counts the number of primes
if isprime(n)=false and a&^(n-1) mod n=1 then ps:=ps+1:
counts only the pseudoprimes
end if:
end do:
print("number of primes=",pr);print("number of pseudoprimes to base " ,a," = ",ps); |
Comments
The test shows that pseudoprimes are rather common.
It is not a very good idea to use pseudoprimes for primality testing
Issue 561
Program for examination of bases for which 561 is a pseudoprime
| > |
restart:
n:=561: testbase:=[2,3,5,7,9,11,13,15,17,19,21,23]:psp:="n psp base %a ":
testing n=561 as pseudoprime in bases of testbase |
| > |
m:=n-1:
for a in testbase do
if (a&^m mod n =1) then
printf(psp,a):
end if:
end do; |
n psp base 2 n psp base 5 n psp base 7 n psp base 13 n psp base 19 n psp base 23
Result from the examination
561 is a pseudoprime to all bases a with (561,a)=1
561=3·11·17. Therefore the numbers 3,9,11,15,17,21 are excluded from the bases
561 is an example of Carmichael number: See next section
Carmichael numbers
Definition
A composite number n is called a Carmichael number if
Theorem
A composite number n is a Carmichael number if and only if for every prime divisor p to n we have p-1 is divisor to n-1
Programs to calculate Carmichael numbers
Program with 3 factors
| > |
restart:p[1]:=2: i:=1: e:=200:
choose the highest prime factor < e
for k from 3 by 2 to e do
if isprime(k) then i:=i+1: p[i]:=k end if;
end do: |
| > |
for r from 3 to i do
for s from 2 to r-1 do
for t from 1 to s-1 do
n:=p[r]*p[s]*p[t]: m:=n-1:
for i=r,s,t we have: p[i]-1 is divisor to m=n-1
if (m mod (p[r]-1) =0) and (m mod (p[s]-1) =0) and (m mod (p[t]-1) =0) then
print(p[t],p[s],p[r] ,n):
end if:
end do : end do: end do:
PLEASE WAIT UNTIL READY |
Program with 4 factors
| > |
restart:p[1]:=2: i:=1: e:=62:
for k from 3 by 2 to e do
calculates the primes < e
if isprime(k) then i:=i+1: p[i]:=k end if;
end do: |
| > |
for u from 4 to i do
for r from 3 to u-1 do
for s from 2 to r-1 do
for t from 1 to s-1 do
n:=p[r]*p[s]*p[t]*p[u]: m:=n-1:
for k=t,s,r,u p[k]-1 divisor to m=n-1
if (m mod (p[r]-1) =0) and (m mod (p[s]-1) =0)
and (m mod (p[t]-1) =0)
and (m mod (p[u]-1)=0) then
print(p[t],p[s],p[r],p[u]," = ",n):
end if:
end do : end do: end do:end do:
PLEASE WAIT UNTIL READY |
Strong pseudoprimes
Definition
Given an odd composite integer n with n - 1 = q·
n is a strong pseudorprime to base a if
= 1 mod n or
Strong pseudoprimes are introduced to get a better tool for identifying probable primes
Applications strong pseudoprimes
Testing strong pseudoprimes to different bases
| > |
restart: n:=12403: a:=3: |
try numbers n 314821 873181 76491 597871 112141 87913 12403
try bases a 2 3 5 7 11 13
| > |
spsp:=false:m:=n-1:q:=m:r:=0:
writing m=n-1 as m=q*
while type(q,even) do
q:=iquo(q,2):r:=r+1:
end do:
e:=a&^q mod n:
testing if 
if e=1 then
spsp:=true:
end if:
for i from 0 to r-1 do
testing if 
if e=m then
spsp:=true:
end if:
e:=e*e mod n:
squaring to take next i instead of exponentiation
end do:
print(spsp); |
| > |
if spsp then print(n,"is strong pseudoprime to base",a);end if; |
Compare the number of pseudoprimes and strong pseudoprimes
| > |
restart:
LL:=3: low limit odd number > 1
HL:=100000: high limit
a:=11: base
Digits:=20: str:=0: ps:=0: |
| > |
for n from LL by 2 to HL do
if isprime(n)=false then
spsp:=false:psp:=false:
m:=n-1: q:=m: r:=0:
while type(q,even) do
q:=iquo(q,2):r:=r+1:
end do:
e:=a&^q mod n:
if e=1 then
str:=str+1:spsp:=true:
end if;
for i from 0 to r-1 do
if e=m then
spsp:=true:str:=str+1:
end if:
e:=e*e mod n:
end do:
if e=1
then ps:=ps+1:
end if:end if:
end do:
print("number of strong pseudoprimes",str);
print("number of pseudoprimes",ps);
PLEASE WAIT |
Test for pseudoprime and strongpseudoprime with bases in a testbase
| > |
restart:
Testing for pseudoprimes and strong pseudoprimes
for number n to choose and bases in textbase to choose
Digits:=20:n:=314821:testbase :=[2,3,5,7,11,13,17]:
sp:="n strong pseudoprime base %a ":p:="n pseudoprime base %a ": |
| > |
while type(q,even) do
q:=iquo(q,2):r:=r+1:
end do: |
| > |
for a in testbase do
spsp:=false:psp:=false:
e:=a&^q mod n:
if e=1 then
spsp:=true: printf(sp,a);
end if;
for i from 0 to r-1 do
if e=m then
spsp:=true:printf(sp,a);
end if;
e:=e*e mod n:
end do:
if e=1 and spsp=false then
psp:=true: printf(p,a);
end if:
end do: |
n strong pseudoprime base 2 n pseudoprime base 3 n pseudoprime base 5 n strong pseudoprime base 7 n pseudoprime base 11 n pseudoprime base 17
Primality test: testing n for strong pseudoprimes to several bases in testbase
| > |
restart:
Testing a big number n for strong pseudoprimes to bases in pr
Choose n and pr
n:=2^1279-1:pr:=[2,3,5,7,11,13,17,19,23,29]:
sp:="n spp base %a ": |
| > |
while type(q,even) do
q:=iquo(q,2):r:=r+1:
end do: |
| > |
for a in pr do
e:=a&^q mod n:
if e=1 then
printf(sp,a);
end if:
for i from 0 to r-1 do
if e=m then
printf(sp,a);
end if:
e:=e*e mod n:
end do; |
n spp base 2 n spp base 3 n spp base 5 n spp base 7 n spp base 11 n spp base 13 n spp base 17 n spp base 19 n spp base 23 n spp base 29
Comments
The program above admits us to test a number n for strong pseudoprimality (spp-test) to several bases. For simplicity the testbase was given. (Theoretically it is possible to construct a composite number which pass the spp-test for any small set of bases a.) If n is prime then it satisfies spp-test to all bases a. Rabin has showed that:: if n is composite and we select base a at random the probability that n passes the spp-test to base a is less than1/4. If we repeat the test t times with different a and n passes the spp-test the probability that n is prime is 
. We call n a probable prime. (Miller-Rabin Probabilistic Primality Test) If n passes the spp-test to 10 bases the probability that n is prime is 0.999999. Most numbers are composite and the spp-test will prove their compositeness. The spp-test will never prove the primality, only that the number is a probable prime. There are a number of more advanced probabilty tests. Probabilistic primality tests are sufficient for practical use e g cryptography.
Conclusion
As you have discovered from the programs, MAPLE is well suited
for (among others) applications like these.
Some results
Examples for the treated types of pseudoprimes
p primes
p(x) primes less than x
pp pseudoprime
pseudoprime to base a
spp strong pseudoprime
Cmn Carmichael number
Cmn(x) Carmichael number less than x
?a : 
Least element in each region
p 2
341
2047
Cmn 561
Cmn?
15841
Number of elements x = 
p(x) 78498
245
46
Cmn(x) 43 (of these 23 with 3 factors, 19 with 4 factors, 1 with 5 factors)
'Beautiful' Carmichael numbers
1729 = 7*13*19 = 19*91 = 
+ 
41041 = 7*11*13*41 = 1001*41
410041= 41*73*137 = 10001*41
101101 = 7*11*13*101 = 101*1001
Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.
