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 7, 2013

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+18 24739954287740860 33763684 0 0
1.0 e+19 234057667276344607 91210364 0 0
2^64
118968378 0 0

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 0 0 3096 15352 3622
2.0e+10 19865 4412 0 0 4145 20877 4927
3.0e+10 23554 5233 0 0 4970 25015 5872
4.0e+10 26568 5865 0 0 5557 28420 6600
5.0e+10 29238 6458 0 0 6111 31313 7238
6.0e+10 31543 6977 0 0 6623 33905 7801
7.0e+10 33663 7450 0 0 7036 36338 8353
8.0e+10 35566 7861 0 0 7458 38588 8844
9.0e+10 37320 8243 0 0 7806 40630 9280
1.0e+11 38975 8607 0 0 8165 42505 9714
2.0e+11 52092 11480 0 0 10929 57588 12921
3.0e+11 61828 13619 0 0 12963 68674 15315
4.0e+11 69556 15325 0 0 14570 77946 17252
5.0e+11 76242 16795 0 0 15947 86064 18973
6.0e+11 82294 18162 0 0 17165 93317 20511
7.0e+11 87760 19317 0 0 18323 99978 21907
8.0e+11 92742 20426 0 0 19385 105997 23180
9.0e+11 97341 21417 0 0 20414 111593 24413
1.0e+12 101629 22407 0 0 21354 116928 25542

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

* Special thanks to  Wojciech Izykowski, Danaj, and Jan Feitsma for finding errors in the table.  The # PSP (Miller-Rabin base 2) column had 433 more PSP's values than it should have between 4.0e+11 and 1.0e+12.  Looking at my original data, I had miscopied a value which caused a cascading error to the end of a table.  These have now been corrected.


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