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

%I #72 Feb 23 2024 06:27:17

%S 2047,1373653,25326001,3215031751,2152302898747,3474749660383,

%T 341550071728321,341550071728321,3825123056546413051,

%U 3825123056546413051,3825123056546413051,318665857834031151167461,3317044064679887385961981

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

%C Note that some terms are repeated.

%C Same as A006945 except for first term.

%C 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 R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.

%H 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 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, section 39.10, pp. 786-792.

%H 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 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 C. Caldwell, <a href="https://primes.utm.edu/prove/prove2_3.html">Strong probable-primality and a practical test</a>.

%H 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 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 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 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 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 F. Raynal, <a href="http://www.security-labs.org/full-page.php3?page=5">Miller-Rabin's Primality Test</a>

%H 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 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 S. Wagon, <a href="http://dx.doi.org/10.1007/BF03025793">Primality testing</a>, Math. Intellig., 8 (No. 3, 1986), 58-61.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/StrongPseudoprime.html">Strong Pseudoprime</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Rabin-Miller Strong Pseudoprime Test</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Miller-Rabin_primality_test">Miller-Rabin primality test</a>

%H 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 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

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

%K nonn,hard,more

%O 1,1

%A _Jud McCranie_, Feb 15 1997

%E Minor edits from _N. J. A. Sloane_, Jun 20 2009

%E a(9)-a(11) from _Charles R Greathouse IV_, Aug 14 2010

%E a(12)-a(13) from the Sorenson/Webster reference, _Joerg Arndt_, Sep 04 2015