A014233 Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness.

2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981

Offset

1,1

Comments

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

References

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

Links

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 [broken link]

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

Formula

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

Crossrefs

Sequence in context: A258812 A321556 A321550 * A160964 A022193 A069386

Adjacent sequences: A014230 A014231 A014232 * A014234 A014235 A014236

Keyword

nonn,hard,more

Author

Jud McCranie, Feb 15 1997

Extensions

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

Status

approved