This website summarizes the best known bases for deterministic variant of Miller-Rabin primality test. It also contains a brief summary of hashing methods.

Submissions and contact

If you discovered a new record or you know about an unlisted record, please let me know. My email is wizykowski [at] gmail [dot] com. Write who should be credited for submitted record.



27 April. Added section about using hashing to obtain witness.

The best known SPRP bases sets

countdatebest solutionbasesdiscoverer
103-03-20133415319345883071009581737Steve Worley
226-07-20131050535501336781006125, 9639812373923155Wojciech Izykowski, Marcin Panasiuk
327-05-20133502694563374230279247111683200, 14694767155120705706, 16641139526367750375Steve Worley
423-05-2013552456424894512, 141889084524735, 1199124725622454117, 11096072698276303650Steve Worley
523-05-201379992521755828512, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805Steve Worley
623-05-20135852260055929319772, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375Steve Worley
720-04-2011at least 2642, 325, 9375, 28178, 450775, 9780504, 1795265022Jim Sinclair

Record history of the best known SPRP bases sets

datebest solutionbasediscoverer
03-03-20133415319345883071009581737Steve Worley
08-02-2013291831126401071349994536Wojciech Izykowski, Marcin Panasiuk
23-01-201327216162769592775616394Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
14-01-201321824534933608779780163Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
17-10-20122123211948244569546278Sebastian Jaworowicz, Wojciech Izykowski, Marcin Panasiuk
15-10-20121920011769236083487960Sebastian Jaworowicz, Wojciech Izykowski, Marcin Panasiuk
02-07-201216170164390572806844Wojciech Izykowski, Marcin Panasiuk
12-02-2011132239814494960528Wojciech Izykowski, Marcin Panasiuk
12-02-201149141921211727 *Wojciech Izykowski, Marcin Panasiuk
19935329377687Gerhard Jaeschke
* best witness less than 232
datebest solutionbasesdiscoverer
26-07-20131050535501336781006125, 9639812373923155Wojciech Izykowski, Marcin Panasiuk
27-05-2013885594169725270293939359937, 3569819667048198375Steve Worley
10-03-201371616930115, 13393019396194701Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
28-02-201362473242115, 5511855321103177Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
07-02-201352092414115, 750068417525532Wojciech Izykowski, Marcin Panasiuk
03-12-201246675818191869414, 6346128598129234Steve Worley
21-11-20123600183611143370, 2350307676Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
10-03-201131634928111000544, 31481107Jim Sinclair
12-02-2011227132641660, 56928287Wojciech Izykowski, Marcin Panasiuk
08-09-20091766094412346211568, 3056093627David McAllister
2005380103072, 9332593Charles Greathouse
1993194710332, 299417Gerhard Jaeschke
datebest solutionbasesdiscoverer
27-05-20133502694563374230279247111683200, 14694767155120705706, 16641139526367750375Steve Worley
21-05-201327391952304115, 7363882082, 992620450144556Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
18-05-201324217550781715, 7363882082, 211573017068182Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
15-05-201322014605940715, 953185122, 158682512356199Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
23-02-201315463967338115, 176006322, 4221622697Wojciech Izykowski, Marcin Panasiuk
30-01-20131091348664972, 45650740, 3722628058Steve Worley
12-02-20111059368942532, 1005905886, 1340600841Wojciech Izykowski, Marcin Panasiuk
2009757929806772, 379215, 457083754Steve Worley
199347591231412, 7, 61Gerhard Jaeschke
datebest solutionbasesdiscoverer
23-05-2013552456424894512, 141889084524735, 1199124725622454117, 11096072698276303650Steve Worley
30-01-2013476366229612012, 2570940, 211991001, 3749873356Steve Worley
12-02-2011318583172186472, 642735, 553174392, 3046413974Wojciech Izykowski, Marcin Panasiuk
2009216526845022212, 1215, 34862, 574237825Steve Worley
199311220046696332, 13, 23, 1662803Gerhard Jaeschke
datebest solutionbasesdiscoverer
23-05-201379992521755828512, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805Steve Worley
30-01-201337705795821545472, 2570940, 880937, 610386380, 4130785767Steve Worley
12-02-201130718376923578492, 75088, 642735, 203659041, 3613982119Wojciech Izykowski, Marcin Panasiuk
datebest solutionbasesdiscoverer
23-05-20135852260055929319772, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375Steve Worley
datebest solutionbasesdiscoverer
20-04-2011at least 2642, 325, 9375, 28178, 450775, 9780504, 1795265022Jim Sinclair


Let \(a\) be primality witness. Let \(n\) be the number we test for primality.

Solution checker


By using hashing we can reduce number of witnesses needed to perform deterministic test. The idea is to compute witnesses for every composite by using a small (not using too much memory) and fast function. It is also important for this function to be small to be fast, because we should spare precious cache memory.

(2016-2014) Bradley Berg
Bradley Berg found very dense hashes up to 264. Latest version can be found on his website
(2015) Forisek and Jancina
Forisek and Jancina hashes are described in their paper Fast Primality Testing for Integers That Fit into a Machine Word. Their code can be found at
(2014) Dana Jacobsen
Dana Jacobsen posted his own hashes up to 264:
Related papers
W. Izykowski, M. Panasiuk, Finding strong probable prime bases for efficient ranged primality testing
S. Worley, Optimization of Primality Testing Methods by GPU Evolutionary Search
G. Jaeschke, On strong pseudoprimes to several bases
C. Pomerance, J. L. Selfridge, S. S. Wagstaff, The pseudoprimes to 25 · 109
Strong probable-primality and a practical test (at the Prime Pages)
Deterministic variants of the Miller-Rabin primality test (at Wikipedia)
Using CUDA to find better SPRP classifiers (at Mersenne Forum)
PSPS list computed by Jan Feitsma, arranged and edited by William Galway. Some results above depend on it.
At you can find Feitsma's notes

If you are interested in composite 2-SPRP only, you can download slightly smaller file containing composite 2-SPRP list up to 264 (based on Feitsma's results):
Download linkSizeChecksums (mirror 1) (mirror 2)
203,889,146 bytes [MD5    ] 1bdbd72be1b6e104f8c3d08d05ee6bf4
[SHA1   ] f219614e04e2e9bf0e6d4dbc786c79e5ed1f2d99
[SHA-256] a8db0d43c9b04cb1f9d19fc9a87da779c420a6d88f6c2c7b87cde377a7e1f7fe
Useful code
Efficient implementation of the Miller-Rabin primality test in C.
Math::Prime::Util Perl module. Its primality.c file contains lots of useful C code implementing various primality tests.