The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A014233 Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness. 4
2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981 (list; graph; refs; listen; history; text; internal format)



Note that some terms are repeated.

Same as A006945 except for first term.

a(12) > 2^64.  Hence the primality of numbers < 2^64 can be determined by asserting strong pseudoprimality to all prime bases <= 37 (=prime(12)). Testing to prime bases <=31 does not suffice, as a(11) < 2^64 and a(11) is a strong pseudoprime to all prime bases <= 31 (=prime(11)). - Joerg Arndt, Jul 04 2012


R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.


Table of n, a(n) for n=1..13.

Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, Juraj Somorovsky, Prime and Prejudice: Primality Testing Under Adversarial Conditions, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 281-298.

Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792.

Paul D. Beale, A new class of scalable parallel pseudorandom number generators based on Pohlig-Hellman exponentiation ciphers, arXiv:1411.2484 [physics.comp-ph], 2014-2015.

Paul D. Beale, Jetanat Datephanyawat, Class of scalable parallel and vectorizable pseudorandom number generators based on non-cryptographic RSA exponentiation ciphers, arXiv:1811.11629 [cs.CR], 2018.

C. Caldwell, Strong probable-primality and a practical test.

G. Jaeschke, On strong pseudoprimes to several bases, Mathematics of Computation, 61 (1993), 915-926.

Yupeng Jiang, Yingpu Deng, Strong pseudoprimes to the first 9 prime bases, arXiv:1207.0063v1 [math.NT], June 30, 2012.

A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996; see section 4.2.3, Miller-Rabin test.

C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., The pseudoprimes to 25.10^9, Mathematics of Computation 35 (1980), pp. 1003-1026.

Eric Bach, Explicit bounds for primality testing and related problems, Mathematics of Computation 55 (1990), pp. 355-380.

F. Raynal, Miller-Rabin's Primality Test

K. Reinhardt, Miller-Rabin Primality Test for odd n

Jonathan P. Sorenson, Jonathan Webster, Strong Pseudoprimes to Twelve Prime Bases, arXiv:1509.00864 [math.NT], 2015.

S. Wagon, Primality testing, Math. Intellig., 8 (No. 3, 1986), 58-61.

Eric Weisstein's World of Mathematics, Strong Pseudoprime

Eric Weisstein's World of Mathematics, Rabin-Miller Strong Pseudoprime Test

Wikipedia, Miller-Rabin primality test

Zhenxiang Zhang and Min Tang, Finding strong pseudoprimes to several bases. II, Mathematics of Computation 72 (2003), pp. 2085-2097.

Index entries for sequences related to pseudoprimes


Bach shows that, on the ERH, a(n) >> exp(sqrt(1/2 * x log x)). - Charles R Greathouse IV, May 17 2011


Sequence in context: A258812 A321556 A321550 * A160964 A022193 A069386

Adjacent sequences:  A014230 A014231 A014232 * A014234 A014235 A014236




Jud McCranie, Feb 15 1997


Minor edits from N. J. A. Sloane, Jun 20 2009

a(9)-a(11) from Charles R Greathouse IV, Aug 14 2010

a(12)-a(13) from the Sorenson/Webster reference, Joerg Arndt, Sep 04 2015



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 09:02 EDT 2021. Contains 348041 sequences. (Running on oeis4.)