Pseudoprime Enumeration with Probabilistic Primality Tests 
(Fermat base 2, Baillie-PSW, Miller-Rabin, Lucas, Lucas-Selfridge)

by Jeff Gilchrist
Jeff's E-mail Address

Last Updated:  July 11, 2011

This page show the number of prime numbers and pseudoprimes up to different levels using various probabilistic primality (prp) testing algorithms.  With this enumeration, developers can use a fast prp test to determine if a number is prime taking into account the # of pseudoprimes listed in the range they want to use.

Primality Testing Primer

There are two main types of primality tests, probabilistic and deterministic.  Probabilistic tests are very fast but there is a small probability they will false identify composite numbers as prime (but not vice-versa).  Deterministic tests are slower but guarentee that the number is prime.  Numbers that pass probablistic tests are called probable primes since they are not guarenteed to be prime.  Numbers that pass probabilistic tests that are in fact composite numbers are called pseudoprimes.  For example, using a Fermat base 2 prp test, the value 341 passes the test, but in fact it is composite with factors 11 and 31.  So 341 would be a pseudoprime (psp).

Pseudoprime Table (Fermat, Baillie-PSW)

Database used to test pseudoprimes from 1 to 2^64 was created by Jan Feitsma and William Galway: http://www.janfeitsma.nl/math/psp2/database
(In 2009, Jeff Gilchrist and David Cleaver verified the pseudoprime database with Jan's algorithm using independently written code)
Code to test pseudoprimes uses Baillie-PSW algorithm written by Thomas R. Nicely: http://www.trnicely.net/misc/bpsw.html
Prime number counts taken from table's by Thomas R. Nicely and Tomas Oliveira e Silva

Limit # Prime Numbers # PSP (Fermat base 2) # PSP (Baillie-PSW Standard) # PSP (Baillie-PSW Strong)
1.0 e+10 455052511 14884 0 0
1.0 e+11 4118054813 38975 0 0
1.0 e+12 37607912018 101629 0 0
1.0 e+13 346065536839 264239 0 0
1.0 e+14 3204941750802 687007 0 0
1.0 e+15 29844570422669 1801533 0 0
1.0 e+16 279238341033925 4744920 0 0
2.0 e+16 547863431950008 6362330 0 0
3.0 e+16 812760276789503 7556682 0 0
4.0 e+16 1075292778753150 8537451 0 0
5.0 e+16 1336094767763971 9387192
 0 0
6.0 e+16 1595534099589274 10142500
 0 0
7.0 e+16 1853851099626620 10829550
 0 0
8.0 e+16 2111215026220444 11462279
 0 0
9.0 e+16 2367751438410550 12050920
 0 0
1.0 e+17 2623557157654233 12604009
 0 0
1.0 e+18247399542877408603376368400
1.0 e+192340576672763446079121036400
2^6411896837800

For any number up to 2^64, it is safe to use a Baillie-PSW prp test to ensure a number is prime since no pseudoprimes exist up to that limit.  Charles Greathouse has also confirmed no BPSW pseudoprimes exist using PARI with Jan Feitsma's database.


Pseudoprime Table (Fermat, Miller-Rabin, Lucas, Lucas-Selfridge)

Code to test pseudoprimes uses algorithms written by Thomas R. Nicely: http://www.trnicely.net/misc/bpsw.html

Limit # PSP (Fermat base 2) # PSP (Miller-Rabin base 2) # PSP (Miller-Rabin 5 bases1)# PSP (Miller-Rabin 10 bases1)# PSP (Extra Strong Lucas)# PSP (Lucas-Selfridge)# PSP (Lucas-Selfridge Strong)
1.0e+10 14884 3291 003096153523622
2.0e+10 19865 4412 004145208774927
3.0e+10 23554 5233 004970250155872
4.0e+10 26568 5865 005557284206600
5.0e+10 29238 6458 006111313137238
6.0e+10 31543 6977 006623339057801
7.0e+10 33663 7450 007036363388353
8.0e+10 35566 7861 007458385888844
9.0e+10 37320 8243 007806406309280
1.0e+11 38975 8607 008165425059714
2.0e+11520921148000109295758812921
3.0e+11618281361900129636867415315
4.0e+11695561575800145707794617252
5.0e+11762421722800159478606418973
6.0e+11822941859500171659331720511
7.0e+11877601975000183239997821907
8.0e+119274220859001938510599723180
9.0e+119734121850002041411159324413
1.0e+1210162922840002135411692825542

1 - Miller-Rabin with 5 and 10 bases enumeration used the mpz_probab_prime_p() function in MPIR v1.2 (also compatible with GMP v4.3).

* Source code to test pseudoprimes will be made available when the code has been finalized.

  • This web page is maintained by Jeff Gilchrist, Copyright (C) 2009-2011.
  • This web page best viewed using a resolution of 800 x 600 or higher.