Introduction

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.

News

2016

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

2015

10 June. Added historical result by David McAllister.

2014

1 August. Added remarks section (suggested by Todd Lehman).

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
21 May. New record found: 273919523041 for bases 15, 7363882082, 992620450144556 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
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.

2012

3 December. New record found: 466758181 for bases 91869414, 6346128598129234 by Steve Worley.
21 November. New record found: 360018361 for bases 1143370, 2350307676 by Dana Jacobsen, Marcin Panasiuk, and Wojciech Izykowski.
17 October. New record found: 212321 for base 1948244569546278 by Sebastian Jaworowicz from PNT BOINC Team, Marcin Panasiuk, and Wojciech Izykowski.
15 October. New record found: 192001 for base 1769236083487960 by Sebastian Jaworowicz, Marcin Panasiuk, and Wojciech Izykowski.
10 July. If you participate in distributed SPRP search, you have the limited choice which record to beat. See here.
2 July. New record found: 161701 for base 64390572806844 by Marcin Panasiuk and Wojciech Izykowski.
10 June. More user-friendly solution checker.
29 May. You can now participate in SPRP search. See details here.

2011

6 September. Added solution checker for 3, 4 and 5 bases (limited to solutions where the first base equals 2).
18 August. Added RSS feed with news.
8 August. Added solution checker for 1 and 2 bases.
8 August. The website has been moved to http://miller-rabin.appspot.com - please update your bookmarks.
23 July. Added historical Jaeschke's result for 1 base.
21 July. Added historical Jaeschke's result for 4 bases.
4 July. Added link to Jan Feitsma's SPSP database.
28 June. Added result for 7 bases by Jim Sinclair.
28 June. First version of this webpage, published at http://priv.ckp.pl/wizykowski/sprp.php

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

Remarks

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

Hashing

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 http://www.techneon.com/
 
(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 https://people.ksp.sk/~misof/primes/
 
(2014) Dana Jacobsen
Dana Jacobsen posted his own hashes up to 264: http://probableprime.org/download/example-primality.c
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.zip203,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.
 

Acknowledgements

The author would like to thank Dana Jacobsen, Marcin Panasiuk, Steve Worley, Bradley Berg, Todd Lehman and Brian Dean for useful remarks which helped improve this website.