minimal-elements-of-the-prime-numbers/unproven-probable-primes at main · xayahrainie4793/minimal-elements-of-the-prime-numbers

Unfortunately, for every base b, there are infinitely many strong pseudoprimes, see https://www.ams.org/journals/mcom/1980-35-151/S0025-5718-1980-0572872-7/S0025-5718-1980-0572872-7.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_45.pdf), even more worse, for any given finite set of bases, there are infinitely strong pseudoprimes to these bases simultaneously, i.e. no finite set of bases is sufficient for all composite numbers, Alford, Granville, and Pomerance have shown that there exist infinitely many composite numbers n whose smallest compositeness witness is at least (ln(n))^{1/(3×ln(ln(ln(n))))}, see https://math.dartmouth.edu/~carlp/PDF/reliable.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_121.pdf), however, there are no "strong Carmichael numbers" (i.e. numbers that are strong pseudoprimes to all bases coprime to them), and given a random base, the probability that a number is a strong pseudoprime to that base is less than 1/4, and if the generalized Riemann hypothesis (https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis, https://mathworld.wolfram.com/GeneralizedRiemannHypothesis.html, https://primes.utm.edu/notes/rh.html) is true, then every composite number n has smallest compositeness witness less than 2×(ln(n))², also, when the number n to be tested is small, trying all bases b < 2×(ln(n))² is not necessary, as much smaller sets of potential witnesses are known to suffice. For example: (also see https://oeis.org/A014233 for the smallest composite number which is strong pseudoprime to all of the first n prime bases)

test bases b	the smallest composite number which is strong pseudoprime to all these bases b	prime factorization
2	2047	23 × 89
3	121	11²
5	781	11 × 71
6	217	7 × 31
7	25	5²
10	9	3²
11	133	7 × 19
12	91	7 × 13
15	1687	7 × 241
95	1891	31 × 61
240	1991	11 × 181
385	1891	31 × 61
777	1541	23 × 67
933	1387	19 × 73
1320	4097	17 × 241
2, 3	1373653	829 × 1657
31, 73	9080191	2131 × 4261
2, 3, 5	25326001	2251 × 11251
350, 3958281543	170584961	7541 × 22621
2, 3, 5, 7	3215031751	151 × 751 × 28351
2, 7, 61	4759123141	48781 × 97561
2, 379215, 457083754	75792980677	137653 × 550609
2, 13, 23, 1662803	1122004669633	611557 × 1834669
2, 3, 5, 7, 11	2152302898747	6763 × 10627 × 29947
2, 3, 5, 7, 11, 13	3474749660383	1303 × 16927 × 157543
2, 1215, 34862, 574237825	21652684502221	3290341 × 6580681
2, 3, 5, 7, 11, 13, 17	341550071728321	10670053 × 32010157
2, 3, 5, 7, 11, 13, 17, 19, 23	3825123056546413051	149491 × 747451 × 34233211
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37	318665857834031151167461	399165290221 × 798330580441
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41	3317044064679887385961981	1287836182261 × 2575672364521
all primes p ≤ n	> e^{(n/2)^1/2} (under the generalized Riemann hypothesis)	–

Thus, for this minimal prime problem in base b, especially for square (https://en.wikipedia.org/wiki/Square_number, https://www.rieselprime.de/ziki/Square_number, https://mathworld.wolfram.com/SquareNumber.html, https://oeis.org/A000290) base b, we should not assume a number which has passed the Fermat primality tests to many bases is in fact prime, also, there are Carmichael numbers (https://en.wikipedia.org/wiki/Carmichael_number, https://primes.utm.edu/glossary/xpage/CarmichaelNumber.html, https://mathworld.wolfram.com/CarmichaelNumber.html, https://www.numbersaplenty.com/set/Carmichael_number/, http://www.numericana.com/answer/modular.htm#carmichael, https://oeis.org/A002997) (i.e. composites which are Fermat pseudoprimes to all bases b coprime to them) which are strong pseudoprimes to several bases simultaneously, see https://www.sciencedirect.com/science/article/pii/S0747717185710425?via%3Dihub (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_44.pdf), this article gives a 397-digit such number (factordb entry: http://factordb.com/index.php?id=1100000000708885054) which is strong pseudoprime to all bases b ≤ 306 (see https://mersenneforum.org/showpost.php?p=613381&postcount=6), another example is a 23707-digit number (https://primes.utm.edu/curios/page.php?number_id=4265, http://factordb.com/index.php?id=1100000002517553325) which is strong pseudoprime to all bases b ≤ 10¹¹⁰⁰, also see http://factordb.com/prooffailed.php (the factordb test failed page) (numbers passed Miller–Rabin primality tests (10 prime bases at least), but turned out to be composite) and https://faculty.lynchburg.edu/~nicely/misc/mpzspsp.html (the GNU GMP test failed page) (this page mentions a 337-digit number (http://factordb.com/index.php?id=1100000000047694476) which is strong pseudoprime to all bases b ≤ 210) (now GMP runs the Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) combine with some Miller–Rabin primality tests (https://primes.utm.edu/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/MillersTest.html, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, https://mathworld.wolfram.com/StrongPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.numericana.com/answer/pseudo.htm#strong, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm, http://ntheory.org/data/spsps.txt, https://sites.google.com/view/strong-pseudoprime, https://sites.google.com/view/bases-strong-pseudoprime, https://oeis.org/A001262, https://oeis.org/A020229, https://oeis.org/A072276, https://oeis.org/A014233, https://oeis.org/A181782, https://oeis.org/A071294, https://oeis.org/A141768, https://oeis.org/A195328, https://oeis.org/A329759, https://oeis.org/A298756) combine with some trial divisions (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial), see https://gmplib.org/manual/Number-Theoretic-Functions), thus we need to combine with strong Lucas primality tests (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html, http://ntheory.org/data/slpsps-baillie.txt, https://oeis.org/A217255), to do the Baillie–PSW primality test, only run strong tests is also a little dangerous (especially when the number has the form (m+1)×(2×m+1) or (m+1)×(3×m+1), with both factors primes), however, there is no known overlap between these lists of strong pseudoprimes and strong Lucas pseudoprimes, and there is even evidence that the numbers in these lists tend to be different kinds of numbers. For example, Fermat pseudoprimes tend to fall into the residue class 1 (mod n) for many small n, whereas Lucas pseudoprimes tend to fall into the residue class −1 (mod n) for many small n. As a result, a number that passes both a strong Fermat and a strong Lucas test is very likely to be prime, indeed, no known composites which pass the Baillie–PSW probable prime test, and no composites < 2⁶⁴ pass the Baillie–PSW probable prime test (see http://ntheory.org/pseudoprimes.html and https://faculty.lynchburg.edu/~nicely/misc/bpsw.html).

15₆₃ (base 16) is Fermat pseudoprime to base b (assuming b is coprime to the number) if and only if b is cubic residue (https://en.wikipedia.org/wiki/Cubic_residue, https://mathworld.wolfram.com/CubicResidue.html) mod the prime 2¹²⁷−1, thus 1/3 of the bases coprime to the number; 85₃₆ (base 16) is Fermat pseudoprime to base b (assuming b is coprime to the number) if and only if b is cubic residue (https://en.wikipedia.org/wiki/Cubic_residue, https://mathworld.wolfram.com/CubicResidue.html) mod the prime 5×2⁷²−1, thus 1/3 of the bases coprime to the number; 1₁₃ (base 9) is Fermat pseudoprime to base b (assuming b is coprime to the number) if and only if b is quadratic residue (https://en.wikipedia.org/wiki/Quadratic_residue, https://primes.utm.edu/glossary/xpage/QuadraticResidue.html, https://www.rieselprime.de/ziki/Quadratic_residue, https://mathworld.wolfram.com/QuadraticResidue.html) mod the prime (3¹³−1)/2, thus 1/2 of the bases coprime to the number.

number	factordb entry	bases 2 ≤ b ≤ 64 such that this number is Fermat pseudoprime (called "Fermat liars")	count
15₆₃ in base b = 16	http://factordb.com/index.php?id=1000000000043569151	2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 24, 26, 27, 29, 31, 32, 33, 34, 36, 37, 38, 39, 41, 44, 47, 48, 51, 52, 54, 57, 58, 59, 61, 62, 64	39 (61.90%)
85₃₆ in base b = 16	http://factordb.com/index.php?id=1100000000348829387	3, 5, 8, 9, 13, 15, 17, 22, 24, 25, 27, 28, 29, 39, 40, 41, 45, 46, 47, 51, 53, 62, 64	23 (36.51%)
1₁₃ in base b = 9	http://factordb.com/index.php?id=317733228541	2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 23, 24, 25, 26, 27, 28, 29, 30, 32, 35, 36, 37, 38, 39, 40, 41, 42, 45, 46, 48, 49, 50, 52, 54, 56, 57, 58, 59, 60, 61, 63, 64	50 (79.37%)
I0901 in base b = 26 (see https://github.com/curtisbright/mepn-data/commit/7565d197d7b438b437871bf71614a6f8914397f7)	http://factordb.com/index.php?id=8231653	2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 18, 21, 22, 23, 24, 25, 26, 27, 28, 32, 33, 36, 39, 41, 42, 43, 44, 46, 48, 49, 50, 52, 53, 54, 56, 59, 63, 64	40 (63.49%)
28462346×3⁷+1 (see https://mersenneforum.org/showpost.php?p=137730&postcount=1)	http://factordb.com/index.php?id=62247150703	3, 4, 7, 9, 10, 11, 12, 13, 16, 17, 19, 21, 25, 27, 28, 29, 30, 33, 36, 39, 40, 41, 44, 46, 47, 48, 49, 51, 52, 53, 57, 59, 61, 62, 63, 64	36 (57.14%)

This list is the time complexity (https://en.wikipedia.org/wiki/Time_complexity) for the primality testing (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/prove3.html, https://primes.utm.edu/prove/prove4.html) methods and the integer factoring (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm) methods:

method (primality testing (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/prove3.html, https://primes.utm.edu/prove/prove4.html) or integer factoring (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm))	time complexity (https://en.wikipedia.org/wiki/Time_complexity) (where n is the number to be primality tested (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html, https://primes.utm.edu/prove/prove3.html, https://primes.utm.edu/prove/prove4.html) or integer factored (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html, https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html, http://www.numericana.com/answer/factoring.htm), p is the prime factor to be found, O is the big O notation (https://en.wikipedia.org/wiki/Big_O_notation, https://primes.utm.edu/glossary/xpage/BigOh.html, https://mathworld.wolfram.com/Big-ONotation.html), o is the little o notation (https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation, https://primes.utm.edu/glossary/xpage/LittleOh.html, https://mathworld.wolfram.com/Little-ONotation.html), L is the L-notation (https://en.wikipedia.org/wiki/L-notation), e = 2.718281828459... is the base of the natural logarithm (https://en.wikipedia.org/wiki/E_(mathematical_constant), https://mathworld.wolfram.com/e.html, https://oeis.org/A001113), log is the natural logarithm (https://en.wikipedia.org/wiki/Natural_logarithm, https://primes.utm.edu/glossary/xpage/Log.html, https://mathworld.wolfram.com/NaturalLogarithm.html))	usage for numbers	record number	factordb entry of the record number	number of decimal digits of the record number	reference of the record number
Fermat probable primality testing (https://primes.utm.edu/prove/prove2_2.html, https://en.wikipedia.org/wiki/Fermat_primality_test, https://en.wikipedia.org/wiki/Fermat_pseudoprime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Fermat_pseudoprimality_test, https://mathworld.wolfram.com/FermatPseudoprime.html, https://www.numbersaplenty.com/set/Poulet_number/, http://www.numericana.com/answer/pseudo.htm#pseudoprime, http://ntheory.org/data/psps.txt, https://sites.google.com/view/fermat-pseudoprime, https://sites.google.com/view/bases-fermat-pseudoprime, https://oeis.org/A001567, https://oeis.org/A005935, https://oeis.org/A052155, https://oeis.org/A083876, https://oeis.org/A181780, https://oeis.org/A063994, https://oeis.org/A194946, https://oeis.org/A195327, https://oeis.org/A002997, https://oeis.org/A191311, https://oeis.org/A090086, https://oeis.org/A007535)	O(log(n))	any number, but only probabilistic (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality testing	(10^8177207−1)/9 (largest known unproved probable prime)	http://factordb.com/index.php?id=1100000002579528773	8177207	http://www.primenumbers.net/prptop/prptop.php
Miller–Rabin probable primality testing (https://primes.utm.edu/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/MillersTest.html, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, https://mathworld.wolfram.com/StrongPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.numericana.com/answer/pseudo.htm#strong, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm, http://ntheory.org/data/spsps.txt, https://sites.google.com/view/strong-pseudoprime, https://sites.google.com/view/bases-strong-pseudoprime, https://oeis.org/A001262, https://oeis.org/A020229, https://oeis.org/A072276, https://oeis.org/A014233, https://oeis.org/A181782, https://oeis.org/A071294, https://oeis.org/A141768, https://oeis.org/A195328, https://oeis.org/A329759, https://oeis.org/A298756)	O(log(n))	any number, but only probabilistic (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality testing	(10^8177207−1)/9 (largest known unproved probable prime)	http://factordb.com/index.php?id=1100000002579528773	8177207	http://www.primenumbers.net/prptop/prptop.php
Baillie–PSW primality testing (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html)	O(log(n))	any number, but only probabilistic (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality testing	(10^8177207−1)/9 (largest known unproved probable prime)	http://factordb.com/index.php?id=1100000002579528773	8177207	http://www.primenumbers.net/prptop/prptop.php
Pépin primality testing (https://en.wikipedia.org/wiki/P%C3%A9pin%27s_test, https://primes.utm.edu/glossary/xpage/PepinsTest.html, https://www.rieselprime.de/ziki/P%C3%A9pin%27s_test, https://mathworld.wolfram.com/PepinsTest.html)	O(log(n))	Fermat numbers (https://en.wikipedia.org/wiki/Fermat_number, https://primes.utm.edu/glossary/xpage/FermatNumber.html, https://www.rieselprime.de/ziki/Fermat_number, https://mathworld.wolfram.com/FermatNumber.html, https://mathworld.wolfram.com/FermatPrime.html, https://pzktupel.de/Primetables/TableFermat.php)	65537 (largest known Fermat prime)	http://factordb.com/index.php?id=65537	5	http://www.fermatsearch.org/
Lucas–Lehmer primality testing (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test, https://www.rieselprime.de/ziki/Lucas-Lehmer_test, https://mathworld.wolfram.com/Lucas-LehmerTest.html, https://primes.utm.edu/notes/proofs/LucasLehmer.html, http://www.numericana.com/answer/primes.htm#lucas-lehmer)	O(log(n))	Mersenne numbers (https://en.wikipedia.org/wiki/Mersenne_prime, https://primes.utm.edu/glossary/xpage/MersenneNumber.html, https://primes.utm.edu/glossary/xpage/Mersennes.html, https://www.rieselprime.de/ziki/Mersenne_number, https://www.rieselprime.de/ziki/Mersenne_prime, https://mathworld.wolfram.com/MersenneNumber.html, https://mathworld.wolfram.com/MersennePrime.html, https://pzktupel.de/Primetables/TableMersenne.php)	2^82589933−1 (largest known Mersenne prime)	http://www.factordb.com/index.php?id=1100000001257221107	24862048	http://www.mersenne.org/primes/
Proth primality testing (https://en.wikipedia.org/wiki/Proth%27s_theorem, https://www.rieselprime.de/ziki/Proth%27s_theorem, https://mathworld.wolfram.com/ProthsTheorem.html, http://www.numericana.com/answer/primes.htm#proth)	O(log(n))	numbers of the form k×2ⁿ+1 with k odd and k < 2ⁿ	10223×2^31172165+1	http://factordb.com/index.php?id=1100000000881266827	9383761	https://primes.utm.edu/primes/lists/all.txt
Lucas–Lehmer–Riesel primality testing (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test)	O(log(n))	numbers of the form k×2ⁿ−1 with k odd and k < 2ⁿ	69×2^19374980−1	http://factordb.com/index.php?id=1100000003714265355	5832452	https://primes.utm.edu/primes/lists/all.txt
Pocklington (N−1) primality testing (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1)	O(log(n))	numbers n such that n−1 can be ≥ 1/2 factored	1963736^1048576+1	http://factordb.com/index.php?id=1100000003905175851	6598776	https://primes.utm.edu/primes/lists/all.txt
Morrison (N+1) primality testing (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2)	O(log(n))	numbers n such that n+1 can be ≥ 1/2 factored	3622×5^7558139−1	http://factordb.com/index.php?id=1100000002920355417	5282917	https://primes.utm.edu/primes/lists/all.txt
elliptic curve (ECPP) primality testing (https://primes.utm.edu/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://primes.utm.edu/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html, https://primes.utm.edu/top20/page.php?id=27)	O(log(n)^4+ε) for some ε > 0	any number	5¹⁰⁴⁸²⁴+104824⁵	http://factordb.com/index.php?id=1100000000213077170&open=prime	73269	https://primes.utm.edu/top20/page.php?id=27
Adleman–Pomerance–Rumely (APR) primality testing (https://en.wikipedia.org/wiki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test, https://www.rieselprime.de/ziki/Adleman%E2%80%93Pomerance%E2%80%93Rumely_primality_test, https://mathworld.wolfram.com/Adleman-Pomerance-RumelyPrimalityTest.html, https://primes.utm.edu/prove/prove4_1.html)	O(log(n)^{log(log(log(n)))})	any number	(none)	(none)	(none)	(none)
Agrawal–Kayal–Saxena (AKS) primality testing (https://en.wikipedia.org/wiki/AKS_primality_test, https://mathworld.wolfram.com/AKSPrimalityTest.html, https://primes.utm.edu/prove/prove4_3.html, http://www.numericana.com/answer/primes.htm#aks, http://cr.yp.to/papers/aks-20030125-retypeset20220327.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_70.pdf))	O(log(n)¹²)	any number	(none)	(none)	(none)	(none)
special number field sieve (SNFS) integer factoring (https://en.wikipedia.org/wiki/Special_number_field_sieve, https://www.rieselprime.de/ziki/Special_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGSNFS, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=snfs&maxrows=100, https://stdkmd.net/nrr/wanted.htm#smallpolynomial)	e^{(1+o(1))×(32/9×log(n))^1/3×log(log(n))^2/3} = L_n(1/3, (32/9)^1/3)	numbers of special forms, e.g. numbers of the form a×bⁿ±c with small a, b, c and large n	2¹¹⁹³−1	http://factordb.com/index.php?id=1000000000000001193	360 (SNFS difficulty)	https://homes.cerias.purdue.edu/~ssw/cun/champ.txt
general number field sieve (GNFS) integer factoring (https://en.wikipedia.org/wiki/General_number_field_sieve, https://www.rieselprime.de/ziki/General_number_field_sieve, https://mathworld.wolfram.com/NumberFieldSieve.html, https://stdkmd.net/nrr/records.htm#BIGGNFS, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=gnfs&maxrows=100, https://stdkmd.net/nrr/wanted.htm#suitableforgnfs)	e^{((64/9)^1/3+o(1))×log(n)^1/3×log(log(n))^2/3} = L_n(1/3, (64/9)^1/3)	any number	cofactor of the Aurifeuillean M-part of 2²²⁴⁶+1	http://factordb.com/index.php?id=1100000000921160018	221 (GNFS difficulty)	https://homes.cerias.purdue.edu/~ssw/cun/champ.txt
trial division (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial)	O(p)	any prime factor	(none)	(none)	(none)	(none)
Pollard (P−1) integer factoring (https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm, https://www.rieselprime.de/ziki/P-1_factorization_method, https://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=p-1&maxrows=100, http://www.numericana.com/answer/factoring.htm#p-1, http://factordb.com/listecm.php?c=2)	O(log(p))	prime factors p such that p−1 is smooth	1991275566641625900337327554338283035474653985743748625294504542099901705952228830784581356237891	http://factordb.com/index.php?id=1100000000466456796&open=ecm	97	http://factordb.com/listecm.php?c=2
Williams (P+1) integer factoring (https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm, https://www.rieselprime.de/ziki/P%2B1_factorization_method, https://mathworld.wolfram.com/WilliamspPlus1FactorizationMethod.html, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=p%2b1&maxrows=100, http://www.numericana.com/answer/factoring.htm#p+1, http://factordb.com/listecm.php?c=3)	O(log(p))	prime factors p such that p+1 is smooth	65457336109138688442516604905896707447825650836160916999487316231912826123193833	http://factordb.com/index.php?id=1100000004126612391&open=ecm	80	http://factordb.com/listecm.php?c=3
Lenstra elliptic-curve (ECM) integer factoring (https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization, https://www.rieselprime.de/ziki/Elliptic_curve_method, https://mathworld.wolfram.com/EllipticCurveFactorizationMethod.html, http://www.numericana.com/answer/factoring.htm#ecm, http://factordb.com/listecm.php?c=1, http://www.loria.fr/~zimmerma/ecmnet/, http://www.loria.fr/~zimmerma/records/ecmnet.html, http://www.loria.fr/~zimmerma/records/factor.html, http://www.loria.fr/~zimmerma/records/top50.html, https://stdkmd.net/nrr/records.htm#largefactorecm, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=ecm&maxrows=100, http://maths-people.anu.edu.au/~brent/factors.html, http://maths-people.anu.edu.au/~brent/ftp/champs.txt, https://www.alpertron.com.ar/ECM.HTM, https://www.alpertron.com.ar/ECMREC.HTM, https://homes.cerias.purdue.edu/~ssw/cun/press/tech.html, https://homes.cerias.purdue.edu/~ssw/cun/press/nontech.html, https://kurtbeschorner.de/ecm-efforts.htm, http://www.rechenkraft.net/yoyo//y_factors_ecm.php, http://www.rechenkraft.net/yoyo/y_status_ecm.php, https://www.alpertron.com.ar/ECM.HTM)	e^{(2^1/2+o(1))×log(n)^1/2×log(log(n))^1/2} = L_p(1/2, 2^1/2)	any prime factor	prime factor of 7³³⁷+1	http://factordb.com/index.php?id=1100000000632146801&open=ecm	83	https://members.loria.fr/PZimmermann/records/top50.html

Thus, for these numbers, we usually use the general purpose tests (https://primes.utm.edu/prove/prove4.html), which do not require factorization of N±1 and can be used for ordinary primes (https://primes.utm.edu/glossary/xpage/OrdinaryPrime.html).

Primes p such that p−1 has many factors	Primes p such that p+1 has many factors
Fermat probable primality test (https://primes.utm.edu/prove/prove2_2.html, https://en.wikipedia.org/wiki/Fermat_primality_test, https://en.wikipedia.org/wiki/Fermat_pseudoprime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Fermat_pseudoprimality_test, https://mathworld.wolfram.com/FermatPseudoprime.html, https://www.numbersaplenty.com/set/Poulet_number/, http://www.numericana.com/answer/pseudo.htm#pseudoprime, http://ntheory.org/data/psps.txt, https://sites.google.com/view/fermat-pseudoprime, https://sites.google.com/view/bases-fermat-pseudoprime, https://oeis.org/A001567, https://oeis.org/A005935, https://oeis.org/A052155, https://oeis.org/A083876, https://oeis.org/A181780, https://oeis.org/A063994, https://oeis.org/A194946, https://oeis.org/A195327, https://oeis.org/A002997, https://oeis.org/A191311, https://oeis.org/A090086, https://oeis.org/A007535)	Lucas probable primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime, https://mathworld.wolfram.com/LucasPseudoprime.html, http://ntheory.org/data/lpsps-baillie.txt, https://oeis.org/A217120)
Miller–Rabin probable primality test (https://primes.utm.edu/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/MillersTest.html, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, https://mathworld.wolfram.com/StrongPseudoprime.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.numericana.com/answer/pseudo.htm#strong, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm, http://ntheory.org/data/spsps.txt, https://sites.google.com/view/strong-pseudoprime, https://sites.google.com/view/bases-strong-pseudoprime, https://oeis.org/A001262, https://oeis.org/A020229, https://oeis.org/A072276, https://oeis.org/A014233, https://oeis.org/A181782, https://oeis.org/A071294, https://oeis.org/A141768, https://oeis.org/A195328, https://oeis.org/A329759, https://oeis.org/A298756)	Strong Lucas probable primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html, http://ntheory.org/data/slpsps-baillie.txt, https://oeis.org/A217255)
Carmichael number (https://oeis.org/A002997, https://en.wikipedia.org/wiki/Carmichael_number, https://primes.utm.edu/glossary/xpage/CarmichaelNumber.html, https://mathworld.wolfram.com/CarmichaelNumber.html, https://www.numbersaplenty.com/set/Carmichael_number/, http://www.numericana.com/answer/modular.htm#carmichael)	Lucas–Carmichael number (https://oeis.org/A006972, https://en.wikipedia.org/wiki/Lucas%E2%80%93Carmichael_number)
Euler's totient function (https://oeis.org/A000010, https://en.wikipedia.org/wiki/Euler%27s_totient_function, https://primes.utm.edu/glossary/xpage/EulersPhi.html, https://mathworld.wolfram.com/TotientFunction.html, http://www.numericana.com/answer/modular.htm#phi), its range is https://oeis.org/A002202, and the even numbers not in its range are https://oeis.org/A005277	Dedekind psi function (https://oeis.org/A001615, https://en.wikipedia.org/wiki/Dedekind_psi_function, https://mathworld.wolfram.com/DedekindFunction.html), its range is https://oeis.org/A203444, and the even numbers not in its range are https://oeis.org/A307055
Pépin primality test (https://en.wikipedia.org/wiki/P%C3%A9pin%27s_test, https://primes.utm.edu/glossary/xpage/PepinsTest.html, https://www.rieselprime.de/ziki/P%C3%A9pin%27s_test, https://mathworld.wolfram.com/PepinsTest.html) for Fermat numbers (https://en.wikipedia.org/wiki/Fermat_number, https://primes.utm.edu/glossary/xpage/FermatNumber.html, https://www.rieselprime.de/ziki/Fermat_number, https://mathworld.wolfram.com/FermatNumber.html, https://mathworld.wolfram.com/FermatPrime.html, https://pzktupel.de/Primetables/TableFermat.php), i.e. numbers of the form 2ⁿ+1 (https://oeis.org/A000051), if 2ⁿ+1 is prime, then n must be power of 2, such numbers are https://oeis.org/A000215, and such primes are https://oeis.org/A019434	Lucas–Lehmer primality test (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test, https://www.rieselprime.de/ziki/Lucas-Lehmer_test, https://mathworld.wolfram.com/Lucas-LehmerTest.html, https://primes.utm.edu/notes/proofs/LucasLehmer.html, http://www.numericana.com/answer/primes.htm#lucas-lehmer) for Mersenne numbers (https://en.wikipedia.org/wiki/Mersenne_prime, https://primes.utm.edu/glossary/xpage/MersenneNumber.html, https://primes.utm.edu/glossary/xpage/Mersennes.html, https://www.rieselprime.de/ziki/Mersenne_number, https://www.rieselprime.de/ziki/Mersenne_prime, https://mathworld.wolfram.com/MersenneNumber.html, https://mathworld.wolfram.com/MersennePrime.html, https://pzktupel.de/Primetables/TableMersenne.php), i.e. numbers of the form 2ⁿ−1 (https://oeis.org/A000225), if 2ⁿ−1 is prime, then n must be prime, such numbers are https://oeis.org/A001348, and such primes are https://oeis.org/A000668
Pépin primality test numbers: https://oeis.org/A060377	Lucas–Lehmer primality test numbers: https://oeis.org/A003010
Residues of Pépin primality test for Fermat numbers: https://oeis.org/A152153	Residues of Lucas–Lehmer primality test for Mersenne numbers: https://oeis.org/A095847
Possible bases for Pépin primality test for Fermat numbers (the original base for Pépin primality test is 3): https://oeis.org/A129802	Possible starting values for Lucas–Lehmer primality test for Mersenne numbers (the original starting value for Lucas–Lehmer primality test is 4): https://oeis.org/A018844
Proth primality test (https://en.wikipedia.org/wiki/Proth%27s_theorem, https://www.rieselprime.de/ziki/Proth%27s_theorem, https://mathworld.wolfram.com/ProthsTheorem.html, http://www.numericana.com/answer/primes.htm#proth) for numbers of the form k×2ⁿ+1 with k odd and k < 2ⁿ, such numbers are called "Proth numbers" (https://en.wikipedia.org/wiki/Proth_prime, https://primes.utm.edu/glossary/xpage/ProthPrime.html, https://www.rieselprime.de/ziki/Proth_prime, https://mathworld.wolfram.com/ProthNumber.html, https://www.numbersaplenty.com/set/Proth_number/, https://pzktupel.de/Primetables/TableProth1.php, https://pzktupel.de/Primetables/TableProth2.php, https://primes.utm.edu/top20/page.php?id=66, https://www.primegrid.com/forum_thread.php?id=2665, https://www.primegrid.com/stats_pps_llr.php, https://www.primegrid.com/stats_ppse_llr.php, https://www.primegrid.com/stats_mega_llr.php), and such primes are called "Proth primes", such numbers are https://oeis.org/A080075, and such primes are https://oeis.org/A080076	Lucas–Lehmer–Riesel primality test (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test) for numbers of the form k×2ⁿ−1 with k odd and k < 2ⁿ, such numbers are called "Proth numbers of the second kind" (https://www.rieselprime.de/ziki/Riesel_prime, https://pzktupel.de/Primetables/TableRiesel1.php, https://pzktupel.de/Primetables/TableRiesel2.php), and such primes are called "Proth primes of the second kind", such numbers are https://oeis.org/A112714, and such primes are https://oeis.org/A112715
Pocklington N−1 primality test (https://primes.utm.edu/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, https://en.wikipedia.org/wiki/Pocklington_primality_test, https://www.rieselprime.de/ziki/Pocklington%27s_theorem, https://mathworld.wolfram.com/PocklingtonsTheorem.html, https://stdkmd.net/nrr/pock/, http://factordb.com/nmoverview.php?method=1) for numbers N such that N−1 can be ≥ 1/2 factored	Morrison N+1 primality test (https://primes.utm.edu/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://factordb.com/nmoverview.php?method=2) for numbers N such that N+1 can be ≥ 1/2 factored
List of primes of the form k×2ⁿ+1 with odd k (http://www.prothsearch.com/riesel1.html, http://www.prothsearch.com/riesel1a.html, http://www.prothsearch.com/riesel1b.html, http://www.prothsearch.com/riesel1c.html, http://irvinemclean.com/maths/sierpin.htm, http://irvinemclean.com/maths/sierpin2.htm, http://irvinemclean.com/maths/sierpin3.htm, https://www.rieselprime.de/default.htm, https://www.rieselprime.de/ziki/Proth_prime, https://sites.google.com/view/proth-primes)	List of primes of the form k×2ⁿ−1 with odd k (http://www.prothsearch.com/riesel2.html, https://web.archive.org/web/20210715115849/http://www.15k.org/riesellist.html, https://web.archive.org/web/20210715164816/http://www.15k.org/Summary00300.htm, https://web.archive.org/web/20210715164824/http://www.15k.org/Summary02000.htm, https://web.archive.org/web/20210715164823/http://www.15k.org/Summary04000.htm, https://web.archive.org/web/20210715164815/http://www.15k.org/Summary06000.htm, https://web.archive.org/web/20210715164832/http://www.15k.org/Summary08000.htm, http://www.noprimeleftbehind.net/gary/primes-kx2n-1-001.htm, http://www.noprimeleftbehind.net/gary/Rieselprimes-ranges.htm, https://www.rieselprime.de/default.htm, https://www.rieselprime.de/ziki/Riesel_prime, https://sites.google.com/view/proth-primes)
Sierpiński problem (http://www.prothsearch.com/sierp.html, http://www.primegrid.com/forum_thread.php?id=1647, http://www.primegrid.com/forum_thread.php?id=972, http://www.primegrid.com/forum_thread.php?id=1750, http://www.primegrid.com/forum_thread.php?id=5758, http://www.primegrid.com/stats_sob_llr.php, http://www.primegrid.com/stats_psp_llr.php, http://www.primegrid.com/stats_esp_llr.php, https://web.archive.org/web/20160405211049/http://www.seventeenorbust.com/, https://en.wikipedia.org/wiki/Sierpi%C5%84ski_number, https://primes.utm.edu/glossary/xpage/SierpinskiNumber.html, https://www.rieselprime.de/ziki/Sierpi%C5%84ski_problem, https://www.rieselprime.de/ziki/Proth_2_Sierpinski, https://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html, https://en.wikipedia.org/wiki/Seventeen_or_Bust, https://www.rieselprime.de/ziki/Seventeen_or_Bust, https://web.archive.org/web/20190929190947/https://primes.utm.edu/glossary/xpage/ColbertNumber.html, https://mathworld.wolfram.com/ColbertNumber.html, http://www.numericana.com/answer/primes.htm#sierpinski, http://www.bitman.name/math/article/204 (in Italian), https://oeis.org/A076336), finding and proving the smallest odd k such that k×2ⁿ+1 is composite for all n ≥ 1, the smallest such k is conjectured to be 78557, such k are called Sierpiński numbers	Riesel problem (http://www.prothsearch.com/rieselprob.html, http://www.primegrid.com/forum_thread.php?id=1731, http://www.primegrid.com/stats_trp_llr.php, https://web.archive.org/web/20061021153313/http://stats.rieselsieve.com//queue.php, https://en.wikipedia.org/wiki/Riesel_number, https://primes.utm.edu/glossary/xpage/RieselNumber.html, https://www.rieselprime.de/ziki/Riesel_problem, https://www.rieselprime.de/ziki/Riesel_2_Riesel, https://mathworld.wolfram.com/RieselNumber.html, http://www.bitman.name/math/article/203 (in Italian), https://oeis.org/A076337, https://oeis.org/A101036), finding and proving the smallest odd k such that k×2ⁿ−1 is composite for all n ≥ 1, the smallest such k is conjectured to be 509203, such k are called Riesel numbers
Smallest n such that k×2ⁿ+1 is prime (https://oeis.org/A078680, https://oeis.org/A078683 (corresponding primes), https://oeis.org/A033809 (odd k), https://oeis.org/A040076 (n = 0 allowed), https://oeis.org/A225721 (n = 0 allowed), https://oeis.org/A050921 (n = 0 allowed, corresponding primes), https://oeis.org/A046067 (odd k, n = 0 allowed), https://oeis.org/A057025 (odd k, n = 0 allowed, corresponding primes), https://oeis.org/A057192 (prime k, n = 0 allowed), https://oeis.org/A057247 (prime k, corresponding primes))	Smallest n such that k×2ⁿ−1 is prime (https://oeis.org/A050412, https://oeis.org/A052333 (corresponding primes), https://oeis.org/A108129 (odd k), https://oeis.org/A040081 (n = 0 allowed), https://oeis.org/A038699 (n = 0 allowed, corresponding primes), https://oeis.org/A046069 (odd k, n = 0 allowed), https://oeis.org/A057026 (odd k, n = 0 allowed, corresponding primes), https://oeis.org/A128979 (prime k), https://oeis.org/A101050 (prime k, n = 0 allowed))
dual Sierpiński problem (http://www.kurims.kyoto-u.ac.jp/EMIS/journals/INTEGERS/papers/i61/i61.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_1.pdf), https://www.rechenkraft.net/wiki/Five_or_Bust, https://oeis.org/A076336/a076336c.html, http://www.mit.edu/~kenta/three/prime/dual-sierpinski/ezgxggdm/dualsierp-excerpt.txt, http://mit.edu/kenta/www/three/prime/dual-sierpinski/ezgxggdm/dualsierp.txt.gz, https://mersenneforum.org/showthread.php?t=10761)	dual Riesel problem (https://mersenneforum.org/showthread.php?t=6545)
Smallest n such that 2ⁿ+k is prime for odd k (https://oeis.org/A067760, https://oeis.org/A123252 (corresponding primes), https://oeis.org/A094076 (prime k, n = 0 allowed), https://oeis.org/A139758 (prime k, n = 0 allowed, corresponding primes))	Smallest n such that 2ⁿ−k is prime for odd k (https://oeis.org/A096502, https://oeis.org/A096822 (corresponding primes), https://oeis.org/A101462 (prime k))
Generalized Sierpiński problems to bases b > 2 (http://www.noprimeleftbehind.net/crus/Sierp-conjectures.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Sierp-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats/all_ck_sierpinski.txt, https://www.utm.edu/staff/caldwell/preprints/2to100.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_3.pdf), http://www.bitman.name/math/article/1259 (in Italian), https://oeis.org/A123159), finding and proving the smallest k such that k×bⁿ+1 is composite for all n ≥ 1	Generalized Riesel problems to bases b > 2 (http://www.noprimeleftbehind.net/crus/Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjectures-powers2.htm, http://www.noprimeleftbehind.net/crus/Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/vstats/all_ck_riesel.txt, https://oeis.org/A273987), finding and proving the smallest k such that k×bⁿ−1 is composite for all n ≥ 1
Pierpont prime (class 1− prime) (https://en.wikipedia.org/wiki/Pierpont_prime, https://primes.utm.edu/glossary/xpage/PierpontPrime.html, https://mathworld.wolfram.com/PierpontPrime.html, https://oeis.org/A005109)	Pierpont prime of the second kind (class 1+ prime) (https://oeis.org/A005105)
Pollard P−1 integer factorization method (https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm, https://www.rieselprime.de/ziki/P-1_factorization_method, https://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=p-1&maxrows=100, http://www.numericana.com/answer/factoring.htm#p-1, http://factordb.com/listecm.php?c=2)	Williams P+1 integer factorization method (https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm, https://www.rieselprime.de/ziki/P%2B1_factorization_method, https://mathworld.wolfram.com/WilliamspPlus1FactorizationMethod.html, http://mklasson.com/factors/viewlog.php?hide_algebraic=true&sort=2&order=desc&method=p%2b1&maxrows=100, http://www.numericana.com/answer/factoring.htm#p+1, http://factordb.com/listecm.php?c=3)

All these numbers are strong probable primes (https://en.wikipedia.org/wiki/Strong_pseudoprime, https://primes.utm.edu/glossary/xpage/StrongPRP.html, https://mathworld.wolfram.com/StrongPseudoprime.html) to bases 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 (see https://oeis.org/A014233 and https://oeis.org/A141768 and https://oeis.org/A001262 and https://oeis.org/A074773 and http://ntheory.org/data/psps.txt), and strong Lucas probable primes (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html) with parameters (P, Q) defined by Selfridge's Method A (see https://oeis.org/A217255 and http://ntheory.org/data/slpsps-baillie.txt), and trial factored (https://en.wikipedia.org/wiki/Trial_division, https://primes.utm.edu/glossary/xpage/TrialDivision.html, https://www.rieselprime.de/ziki/Trial_factoring, https://mathworld.wolfram.com/TrialDivision.html, http://www.numericana.com/answer/factoring.htm#trial) to 10¹⁶ (thus, all these numbers are Baillie–PSW probable primes (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html)), and since all of them are > 10²⁵⁰⁰⁰, thus the property that they are in fact composite is less than 10⁻²⁰⁰⁰ (but still not zero!), see https://primes.utm.edu/notes/prp_prob.html and https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-1989-0982368-4/S0025-5718-1989-0982368-4.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_22.pdf) (bases 11, 16, 22, 30 have no unsolved families but have unproven probable primes, thus, we can 99.999999...999999% (with >2000 9's) say that the minimal sets for bases 11, 16, 22, 30 are these four sets, but we still cannot 100% say this)

A reference of many types of pseudoprimes: http://ntheory.org/pseudoprimes.html; also a reference of data for all base 2 Fermat pseudoprimes < 2⁶⁴: http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html; also examples of strong pseudoprimes to many bases: https://www.ams.org/journals/mcom/1993-61-204/S0025-5718-1993-1192971-8/S0025-5718-1993-1192971-8.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_41.pdf), https://arxiv.org/pdf/1207.0063.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_42.pdf), https://arxiv.org/pdf/1509.00864.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_43.pdf), https://www.sciencedirect.com/science/article/pii/S0747717185710425?via%3Dihub (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_44.pdf), https://primes.utm.edu/curios/page.php?number_id=4265, https://primes.utm.edu/prove/prove2_3.html, https://faculty.lynchburg.edu/~nicely/misc/mpzspsp.html, http://factordb.com/prooffailed.php, https://oeis.org/A072276, https://oeis.org/A056915, https://oeis.org/A074773

If 57₆₂₆₆₈ (base 11) is in fact composite, then 5{7} will be an additional unsolved family for base 11.
If C5₂₃₇₅₅C (base 13) is in fact composite, then C{5}C will be an additional unsolved family for base 13.
If 80₃₂₀₁₇111 (base 13) is in fact composite, then 8{0}111 will be an additional unsolved family for base 13.
If 95₁₉₇₄₂₀ (base 13) is in fact composite, then 9{5} will be an additional unsolved family for base 13.
If DB₃₂₂₃₄ (base 16) is in fact composite, then D{B} will be an additional unsolved family for base 16.
If 4₇₂₇₈₅DD (base 16) is in fact composite, then {4}DD will be an additional unsolved family for base 16.
If 3₁₁₆₁₃₇AF (base 16) is in fact composite, then {3}AF will be an additional unsolved family for base 16.
If BK₂₂₀₀₁5 (base 22) is in fact composite, then B{K}5 will be an additional unsolved family for base 22.
If 5₁₉₃₉₁6F (base 26) is in fact composite, then {5}6F will be an additional unsolved family for base 26.
If 7₂₀₂₇₉OL (base 26) is in fact composite, then {7}OL will be an additional unsolved family for base 26.
If LD0₂₀₉₇₅7 (base 26) is in fact composite, then LD{0}7 will be an additional unsolved family for base 26.
If 6K₂₃₃₀₀5 (base 26) is in fact composite, then 6{K}5 will be an additional unsolved family for base 26.
If J0₄₄₃₀₃KCB (base 26) is in fact composite, then J{0}KCB will be an additional unsolved family for base 26.
If M0₆₁₁₈₆2BB (base 26) is in fact composite, then M{0}2BB will be an additional unsolved family for base 26.
If N6₂₄₀₅₁LR (base 28) is in fact composite, then N{6}LR will be an additional unsolved family for base 28.
If 5OA₃₁₂₃₈F (base 28) is in fact composite, then 5O{A}F will be an additional unsolved family for base 28 (unless a prime in the family O{A}F is known, since the family 5O{A}F is covered by the unsolved family O{A}F (if the prime in the family 5O{A}F has longer length than the prime in the family O{A}F) (i.e. the family O{A}F is a subfamily of the family 5O{A}F), and there is still a possibility that the smallest prime in the family 5O{A}F has longer length than the smallest prime in the family O{A}F, thus we still cannot definitely say that there are 25529 minimal primes in base 28 even if we assume the heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://primes.utm.edu/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html, http://www.utm.edu/~caldwell/preprints/Heuristics.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_112.pdf)) that all unsolved families have a prime, this is reasonable, references: https://primes.utm.edu/mersenne/heuristic.html, https://primes.utm.edu/notes/faq/NextMersenne.html, https://web.archive.org/web/20100628035147/http://www.math.niu.edu/~rusin/known-math/98/exp_primes).
If O4O₉₄₅₃₅9 (base 28) is in fact composite, then O4{O}9 will be an additional unsolved family for base 28.
If I0₂₄₆₀₈D (base 30) is in fact composite, then I{0}D will be an additional unsolved family for base 30.
If 7K₂₆₅₆₇Z (base 36) is in fact composite, then 7{K}Z will be an additional unsolved family for base 36.
If S0₇₅₀₀₇8H (base 36) is in fact composite, then S{0}8H will be an additional unsolved family for base 36.
If P₈₁₉₉₃SZ (base 36) is in fact composite, then {P}SZ will be an additional unsolved family for base 36.

For the files in this page:

File "unprovenPRP b": The unproven probable primes which are minimal primes in base b (assuming their primality), expressed as base b strings with x(y^n)z format (which in the README files it is denoted as "xy_nz") (y^n means n copies of y, e.g. 34(5^6)78 is 3455555578)
File "primoinput b n": The input file for Primo for the nth minimal prime in base b (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/Primo309) (local copy from factordb (http://factordb.com/, https://www.rieselprime.de/ziki/Factoring_Database)), they should be renamed to ".in" files before inputting to Primo, e.g. file "primoinput11_1068" is the input file for Primo for the 1068th minimal prime in base 11, i.e. the input file for Primo for the probable prime 57₆₂₆₆₈ in base 11, which equals the probable prime (57×11⁶²⁶⁶⁸−7)/10. (Note: There is no input file for Primo for the probable prime 95₁₉₇₄₂₀ in base 13 (which equals the probable prime (113×13¹⁹⁷⁴²⁰−5)/12) since this probable prime is too large (>10¹⁴⁹⁹⁹⁹) to be PRP-tested in factordb, and factordb does not have input file for Primo for numbers with status (http://factordb.com/status.html, http://factordb.com/distribution.php) "U" (i.e. in http://factordb.com/listtype.php?t=2), factordb only has input file for Primo for numbers with status "PRP" (i.e. in http://factordb.com/listtype.php?t=1))

Latest commit

Git stats

Files

README.md