Application Center - Maplesoft
  Submit your work
Application Center Applications Psedudoprimes Preview

App Preview:

Psedudoprimes

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application

 

Image 

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 

> 1111&^96 mod 97;
 

1 

Issue 341  

Calculate   

Solution 

> 2&^340 mod 341;
 

1 

 

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    `mod`(`≡`(a^(n-1), 1), n) 

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;
 

341 

561 

645 

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);
 

number of primes= 

number of pseudoprimes to base  

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
 

3, 11, 17, 561 

5, 13, 17, 1105 

7, 13, 19, 1729 

5, 17, 29, 2465 

7, 13, 31, 2821 

7, 23, 41, 6601 

13, 37, 61, 29341 

7, 19, 67, 8911 

5, 29, 73, 10585 

7, 31, 73, 15841 

13, 37, 97, 46657 

41, 61, 101, 252601 

7, 73, 103, 52633 

37, 73, 109, 294409 

41, 73, 137, 410041 

37, 73, 181, 488881 

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
 

11, 13, 17, 31,  

7, 13, 19, 37,  

7, 11, 13, 41,  

7, 13, 31, 61,  

13, 17, 41, 61,  

11, 31, 41, 61,  

Strong pseudoprimes 

Definition
Given an odd composite integer n  with    n - 1 = q·`and`(2^r*with*q*odd, 0 <= r)
n is a strong pseudorprime to base a   if
a^q = 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 `mod`(`≡`(a^q, 1), n)
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);
 

1 

true 

> if spsp then print(n,"is strong pseudoprime to base",a);end if;
 

12403,  

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   ":
 

> m:=n-1:q:=m:r:=0:
 

> 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:
 

> ifactor(n);
 

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   ":
 

> m:=n-1:q:=m: r:=0:
 

> 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;
 

> 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 1-1/4^t.   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.
 

Image