Introduction

This website summarizes the best known bases for deterministic variant of Miller-Rabin primality test.

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.

News

2013

26 July. New record found: 1050535501 for bases 336781006125, 9639812373923155 by Marcin Panasiuk and Wojciech Izykowski.
27 May. New records found by Steve Worley:
885594169 for bases 725270293939359937, 3569819667048198375
350269456337 for bases 4230279247111683200, 14694767155120705706, 16641139526367750375
23 May. New records found by Steve Worley:
55245642489451 for bases 2, 141889084524735, 1199124725622454117, 11096072698276303650
7999252175582851 for bases 2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805
585226005592931977 for bases 2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375

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

Solution checker

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
Other
http://primes.utm.edu/prove/prove2_3.html
Strong probable-primality and a practical test (at the Prime Pages)
 
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test
Deterministic variants of the Miller-Rabin primality test (at Wikipedia)
 
http://www.mersenneforum.org/showthread.php?t=12208
Using CUDA to find better SPRP classifiers (at Mersenne Forum)
 
http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html
PSPS list computed by Jan Feitsma, arranged and edited by William Galway. Some results above depend on it.
At http://www.janfeitsma.nl/math/psp2/index 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
2-SPRP-2-to-64.zip (mirror 1)
2-SPRP-2-to-64.zip (mirror 2)
203,889,146 bytes [MD5    ] 1bdbd72be1b6e104f8c3d08d05ee6bf4
[SHA1   ] f219614e04e2e9bf0e6d4dbc786c79e5ed1f2d99
[SHA-256] a8db0d43c9b04cb1f9d19fc9a87da779c420a6d88f6c2c7b87cde377a7e1f7fe
Useful code
https://github.com/wizykowski/miller-rabin
Efficient implementation of the Miller-Rabin primality test in C.
 
https://github.com/danaj/Math-Prime-Util
Math::Prime::Util Perl module. Its primality.c file contains lots of useful C code implementing various primality tests.