Skip to content
main
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
minimal-elements-of-the-prime-numbers/unproven-probable-primes/
minimal-elements-of-the-prime-numbers/unproven-probable-primes/

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time

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 age of the universe (https://en.wikipedia.org/wiki/Age_of_the_universe), 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 AKS 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 too large, also a near-polynomial time (although not completely polynomial time) primality test, APR 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=1044289340#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) (e.g. difference-of-two-squares factorization (https://en.wikipedia.org/wiki/Difference_of_two_squares), 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, 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/The_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://maths-people.anu.edu.au/~brent/ftp/champs.txt, 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, https://www.alpertron.com.ar/ECM.HTM) (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) 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×nc and a×pc (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 bn/2, thus, for the Cunningham number bn±1, if the primitive part (i.e. Φn(b) for bn−1 or Φ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)) 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 Φ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)) 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/)), 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) 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.

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, http://www.numericana.com/answer/pseudo.htm#pseudoprime) Lucas probable primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime, https://mathworld.wolfram.com/LucasPseudoprime.html)
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/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) Strong Lucas probable primality test (https://en.wikipedia.org/wiki/Lucas_pseudoprime#Strong_Lucas_pseudoprimes, https://mathworld.wolfram.com/StrongLucasPseudoprime.html)
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), i.e. numbers of the form 2n+1 (https://oeis.org/A000051), if 2n+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), i.e. numbers of the form 2n−1 (https://oeis.org/A000225), if 2n−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×2n+1 with k odd and k < 2n, 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://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×2n−1 with k odd and k < 2n, such numbers are called "Proth numbers of the second kind" (https://www.rieselprime.de/ziki/Riesel_prime), 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×2n+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, https://www.rieselprime.de/default.htm, https://www.rieselprime.de/ziki/Proth_prime) List of primes of the form k×2n−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, https://www.rieselprime.de/default.htm, https://www.rieselprime.de/ziki/Riesel_prime)
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://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://mathworld.wolfram.com/SierpinskiNumberoftheSecondKind.html, 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×2n+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://en.wikipedia.org/wiki/Riesel_number, https://primes.utm.edu/glossary/xpage/RieselNumber.html, https://www.rieselprime.de/ziki/Riesel_problem, 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×2n−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×2n+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×2n−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 2n+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 2nk 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×bn+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×bn−1 is composite for all n ≥ 1
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://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://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/A074773), 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 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) 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: