cp's OEIS Frontend

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

%I A014233 #76 Apr 05 2025 09:04:28
%S A014233 2047,1373653,25326001,3215031751,2152302898747,3474749660383,
%T A014233 341550071728321,341550071728321,3825123056546413051,
%U A014233 3825123056546413051,3825123056546413051,318665857834031151167461,3317044064679887385961981
%N A014233 Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness.
%C A014233 Note that some terms are repeated.
%C A014233 Same as A006945 except for first term.
%C A014233 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
%D A014233 R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
%D A014233 Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 98.
%H A014233 Martin R. Albrecht, Jake Massimo, Kenneth G. Paterson, Juraj Somorovsky, <a href="https://doi.org/10.1145/3243734.3243787">Prime and Prejudice: Primality Testing Under Adversarial Conditions</a>, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 281-298.
%H A014233 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 39.10, pp. 786-792.
%H A014233 Paul D. Beale, <a href="http://arxiv.org/abs/1411.2484">A new class of scalable parallel pseudorandom number generators based on Pohlig-Hellman exponentiation ciphers</a>, arXiv:1411.2484 [physics.comp-ph], 2014-2015.
%H A014233 Paul D. Beale, Jetanat Datephanyawat, <a href="https://arxiv.org/abs/1811.11629">Class of scalable parallel and vectorizable pseudorandom number generators based on non-cryptographic RSA exponentiation ciphers</a>, arXiv:1811.11629 [cs.CR], 2018.
%H A014233 C. Caldwell, <a href="https://primes.utm.edu/prove/prove2_3.html">Strong probable-primality and a practical test</a>.
%H A014233 G. Jaeschke, <a href="http://dx.doi.org/10.1090/S0025-5718-1993-1192971-8">On strong pseudoprimes to several bases</a>, Mathematics of Computation, 61 (1993), 915-926.
%H A014233 Yupeng Jiang, Yingpu Deng, <a href="http://arxiv.org/abs/1207.0063">Strong pseudoprimes to the first 9 prime bases</a>, arXiv:1207.0063v1 [math.NT], June 30, 2012.
%H A014233 A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, <a href="http://www.cacr.math.uwaterloo.ca/hac/">Handbook of Applied Cryptography</a>, CRC Press, 1996; see section 4.2.3, Miller-Rabin test.
%H A014233 C. Pomerance, J. L. Selfridge and S. S. Wagstaff, Jr., <a href="http://dx.doi.org/10.1090/S0025-5718-1980-0572872-7">The pseudoprimes to 25.10^9</a>, Mathematics of Computation 35 (1980), pp. 1003-1026.
%H A014233 Eric Bach, <a href="http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023756-8/">Explicit bounds for primality testing and related problems</a>, Mathematics of Computation 55 (1990), pp. 355-380.
%H A014233 F. Raynal, <a href="http://www.security-labs.org/full-page.php3?page=5">Miller-Rabin's Primality Test</a>
%H A014233 K. Reinhardt, <a href="http://www-fs.informatik.uni-tuebingen.de/~reinhard/krypto/English/2.3.1.e.html">Miller-Rabin Primality Test for odd n</a> [broken link]
%H A014233 Jonathan P. Sorenson, Jonathan Webster, <a href="http://arxiv.org/abs/1509.00864">Strong Pseudoprimes to Twelve Prime Bases</a>, arXiv:1509.00864 [math.NT], 2015.
%H A014233 S. Wagon, <a href="http://dx.doi.org/10.1007/BF03025793">Primality testing</a>, Math. Intellig., 8 (No. 3, 1986), 58-61.
%H A014233 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/StrongPseudoprime.html">Strong Pseudoprime</a>
%H A014233 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Rabin-Miller Strong Pseudoprime Test</a>
%H A014233 Wikipedia, <a href="http://en.wikipedia.org/wiki/Miller-Rabin_primality_test">Miller-Rabin primality test</a>
%H A014233 Zhenxiang Zhang and Min Tang, <a href="http://dx.doi.org/10.1090/S0025-5718-03-01545-X">Finding strong pseudoprimes to several bases. II</a>, Mathematics of Computation 72 (2003), pp. 2085-2097.
%H A014233 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>
%F A014233 Bach shows that, on the ERH, a(n) >> exp(sqrt(1/2 * x log x)). - _Charles R Greathouse IV_, May 17 2011
%K A014233 nonn,hard,more
%O A014233 1,1
%A A014233 _Jud McCranie_, Feb 15 1997
%E A014233 Minor edits from _N. J. A. Sloane_, Jun 20 2009
%E A014233 a(9)-a(11) from _Charles R Greathouse IV_, Aug 14 2010
%E A014233 a(12)-a(13) from the Sorenson/Webster reference, _Joerg Arndt_, Sep 04 2015