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 e-mail is wizykowski [at] gmail [dot] com. Write who should be credited for submitted record.

News

Subscribe to the RSS Feed

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
112-02-2011132239814494960528Wojciech Izykowski, Marcin Panasiuk
210-03-201131634928111000544, 31481107Jim Sinclair
312-02-20111059368942532, 1005905886, 1340600841Wojciech Izykowski, Marcin Panasiuk
412-02-2011318583172186472, 642735, 553174392, 3046413974Wojciech Izykowski, Marcin Panasiuk
512-02-201130718376923578492, 75088, 642735, 203659041, 3613982119Wojciech Izykowski, Marcin Panasiuk
720-04-2011at least 2^642, 325, 9375, 28178, 450775, 9780504, 1795265022Jim Sinclair

Record history of the best known SPRP bases sets

datebest solutionbasesdiscoverer
1 base
12-02-2011132239814494960528Wojciech Izykowski, Marcin Panasiuk
19935329377687Gerhard Jaeschke
2 bases
10-03-201131634928111000544, 31481107Jim Sinclair
12-02-2011227132641660, 56928287Wojciech Izykowski, Marcin Panasiuk
2005380103072, 9332593Charles Greathouse
1993194710332, 299417Gerhard Jaeschke
3 bases
12-02-20111059368942532, 1005905886, 1340600841Wojciech Izykowski, Marcin Panasiuk
2009757929806772, 379215, 457083754Steve Worley
199347591231412, 7, 61Gerhard Jaeschke
4 bases
12-02-2011318583172186472, 642735, 553174392, 3046413974Wojciech Izykowski, Marcin Panasiuk
2009216526845022212, 1215, 34862, 574237825Steve Worley
199311220046696332, 13, 23, 1662803Gerhard Jaeschke
5 bases
12-02-201130718376923578492, 75088, 642735, 203659041, 3613982119Wojciech Izykowski, Marcin Panasiuk
7 bases
20-04-2011at least 2^642, 325, 9375, 28178, 450775, 9780504, 1795265022Jim Sinclair

Solution checker

1 base

2 bases

Be patient! Checking one pair can take up to 10 minutes.

3 bases

4 bases

5 bases

Links

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://priv.ckp.pl/wizykowski/sprp.pdf
Finding strong probable prime bases for efficient ranged primality testing
 
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.

If you are interested in composite 2-SPRP only, you can download slightly smaller file containing composite 2-SPRP list up to 2^64 (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