A072276
Strong pseudoprimes to bases 2 and 3.
Original entry on oeis.org
1373653, 1530787, 1987021, 2284453, 3116107, 5173601, 6787327, 11541307, 13694761, 15978007, 16070429, 16879501, 25326001, 27509653, 27664033, 28527049, 54029741, 61832377, 66096253, 74927161, 80375707, 101649241
Offset: 1
- Don Reble, Table of n, a(n) for n = 1..10000
- Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
- D. Bleichenbacher, Thesis and strong pseudoprimes to 2 and 3 up to 10^16
- Washington Bomfim, Table of n, a(n) for n=1..1499371 [a large file]
- Jan Feitsma and William Galway, Tables of pseudoprimes and related data
- A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography, section 4.2.3, Miller-Rabin test.
- Eric Weisstein's World of Mathematics, Rabin-Miller test
- Index entries for sequences related to pseudoprimes
-
nmax = 10^8; sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := (s = IntegerExponent[n - 1, 2]; d = (n - 1)/2^s; If[ PowerMod[b, d, n] == 1, Return[True], Do[ If[ PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s-1}]]); A072276 = {}; n = 1; While[n < nmax, n = n+2; If[sppQ[n, 2] && sppQ[n, 3] , Print[n]; AppendTo[ A072276, n]]]; A072276 (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)
A014233
Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness.
Original entry on oeis.org
2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051, 3825123056546413051, 3825123056546413051, 318665857834031151167461, 3317044064679887385961981
Offset: 1
- R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 157.
- Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 98.
- 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
a(12)-a(13) from the Sorenson/Webster reference,
Joerg Arndt, Sep 04 2015
A329759
Odd composite numbers k for which the number of witnesses for strong pseudoprimality of k equals phi(k)/4, where phi is the Euler totient function (A000010).
Original entry on oeis.org
15, 91, 703, 1891, 8911, 12403, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631, 1869211, 2741311, 3270403, 3913003, 4255903, 4686391, 5292631, 5481451, 6186403, 6969511
Offset: 1
15 is in the sequence since out of the phi(15) = 8 numbers 1 <= b < 15 that are coprime to 15, i.e., b = 1, 2, 4, 7, 8, 11, 13, and 14, 8/4 = 2 are witnesses for the strong pseudoprimality of 15: 1 and 14.
- Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, 2005, Theorem 3.5.4., p. 136.
-
o[n_] := (n - 1)/2^IntegerExponent[n - 1, 2];
a[n_?PrimeQ] := n - 1; a[n_] := Module[{p = FactorInteger[n][[;; , 1]]}, om = Length[p]; Product[GCD[o[n], o[p[[k]]]], {k, 1, om}] * (1 + (2^(om * Min[IntegerExponent[#, 2] & /@ (p - 1)]) - 1)/(2^om - 1))];
aQ[n_] := CompositeQ[n] && a[n] == EulerPhi[n]/4; s = Select[Range[3, 10^5, 2], aQ]
A380979
Composites that cause a witness to be added to a set of Fermat witnesses: a(n) is the smallest composite number that is not guaranteed composite using Fermat's Little Theorem by the witness A380978(i) for any i < n.
Original entry on oeis.org
4, 341, 1105, 1729, 29341, 75361, 162401, 252601, 294409, 334153, 399001, 1152271, 1615681, 2508013, 3581761, 3828001, 6189121, 6733693, 10024561, 10267951, 14469841, 17098369, 17236801, 19384289, 23382529, 29111881, 34657141, 53711113, 64377991, 79411201, 79624621
Offset: 1
a(1) = 4, since 4 is the smallest composite number and we need to add a witness to the empty set to guarantee its compositeness. 2 is the minimal Fermat witness for the compositeness of 4, so the set of witnesses becomes {2}.
a(2) = 341, since 341 is the smallest composite number that requires a witness other than 2, namely 3.
a(3) = 1105, since 1105 is the smallest composite number that requires a witness other than 2 and 3, namely 5.
Showing 1-4 of 4 results.
Comments