The best known SPRP bases sets

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

Using PHP? We recommend 17eyes static code analyzer.

2013

18 May. New record found: 242175507817 for bases 15, 7363882082, 211573017068182 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
15 May. New record found: 220146059407 for bases 15, 953185122, 158682512356199 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
10 March. New record found: 716169301 for bases 15, 13393019396194701 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
3 March. New record found: 341531 for base 9345883071009581737 by Steve Worley
28 February. New record found: 624732421 for bases 15, 5511855321103177 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
23 February. New record found: 154639673381 for bases 15, 176006322, 4221622697 by Marcin Panasiuk and Wojciech Izykowski.
8 February. New record found: 291831 for base 126401071349994536 by Marcin Panasiuk and Wojciech Izykowski.
7 February. New record found: 520924141 for bases 15, 750068417525532 by Marcin Panasiuk and Wojciech Izykowski.
30 January. New records found by Steve Worley:
109134866497 for bases 2, 45650740, 3722628058
47636622961201 for bases 2, 2570940, 211991001, 3749873356
3770579582154547 for bases 2, 2570940, 880937, 610386380, 4130785767
23 January. New record found: 272161 for base 62769592775616394 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
14 January. New record found: 218245 for base 34933608779780163 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.

+ Show old news

The best known SPRP bases sets

countdatebest solutionbasesdiscoverer
103-03-20133415319345883071009581737Steve Worley
210-03-201371616930115, 13393019396194701Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
318-05-201324217550781715, 7363882082, 211573017068182Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
430-01-2013476366229612012, 2570940, 211991001, 3749873356Steve Worley
530-01-201337705795821545472, 2570940, 880937, 610386380, 4130785767Steve Worley
720-04-2011at least 2642, 325, 9375, 28178, 450775, 9780504, 1795265022Jim Sinclair

Record history of the best known SPRP bases sets

datebest solutionbasesdiscoverer
1 base
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
2 bases
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
3 bases
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
4 bases
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
5 bases
30-01-201337705795821545472, 2570940, 880937, 610386380, 4130785767Steve Worley
12-02-201130718376923578492, 75088, 642735, 203659041, 3613982119Wojciech Izykowski, Marcin Panasiuk
7 bases
20-04-2011at least 2642, 325, 9375, 28178, 450775, 9780504, 1795265022Jim Sinclair
* best witness less than 232

Solution checker

Take part in SPRP search

You can participate in SPRP search. See details here.

Links

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

Created and maintained by Wojciech Izykowski.