Primality of these probable primes (https://en.wikipedia.org/wiki/Probable_prime, https://primes.utm.edu/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, http://factordb.com/listtype.php?t=1) in the minimal sets for bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 26, 28, 30, 36 (the solved or near-solved bases, i.e. the bases b with ≤ 6 unsolved families) are not certificated yet (technically, probable primality tests (https://en.wikipedia.org/wiki/Probabilistic_algorithm) such as Miller–Rabin primality test (https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://primes.utm.edu/glossary/xpage/MillersTest.html, https://www.rieselprime.de/ziki/Miller-Rabin_pseudoprimality_test, https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html, http://www.numericana.com/answer/pseudo.htm#rabin, http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm) and Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) are used for these numbers (and thus these numbers are only probable primes and not definitely primes (https://en.wikipedia.org/wiki/Provable_prime, https://stdkmd.net/nrr/records.htm#primenumbers, http://factordb.com/listtype.php?t=4), i.e. they might be pseudoprimes (https://en.wikipedia.org/wiki/Pseudoprime, https://primes.utm.edu/glossary/xpage/Pseudoprime.html, https://www.rieselprime.de/ziki/Pseudoprime, https://mathworld.wolfram.com/Pseudoprime.html, http://www.numericana.com/answer/pseudo.htm)), because of their sizes and neither N−1 (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) nor N+1 (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) can be ≥ 1/4 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) (i.e. they are ordinary primes (https://primes.utm.edu/glossary/xpage/OrdinaryPrime.html)), all known primality tests (https://en.wikipedia.org/wiki/Primality_test, https://www.rieselprime.de/ziki/Primality_test, https://mathworld.wolfram.com/PrimalityTest.html) run far too slowly (the CPU time (https://en.wikipedia.org/wiki/CPU_time) is longer than the life expectancy of human (https://en.wikipedia.org/wiki/Life_expectancy) for numbers > 10100000, and longer than the age of the universe (https://en.wikipedia.org/wiki/Age_of_the_universe) for numbers > 10500000, and longer than one quettasecond (https://en.wikipedia.org/wiki/Quetta-) for numbers > 103000000, even if we can do 109 bitwise operations (https://en.wikipedia.org/wiki/Bitwise_operation) per second (https://en.wikipedia.org/wiki/Second)) to run on these numbers, the only known primality test with polynomial time (https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time, https://mathworld.wolfram.com/PolynomialTime.html) of the number of digits is Agrawal–Kayal–Saxena primality test (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)), but it has time complexity (https://en.wikipedia.org/wiki/Time_complexity) O(log(n)12) (where 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), 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)) and if we can do 109 bitwise operations (https://en.wikipedia.org/wiki/Bitwise_operation) per second (https://en.wikipedia.org/wiki/Second), use this test to prove the primality of a 5000-digit (in decimal) prime needs 5.422859049×1039 seconds (https://en.wikipedia.org/wiki/Second), or 1.719577324×1032 years (https://en.wikipedia.org/wiki/Year), much longer than the age of the universe (https://en.wikipedia.org/wiki/Age_of_the_universe), thus to do this test is still impractically, also a near-polynomial time (although not completely polynomial time) primality test, Adleman–Pomerance–Rumely primality test (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), which has time complexity O(log(n)log(log(log(n)))) and also too large), all of these probable primes are > 1025000, if they are in fact primes, then they are minimal primes to the corresponding bases.
If we want to use the classical tests (https://primes.utm.edu/prove/prove3.html) to prove the primality of a large probable prime N, then we must factor N−1 or N+1 to the factored part ≥ 1/4, and except 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) with the primes up to certain limit (say 1016) and the algebra factors (https://en.wikipedia.org/w/index.php?title=Factorization&oldid=1143370673#Factoring_other_polynomials, https://mathworld.wolfram.com/PolynomialFactorization.html, http://www.numericana.com/answer/factoring.htm#special, https://stdkmd.net/nrr/repunit/repunitnote.htm, https://stdkmd.net/nrr/1/10004.htm#about_algebraic, https://stdkmd.net/nrr/1/10008.htm#about_algebraic, https://stdkmd.net/nrr/1/13333.htm#about_algebraic, https://stdkmd.net/nrr/4/40001.htm#about_algebraic, https://stdkmd.net/nrr/5/53333.htm#about_algebraic, https://stdkmd.net/nrr/5/54444.htm#about_algebraic, https://stdkmd.net/nrr/5/55552.htm#about_algebraic, https://stdkmd.net/nrr/7/79999.htm#about_algebraic, https://stdkmd.net/nrr/8/83333.htm#about_algebraic, https://stdkmd.net/nrr/8/88889.htm#about_algebraic, https://stdkmd.net/nrr/8/89999.htm#about_algebraic, https://stdkmd.net/nrr/9/99991.htm#about_algebraic, https://stdkmd.net/nrr/9/99992.htm#about_algebraic, https://brnikat.com/nums/cullen_woodall/algebraic.txt, https://www.numberempire.com/factoringcalculator.php, https://www.emathhelp.net/calculators/algebra-2/factoring-calculator/) (e.g. difference-of-two-squares factorization (https://en.wikipedia.org/wiki/Difference_of_two_squares), sum/difference-of-two-cubes factorization (https://en.wikipedia.org/wiki/Sum_of_two_cubes), difference-of-two-nth-powers factorization with n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html), sum/difference-of-two-nth-powers factorization with odd n > 1 (https://en.wikipedia.org/wiki/Binomial_number, https://mathworld.wolfram.com/BinomialNumber.html), Aurifeuillian factorization (https://en.wikipedia.org/wiki/Aurifeuillean_factorization, https://www.rieselprime.de/ziki/Aurifeuillian_factor, https://mathworld.wolfram.com/AurifeuilleanFactorization.html, http://www.numericana.com/answer/numbers.htm#aurifeuille, http://pagesperso-orange.fr/colin.barker/lpa/cycl_fac.htm, http://list.seqfan.eu/oldermail/seqfan/2017-March/017363.html, http://myfactorcollection.mooo.com:8090/source/cyclo.cpp, http://myfactorcollection.mooo.com:8090/LCD_2_199, http://myfactorcollection.mooo.com:8090/LCD_2_998, https://stdkmd.net/nrr/repunit/repunitnote.htm#aurifeuillean, https://www.unshlump.com/hcn/aurif.html) of x4+4×y4 or x6+27×y6, and the algebra factors of the Cunningham number (https://en.wikipedia.org/wiki/Cunningham_number, https://mathworld.wolfram.com/CunninghamNumber.html, https://www.numbersaplenty.com/set/Cunningham_number/, https://en.wikipedia.org/wiki/Cunningham_Project, https://primes.utm.edu/glossary/xpage/CunninghamProject.html, https://www.rieselprime.de/ziki/Cunningham_project, https://homes.cerias.purdue.edu/~ssw/cun/index.html, https://maths-people.anu.edu.au/~brent/factors.html, https://web.archive.org/web/20190315214330/http://cage.ugent.be/~jdemeyer/cunningham/, http://myfactors.mooo.com/, https://doi.org/10.1090/conm/022, https://www.mersenneforum.org/attachment.php?attachmentid=7727&d=1330555980 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_7.pdf), https://homes.cerias.purdue.edu/~ssw/cun/mine.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_6.pdf), http://homes.cerias.purdue.edu/~ssw/cun1.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_71.pdf)) bn±1 (see https://stdkmd.net/nrr/repunit/repunitnote.htm and https://brnikat.com/nums/cullen_woodall/algebraic.txt)), we can use the elliptic-curve factorization method (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://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) (elliptic-curve factorization method need to calculate the group order, for the tools to calculate the group order, see http://myfactorcollection.mooo.com:8090/calculators.html (section "Group Order") and http://factordb.com/groupcalc.php and https://www.mersenneforum.org/showthread.php?t=14184 (a Magma script, you can use online Magma calculator (http://magma.maths.usyd.edu.au/calc/) to run)) or the Pollard P−1 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://www.numericana.com/answer/factoring.htm#p-1, http://factordb.com/listecm.php?c=2) or the Williams P+1 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://www.numericana.com/answer/factoring.htm#p+1, http://factordb.com/listecm.php?c=3) or the special number field sieve (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, https://stdkmd.net/nrr/wanted.htm#smallpolynomial) or the general number field sieve (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, https://stdkmd.net/nrr/wanted.htm#suitableforgnfs), to factor these numbers (see http://www.numericana.com/answer/factoring.htm), elliptic-curve factorization method and Pollard P−1 method and Williams P+1 method are methods which find a non-large (say between 1020 and 1090) prime factor, an elliptic-curve factorization program is GMP-ECM (https://web.archive.org/web/20210803045418/https://gforge.inria.fr/projects/ecm, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/ecm704dev-svn2990-win64, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/ecm704dev-svn2990-linux64, https://www.rieselprime.de/ziki/GMP-ECM), special number field sieve and general number field sieve are methods which factor a large number (say between 10100 and 10400), special number field sieve can only be used on a number of special form, e.g. numbers of the form a×bn±c with small a, b, c and large n, and cannot be used for general numbers such as a×n!±c and a×p#±c (where ! is the factorial (https://en.wikipedia.org/wiki/Factorial, https://primes.utm.edu/glossary/xpage/Factorial.html, https://www.rieselprime.de/ziki/Factorial_number, https://mathworld.wolfram.com/Factorial.html), # is the primorial (https://en.wikipedia.org/wiki/Primorial, https://primes.utm.edu/glossary/xpage/Primorial.html, https://mathworld.wolfram.com/Primorial.html)) with small a, c and (large n or large prime p), the difficulty (https://www.rieselprime.de/ziki/SNFS_polynomial_selection) of such a number is equivalent to general number field sieve for a general number around b3×n/2, thus, for the Cunningham number bn±1, if the primitive part (i.e. Φn(b) for bn−1 or Φ2×n(b) for bn+1, where Φ is the cyclotomic polynomial (https://en.wikipedia.org/wiki/Cyclotomic_polynomial, https://mathworld.wolfram.com/CyclotomicPolynomial.html, http://www.numericana.com/answer/polynomial.htm#cyclotomic, https://stdkmd.net/nrr/repunit/repunitnote.htm#cyclotomic)) is > 1/3 factored (by the elliptic-curve factorization method or the Pollard P−1 method or the Williams P+1 method), then general number field sieve is usually used for the unfactored part, if the primitive part (i.e. Φn(b) for bn−1 or Φ2×n(b) for bn+1, where Φ is the cyclotomic polynomial (https://en.wikipedia.org/wiki/Cyclotomic_polynomial, https://mathworld.wolfram.com/CyclotomicPolynomial.html, http://www.numericana.com/answer/polynomial.htm#cyclotomic, https://stdkmd.net/nrr/repunit/repunitnote.htm#cyclotomic)) is < 1/3 factored (by the elliptic-curve factorization method or the Pollard P−1 method or the Williams P+1 method), then special number field sieve is usually used for the unfactored part, for more information see https://escatter11.fullerton.edu/nfs/numbers.php (the status of numbers in NFS@HOME (http://escatter11.fullerton.edu/nfs/, https://en.wikipedia.org/wiki/NFS@Home)), for the calculator for special number field sieve and general number field sieve, see http://myfactorcollection.mooo.com:8090/calculators.html (section ".poly Maker"), a general number field sieve program is GGNFS (http://sourceforge.net/projects/ggnfs, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/GGNFS), also a (special or general) number field program is CADO-NFS (https://web.archive.org/web/20210506173015/http://cado-nfs.gforge.inria.fr/index.html, https://www.rieselprime.de/ziki/CADO-NFS, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/cado-nfs-2.3.0), however, all these factorization algorithms (https://en.wikipedia.org/wiki/Algorithm, https://www.rieselprime.de/ziki/Algorithm) take long time, i.e. they cannot be done in polynomial time (https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time, https://mathworld.wolfram.com/PolynomialTime.html), and there are many OEIS sequences which need factors (see https://oeis.org/wiki/OEIS_sequences_needing_factors) (unlike primality proving, when the numbers are sufficiently large, no efficient, non-quantum (https://en.wikipedia.org/wiki/Quantum_computer) integer factorization algorithm is known), i.e. integer factorization may be P-complete (https://en.wikipedia.org/wiki/P-complete) and NP-complete (https://en.wikipedia.org/wiki/NP-complete, https://mathworld.wolfram.com/NP-CompleteProblem.html) and NP-hard (https://en.wikipedia.org/wiki/NP-hard, https://mathworld.wolfram.com/NP-HardProblem.html) (thus, factor a large integer is much harder than determining whether an integer of the same size is prime (determining whether an integer is prime and factor an integer are two completely different problems, we can quickly use Fermat primality test (https://en.wikipedia.org/wiki/Fermat_primality_test, https://mathworld.wolfram.com/FermatCompositenessTest.html, https://www.rieselprime.de/ziki/Fermat_pseudoprimality_test, https://en.wikipedia.org/wiki/Fermat%27s_little_theorem, https://primes.utm.edu/glossary/xpage/FermatsLittleTheorem.html, https://mathworld.wolfram.com/FermatsLittleTheorem.html, https://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html, http://www.numericana.com/answer/modular.htm#fermat, https://primes.utm.edu/prove/prove2_2.html) to prove that an integer is composite, although the most ancient 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) and sieve of Eratosthenes (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes, https://primes.utm.edu/glossary/xpage/SieveOfEratosthenes.html, https://www.rieselprime.de/ziki/Sieve_of_Eratosthenes, https://mathworld.wolfram.com/SieveofEratosthenes.html) can solving these two problems simultaneously), there are many numbers with 500 digits to 10000 digits which are known to be composite but do not have any known factors other than 1 and themselves). However, it has not been proven that no efficient algorithm exists (this is indeed an unsolved problem in computer science (https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science)). The presumed difficulty (https://en.wikipedia.org/wiki/Computational_hardness_assumption) of this problem is at the heart of widely used algorithms in cryptography (https://en.wikipedia.org/wiki/Cryptography, https://mathworld.wolfram.com/Cryptography.html) such as RSA (https://en.wikipedia.org/wiki/RSA_(cryptosystem), https://primes.utm.edu/glossary/xpage/RSA.html, https://mathworld.wolfram.com/RSAEncryption.html, https://web.archive.org/web/20061209135708/http://www.rsasecurity.com/rsalabs/node.asp?id=2093), there are many large semiprimes (https://en.wikipedia.org/wiki/Semiprime, https://primes.utm.edu/glossary/xpage/Semiprime.html, https://mathworld.wolfram.com/Semiprime.html, https://www.numbersaplenty.com/set/semiprime/), called RSA numbers (https://en.wikipedia.org/wiki/RSA_numbers, https://primes.utm.edu/glossary/xpage/RSAExample.html, https://mathworld.wolfram.com/RSANumber.html), which are very hard to factor and are part of the RSA Factoring Challenge (https://en.wikipedia.org/wiki/RSA_Factoring_Challenge). Besides, integer factorization can be used for public-key cryptography (https://en.wikipedia.org/wiki/Public-key_cryptography, https://primes.utm.edu/glossary/xpage/PublicKey.html, https://mathworld.wolfram.com/Public-KeyCryptography.html) is because it has no known polynomial time algorithm. Many areas of mathematics and computer science have been brought to bear on the problem, including elliptic curves (https://en.wikipedia.org/wiki/Elliptic_curve, https://mathworld.wolfram.com/EllipticCurve.html, http://www.numericana.com/answer/modularity.htm#elliptic), algebraic number theory (https://en.wikipedia.org/wiki/Algebraic_number_theory, https://mathworld.wolfram.com/AlgebraicNumberTheory.html), and quantum computing (https://en.wikipedia.org/wiki/Quantum_computing)), and hence to do this is impractically.
Our data assumes that a number > 1025000 which has passed the 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/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) to all prime bases p < 64 and has passed the Baillie–PSW primality test (https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test, https://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) and has 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 1016 is in fact prime, since in some cases (e.g. b = 11) a candidate for minimal prime base b is too large to be proven prime rigorously, this candidate for minimal prime base 11 has 65263 decimal digits, while the top record ordinary prime (https://primes.utm.edu/glossary/xpage/OrdinaryPrime.html) (i.e. neither N−1 (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) nor N+1 (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) can be ≥ 1/4 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)) has 57125 decimal digits (the entry of this prime in top definitely primes is https://primes.utm.edu/primes/page.php?id=134371), see https://primes.utm.edu/top20/page.php?id=27, and 65263 > 57125), however, if we assume a number which has passed the Fermat primality tests (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) to many bases is in fact prime, our list for base 16 minimal primes would wrongly include the composites 1563 (its value is (4×1663−1)/3) and 8536 (its value is (25×1636−1)/3), and our list for base 9 minimal primes would wrongly include the composite 113 (its value is (913−1)/8) (and hence would wrongly exclude the prime 56136, since this prime has 113 as subsequence (https://en.wikipedia.org/wiki/Subsequence, https://mathworld.wolfram.com/Subsequence.html)), although their corresponding families (1{5} in base 16, 8{5} in base 16, {1} in base 9, respectively) can be ruled out as only contain composite numbers (only count the numbers > b), and our data will be wrong for these bases, see https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test#The_danger_of_relying_only_on_Fermat_tests (only run Fermat tests are dangerous).
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))2, also, when the number n to be tested is small, trying all bases b < 2×(ln(n))2 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 | 112 |
| 5 | 781 | 11 × 71 |
| 6 | 217 | 7 × 31 |
| 7 | 25 | 52 |
| 10 | 9 | 32 |
| 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 ≤ 101100, 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/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 < 264 pass the Baillie–PSW probable prime test (see http://ntheory.org/pseudoprimes.html and https://faculty.lynchburg.edu/~nicely/misc/bpsw.html).
1563 (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 2127−1, thus 1/3 of the bases coprime to the number; 8536 (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×272−1, thus 1/3 of the bases coprime to the number; 113 (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 (313−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 |
|---|---|---|---|
| 1563 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%) |
| 8536 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%) |
| 113 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×37+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:
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).
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 1016 (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 > 1025000, thus the property that they are in fact composite is less than 10−2000 (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 < 264: 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 5762668 (base 11) is in fact composite, then 5{7} will be an additional unsolved family for base 11.
- If C523755C (base 13) is in fact composite, then C{5}C will be an additional unsolved family for base 13.
- If 8032017111 (base 13) is in fact composite, then 8{0}111 will be an additional unsolved family for base 13.
- If 95197420 (base 13) is in fact composite, then 9{5} will be an additional unsolved family for base 13.
- If DB32234 (base 16) is in fact composite, then D{B} will be an additional unsolved family for base 16.
- If 472785DD (base 16) is in fact composite, then {4}DD will be an additional unsolved family for base 16.
- If 3116137AF (base 16) is in fact composite, then {3}AF will be an additional unsolved family for base 16.
- If BK220015 (base 22) is in fact composite, then B{K}5 will be an additional unsolved family for base 22.
- If 5193916F (base 26) is in fact composite, then {5}6F will be an additional unsolved family for base 26.
- If 720279OL (base 26) is in fact composite, then {7}OL will be an additional unsolved family for base 26.
- If LD0209757 (base 26) is in fact composite, then LD{0}7 will be an additional unsolved family for base 26.
- If 6K233005 (base 26) is in fact composite, then 6{K}5 will be an additional unsolved family for base 26.
- If J044303KCB (base 26) is in fact composite, then J{0}KCB will be an additional unsolved family for base 26.
- If M0611862BB (base 26) is in fact composite, then M{0}2BB will be an additional unsolved family for base 26.
- If N624051LR (base 28) is in fact composite, then N{6}LR will be an additional unsolved family for base 28.
- If 5OA31238F (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 O4O945359 (base 28) is in fact composite, then O4{O}9 will be an additional unsolved family for base 28.
- If I024608D (base 30) is in fact composite, then I{0}D will be an additional unsolved family for base 30.
- If 7K26567Z (base 36) is in fact composite, then 7{K}Z will be an additional unsolved family for base 36.
- If S0750078H (base 36) is in fact composite, then S{0}8H will be an additional unsolved family for base 36.
- If P81993SZ (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 "xynz") (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 5762668 in base 11, which equals the probable prime (57×1162668−7)/10. (Note: There is no input file for Primo for the probable prime 95197420 in base 13 (which equals the probable prime (113×13197420−5)/12) since this probable prime is too large (>10149999) 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))