login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

Hints
(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. 3
2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981 (list; graph; refs; listen; history; text; internal format)
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.

Index entries for sequences related to pseudoprimes

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

P. 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.

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.

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: A022527 A024009 A258812 * 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

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

License Agreements, Terms of Use, Privacy Policy .

Last modified December 10 21:11 EST 2016. Contains 279011 sequences.