Deterministic variants of the Miller-Rabin primality test. Miller-Rabin SPRP bases records

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

. 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

count	date	best solution	bases	discoverer
1	03-03-2013	341531	9345883071009581737	Steve Worley
2	26-07-2013	1050535501	336781006125, 9639812373923155	Wojciech Izykowski, Marcin Panasiuk
3	27-05-2013	350269456337	4230279247111683200, 14694767155120705706, 16641139526367750375	Steve Worley
4	23-05-2013	55245642489451	2, 141889084524735, 1199124725622454117, 11096072698276303650	Steve Worley
5	23-05-2013	7999252175582851	2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805	Steve Worley
6	23-05-2013	585226005592931977	2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375	Steve Worley
7	20-04-2011	at least 2⁶⁴	2, 325, 9375, 28178, 450775, 9780504, 1795265022	Jim Sinclair

Record history of the best known SPRP bases sets

date	best solution	base	discoverer
03-03-2013	341531	9345883071009581737	Steve Worley
08-02-2013	291831	126401071349994536	Wojciech Izykowski, Marcin Panasiuk
23-01-2013	272161	62769592775616394	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
14-01-2013	218245	34933608779780163	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
17-10-2012	212321	1948244569546278	Sebastian Jaworowicz, Wojciech Izykowski, Marcin Panasiuk
15-10-2012	192001	1769236083487960	Sebastian Jaworowicz, Wojciech Izykowski, Marcin Panasiuk
02-07-2012	161701	64390572806844	Wojciech Izykowski, Marcin Panasiuk
12-02-2011	132239	814494960528	Wojciech Izykowski, Marcin Panasiuk
12-02-2011	49141	921211727 *	Wojciech Izykowski, Marcin Panasiuk
1993	5329	377687	Gerhard Jaeschke

* best witness less than 2³²

date	best solution	bases	discoverer
26-07-2013	1050535501	336781006125, 9639812373923155	Wojciech Izykowski, Marcin Panasiuk
27-05-2013	885594169	725270293939359937, 3569819667048198375	Steve Worley
10-03-2013	716169301	15, 13393019396194701	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
28-02-2013	624732421	15, 5511855321103177	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
07-02-2013	520924141	15, 750068417525532	Wojciech Izykowski, Marcin Panasiuk
03-12-2012	466758181	91869414, 6346128598129234	Steve Worley
21-11-2012	360018361	1143370, 2350307676	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
10-03-2011	316349281	11000544, 31481107	Jim Sinclair
12-02-2011	227132641	660, 56928287	Wojciech Izykowski, Marcin Panasiuk
08-09-2009	176609441	2346211568, 3056093627	David McAllister
2005	38010307	2, 9332593	Charles Greathouse
1993	19471033	2, 299417	Gerhard Jaeschke

date	best solution	bases	discoverer
27-05-2013	350269456337	4230279247111683200, 14694767155120705706, 16641139526367750375	Steve Worley
21-05-2013	273919523041	15, 7363882082, 992620450144556	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
18-05-2013	242175507817	15, 7363882082, 211573017068182	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
15-05-2013	220146059407	15, 953185122, 158682512356199	Dana Jacobsen, Wojciech Izykowski, Marcin Panasiuk
23-02-2013	154639673381	15, 176006322, 4221622697	Wojciech Izykowski, Marcin Panasiuk
30-01-2013	109134866497	2, 45650740, 3722628058	Steve Worley
12-02-2011	105936894253	2, 1005905886, 1340600841	Wojciech Izykowski, Marcin Panasiuk
2009	75792980677	2, 379215, 457083754	Steve Worley
1993	4759123141	2, 7, 61	Gerhard Jaeschke

date	best solution	bases	discoverer
23-05-2013	55245642489451	2, 141889084524735, 1199124725622454117, 11096072698276303650	Steve Worley
30-01-2013	47636622961201	2, 2570940, 211991001, 3749873356	Steve Worley
12-02-2011	31858317218647	2, 642735, 553174392, 3046413974	Wojciech Izykowski, Marcin Panasiuk
2009	21652684502221	2, 1215, 34862, 574237825	Steve Worley
1993	1122004669633	2, 13, 23, 1662803	Gerhard Jaeschke

date	best solution	bases	discoverer
23-05-2013	7999252175582851	2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805	Steve Worley
30-01-2013	3770579582154547	2, 2570940, 880937, 610386380, 4130785767	Steve Worley
12-02-2011	3071837692357849	2, 75088, 642735, 203659041, 3613982119	Wojciech Izykowski, Marcin Panasiuk

date	best solution	bases	discoverer
23-05-2013	585226005592931977	2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375	Steve Worley

date	best solution	bases	discoverer
20-04-2011	at least 2⁶⁴	2, 325, 9375, 28178, 450775, 9780504, 1795265022	Jim Sinclair

Remarks

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

Depending on your Miller-Rabin implementation, you may need to take \(a \gets a \mod n\).
When the witness \(a\) equals \(0\), the test should return that \(n\) is prime.
It is crucial to test all the bases and not just the bases less than \(n\).

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 2⁶⁴. 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 2⁶⁴: http://probableprime.org/download/example-primality.c

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 · 10⁹

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 2⁶⁴ (based on Feitsma's results):

Download link	Size	Checksums
2-SPRP-2-to-64.zip	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.

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.