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

Name	Name	Last commit message	Last commit date
parent directory ..
README.md	README.md	Update README.md	Jun 27, 2024
primoinput11_1068	primoinput11_1068	Add files via upload	Nov 23, 2022
primoinput13_3194	primoinput13_3194	Add files via upload	Nov 23, 2022
primoinput13_3195	primoinput13_3195	Add files via upload	Nov 23, 2022
primoinput16_2345	primoinput16_2345	Add files via upload	Nov 23, 2022
primoinput16_2346	primoinput16_2346	Add files via upload	Nov 23, 2022
primoinput16_2347	primoinput16_2347	Add files via upload	Nov 23, 2022
primoinput22_8003	primoinput22_8003	Add files via upload	Nov 23, 2022
primoinput26_25250	primoinput26_25250	Add files via upload	Dec 23, 2022
primoinput26_25251	primoinput26_25251	Add files via upload	Dec 23, 2022
primoinput26_25252	primoinput26_25252	Add files via upload	Dec 23, 2022
primoinput26_25253	primoinput26_25253	Add files via upload	Dec 23, 2022
primoinput26_25254	primoinput26_25254	Add files via upload	Dec 23, 2022
primoinput26_25255	primoinput26_25255	Add files via upload	Dec 23, 2022
primoinput28_25526	primoinput28_25526	Add files via upload	Nov 23, 2022
primoinput28_25527	primoinput28_25527	Add files via upload	Nov 23, 2022
primoinput28_25528	primoinput28_25528	Add files via upload	Nov 23, 2022
primoinput30_2618	primoinput30_2618	Add files via upload	Nov 23, 2022
primoinput36_35284	primoinput36_35284	Add files via upload	Dec 23, 2022
primoinput36_35285	primoinput36_35285	Add files via upload	Dec 23, 2022
primoinput36_35286	primoinput36_35286	Add files via upload	Dec 23, 2022
unprovenPRP11	unprovenPRP11	Rename unproven-probable-prime/unprovenPRP11 to unproven-probable-pri…	Sep 28, 2022
unprovenPRP13	unprovenPRP13	Update unprovenPRP13	Nov 24, 2023
unprovenPRP16	unprovenPRP16	Rename unproven-probable-prime/unprovenPRP16 to unproven-probable-pri…	Sep 28, 2022
unprovenPRP22	unprovenPRP22	Rename unproven-probable-prime/unprovenPRP22 to unproven-probable-pri…	Sep 28, 2022
unprovenPRP26	unprovenPRP26	Update unprovenPRP26	Dec 23, 2022
unprovenPRP28	unprovenPRP28	Rename unproven-probable-prime/unprovenPRP28 to unproven-probable-pri…	Sep 28, 2022
unprovenPRP30	unprovenPRP30	Rename unproven-probable-prime/unprovenPRP30 to unproven-probable-pri…	Sep 28, 2022
unprovenPRP36	unprovenPRP36	Create unprovenPRP36	Dec 22, 2022
unprovenPRPalgebraic11	unprovenPRPalgebraic11	Create unprovenPRPalgebraic11	Mar 5, 2023
unprovenPRPalgebraic13	unprovenPRPalgebraic13	Update unprovenPRPalgebraic13	Nov 24, 2023
unprovenPRPalgebraic16	unprovenPRPalgebraic16	Create unprovenPRPalgebraic16	Mar 5, 2023
unprovenPRPalgebraic22	unprovenPRPalgebraic22	Create unprovenPRPalgebraic22	Mar 5, 2023
unprovenPRPalgebraic26	unprovenPRPalgebraic26	Create unprovenPRPalgebraic26	Mar 5, 2023
unprovenPRPalgebraic28	unprovenPRPalgebraic28	Create unprovenPRPalgebraic28	Mar 5, 2023
unprovenPRPalgebraic30	unprovenPRPalgebraic30	Create unprovenPRPalgebraic30	Mar 5, 2023
unprovenPRPalgebraic36	unprovenPRPalgebraic36	Create unprovenPRPalgebraic36	Mar 5, 2023

(In progess to add bases b = 17 and b = 21)

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://t5k.org/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²
4	341	11 × 31
5	781	11 × 71
6	217	7 × 31
7	25	5²
8	9	3²
9	91	7 × 13
10	9	3²
11	133	7 × 19
12	91	7 × 13
13	85	5 × 17
14	15	3 × 5
15	1687	7 × 241
16	15	3 × 5
17	9	3²
18	25	5²
19	9	3²
20	21	3 × 7
21	221	13 × 17
22	21	3 × 7
23	169	13²
24	25	5²
25	217	7 × 31
26	9	3²
27	121	11²
28	9	3²
29	15	3 × 5
30	49	7²
31	15	3 × 5
32	25	5²
33	545	5 × 109
34	33	3 × 11
35	9	3²
36	35	5 × 7
95	1891	31 × 61
240	1991	11 × 181
385	1891	31 × 61
777	1541	23 × 67
933	1387	19 × 73
1320	4097	17 × 241
4712	4711	7 × 673
5628	5627	17 × 331
7252	7251	3 × 2417
7852	7851	3 × 2617
14787	9409	97²
17340	10261	31 × 331
61380	11359	37 × 307
78750	13747	59 × 233
254923	18299	29 × 631
377687	5329	73²
486605	25761	3 × 31 × 277
1804842	32761	181²
4095086	38323	19 × 2017
12772344	40501	101 × 401
42162995	97921	181 × 541
921211727	49141	157 × 313
814494960528	132239	223 × 593
64390572806844	161701	101 × 1601
1769236083487960	192001	101 × 1901
1948244569546278	212321	241 × 881
34933608779780163	218245	5 × 43649
62769592775616394	272161	127 × 2143
126401071349994536	291831	3 × 89 × 1093
9345883071009581737	341531	239 × 1429
2, 3	1373653	829 × 1657
31, 73	9080191	2131 × 4261
2, 299417	19471033	883 × 22051
2, 3, 5	25326001	2251 × 11251
2, 9332593	38010307	3083 × 12329
350, 3958281543	170584961	7541 × 22621
2346211568, 3056093627	176609441	7673 × 23017
660, 56928287	227132641	10657 × 21313
11000544, 31481107	316349281	12577 × 25153
91869414, 6346128598129234	466758181	15277 × 30553
15, 750068417525532	520924141	8627 × 60383
15, 5511855321103177	624732421	14431 × 43291
15, 13393019396194701	716169301	15451 × 46351
725270293939359937, 3569819667048198375	885594169	13309 × 66541
336781006125, 9639812373923155	1050535501	12251 × 85751
2, 3, 5, 7	3215031751	151 × 751 × 28351
2, 7, 61	4759123141	48781 × 97561
2, 379215, 457083754	75792980677	137653 × 550609
2, 1005905886, 1340600841	105936894253	230149 × 460297
2, 45650740, 3722628058	109134866497	110119 × 991063
15, 176006322, 4221622697	154639673381	160541 × 963241
15, 953185122, 158682512356199	220146059407	234599 × 938393
15, 7363882082, 211573017068182	242175507817	401809 × 602713
15, 7363882082, 992620450144556	273919523041	370081 × 740161
4230279247111683200, 14694767155120705706, 16641139526367750375	350269456337	197279 × 1775503
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, 642735, 553174392, 3046413974	31858317218647	2822159 × 11288633
2, 2570940, 211991001, 3749873356	47636622961201	4880401 × 9760801
2, 141889084524735, 1199124725622454117, 11096072698276303650	55245642489451	3716371 × 14865481
2, 3, 5, 7, 11, 13, 17	341550071728321	10670053 × 32010157
2, 75088, 642735, 203659041, 3613982119	3071837692357849	24786439 × 123932191
2, 2570940, 880937, 610386380, 4130785767	3770579582154547	30702523 × 122810089
2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805	7999252175582851	9227 × 894923 × 968731
2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375	585226005592931977	382500329 × 1530001313
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
2, 325, 9375, 28178, 450775, 9780504, 1795265022	> 2⁶⁴	?
all primes p ≤ n	> e^{(n/2)^1/2} (under the generalized Riemann hypothesis)	–

These numbers are semiprimes (https://en.wikipedia.org/wiki/Semiprime, https://t5k.org/glossary/xpage/Semiprime.html, https://mathworld.wolfram.com/Semiprime.html, https://www.numbersaplenty.com/set/semiprime/, https://oeis.org/A001358) of the form (m+1)×(2×m+1) or (m+1)×(3×m+1), (m+1)×(2×m+1) 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://t5k.org/glossary/xpage/QuadraticResidue.html, https://www.rieselprime.de/ziki/Quadratic_residue, https://mathworld.wolfram.com/QuadraticResidue.html) mod the prime 2×m+1, thus 1/2 of the bases coprime to the number; (m+1)×(3×m+1) 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 3×m+1, thus 1/3 of the bases coprime to the number. https://oeis.org/A129521 is a subsequence of https://oeis.org/A191311 (i.e. all numbers of the form p×(2×p−1) with p and 2×p−1 both primes are half-Carmichael numbers (i.e. composite numbers c such that b^c−1 == 1 mod c for half of the bases b coprime to c, the Carmichael numbers are the composite numbers c such that b^c−1 == 1 mod c for all bases b coprime to c)) (and the numbers in https://oeis.org/A191311 but not in https://oeis.org/A129521 are the numbers in https://oeis.org/A191592, the smallest such number (except the trivial number 4, which is the only one such even number, the only one such non-squarefree number, and the only one such semiprime, note that all Carmichael numbers are odd, squarefree, and have at least 3 prime factors) is 11305 = 5 × 7 × 17 × 19). e.g. 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; 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; 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; 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://t5k.org/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.

(for more examples, see https://www.mersenneforum.org/showpost.php?p=659223&postcount=1 and https://www.mersenneforum.org/showpost.php?p=659421&postcount=17 and https://oeis.org/A014233 and https://faculty.lynchburg.edu/~nicely/misc/mpzspsp.html and https://miller-rabin.appspot.com/ and http://www.pi-e.de/Miller-Rabin-Pseudoprimzahlen.htm (in German) and http://factordb.com/prooffailed.php)

number	factordb entry	bases 2 ≤ b ≤ 64 such that this number is Fermat pseudoprime (called "Fermat liars")	count
15₁₅ in base b = 16 (see https://web.archive.org/web/19991117032157/http://ourworld.compuserve.com/homepages/hlifchitz/MersFermus.htm (which is an erroneous version of http://www.primenumbers.net/Henri/us/MersFermus.htm))	http://factordb.com/index.php?id=1000000000043569055	2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 29, 32, 36, 41, 48, 54, 58, 59, 64	20 (31.75%)
15₃₀ in base b = 16 (see https://web.archive.org/web/19991117032157/http://ourworld.compuserve.com/homepages/hlifchitz/MersFermus.htm (which is an erroneous version of http://www.primenumbers.net/Henri/us/MersFermus.htm))	http://factordb.com/index.php?id=1000000000043569085	2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 18, 19, 22, 24, 26, 27, 31, 32, 33, 35, 36, 38, 39, 44, 48, 52, 53, 54, 57, 61, 62, 64	32 (50.79%)
15₆₃ in base b = 16 (see https://web.archive.org/web/19991117032157/http://ourworld.compuserve.com/homepages/hlifchitz/MersFermus.htm (which is an erroneous version of http://www.primenumbers.net/Henri/us/MersFermus.htm) and https://www.ams.org/journals/mcom/1993-61-204/S0025-5718-1993-1185243-9/S0025-5718-1993-1185243-9.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_4.pdf))	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=139810133	5, 7, 8, 12, 13, 17, 18, 25, 27, 35, 38, 40, 44, 46, 49, 56, 57, 59, 60, 64	20 (31.75%)
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 (see https://web.archive.org/web/19991117032157/http://ourworld.compuserve.com/homepages/hlifchitz/MersFermus.htm (which is an erroneous version of http://www.primenumbers.net/Henri/us/MersFermus.htm))	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%)
58₉ in base b = 25	http://factordb.com/index.php?id=20345052083333	2, 4, 8, 13, 16, 26, 27, 31, 32, 43, 45, 47, 52, 54, 62, 63, 64	17 (26.98%)
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://www.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://t5k.org/prove/prove3.html, https://t5k.org/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://t5k.org/prove/prove3.html, https://t5k.org/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://t5k.org/prove/prove3.html, https://t5k.org/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://t5k.org/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://t5k.org/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://t5k.org/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://t5k.org/prove/prove2_2.html, https://en.wikipedia.org/wiki/Fermat_primality_test, https://en.wikipedia.org/wiki/Fermat_pseudoprime, https://t5k.org/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://www.cecm.sfu.ca/Pseudoprimes/psps-below-2-to-64.txt.bz2, https://www.cecm.sfu.ca/Pseudoprimes/factored-psps-below-2-to-64.txt.bz2, https://www.cecm.sfu.ca/Pseudoprimes/annotated-psps-below-2-to-64.txt.bz2, 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/A005936, https://oeis.org/A005938, https://oeis.org/A052155, https://oeis.org/A083737, https://oeis.org/A083739, https://oeis.org/A083876, https://oeis.org/A271221, https://oeis.org/A348258, 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 (the largest known unproven probable prime (https://en.wikipedia.org/wiki/Probable_prime, https://t5k.org/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, http://www.primenumbers.net/prptop/prptop.php, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, https://www.mersenne.ca/prp.php?show=1, https://www.alfredreichlg.de/10w7/prp.html, http://factordb.com/listtype.php?t=1))	http://factordb.com/index.php?id=1100000002579528773&open=prime	8177207	http://www.primenumbers.net/prptop/prptop.php
Miller–Rabin probable primality testing (https://t5k.org/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://t5k.org/glossary/xpage/MillersTest.html, https://t5k.org/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://faculty.lynchburg.edu/~nicely/misc/mpzspsp.html, https://miller-rabin.appspot.com/, http://www.pi-e.de/Miller-Rabin-Pseudoprimzahlen.htm (in German), http://factordb.com/prooffailed.php, 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/A020231, https://oeis.org/A020233, https://oeis.org/A072276, https://oeis.org/A056915, https://oeis.org/A074773, https://oeis.org/A014233, https://oeis.org/A006945, https://oeis.org/A089825, 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 (the largest known unproven probable prime (https://en.wikipedia.org/wiki/Probable_prime, https://t5k.org/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, http://www.primenumbers.net/prptop/prptop.php, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, https://www.mersenne.ca/prp.php?show=1, https://www.alfredreichlg.de/10w7/prp.html, http://factordb.com/listtype.php?t=1))	http://factordb.com/index.php?id=1100000002579528773&open=prime	8177207	http://www.primenumbers.net/prptop/prptop.php
Lucas probable primality testing (https://en.wikipedia.org/wiki/Lucas_pseudoprime, https://mathworld.wolfram.com/LucasPseudoprime.html, https://www.mathpages.com/home/kmath127/kmath127.htm, http://ntheory.org/data/lpsps-baillie.txt, http://www.hoegge.dk/lucasselfridgeprps.txt, https://oeis.org/A217120)	O(log(n))	any number, but only probabilistic (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality testing	(10^8177207−1)/9 (the largest known unproven probable prime (https://en.wikipedia.org/wiki/Probable_prime, https://t5k.org/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, http://www.primenumbers.net/prptop/prptop.php, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, https://www.mersenne.ca/prp.php?show=1, https://www.alfredreichlg.de/10w7/prp.html, http://factordb.com/listtype.php?t=1))	http://factordb.com/index.php?id=1100000002579528773&open=prime	8177207	http://www.primenumbers.net/prptop/prptop.php
strong Lucas probable primality testing (https://en.wikipedia.org/wiki/Strong_Lucas_pseudoprime, https://mathworld.wolfram.com/StrongLucasPseudoprime.html, http://ntheory.org/data/slpsps-baillie.txt, http://www.hoegge.dk/lucasselfridgeprps.txt, https://oeis.org/A217255)	O(log(n))	any number, but only probabilistic (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality testing	(10^8177207−1)/9 (the largest known unproven probable prime (https://en.wikipedia.org/wiki/Probable_prime, https://t5k.org/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, http://www.primenumbers.net/prptop/prptop.php, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, https://www.mersenne.ca/prp.php?show=1, https://www.alfredreichlg.de/10w7/prp.html, http://factordb.com/listtype.php?t=1))	http://factordb.com/index.php?id=1100000002579528773&open=prime	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, http://pseudoprime.com/dopo.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_318.pdf))	O(log(n))	any number, but only probabilistic (https://en.wikipedia.org/wiki/Probabilistic_algorithm) primality testing	(10^8177207−1)/9 (the largest known unproven probable prime (https://en.wikipedia.org/wiki/Probable_prime, https://t5k.org/glossary/xpage/PRP.html, https://www.rieselprime.de/ziki/Probable_prime, https://mathworld.wolfram.com/ProbablePrime.html, http://www.primenumbers.net/prptop/prptop.php, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#probableprimenumbers, https://stdkmd.net/nrr/repunit/prpfactors.htm, https://www.mersenne.ca/prp.php?show=1, https://www.alfredreichlg.de/10w7/prp.html, http://factordb.com/listtype.php?t=1))	http://factordb.com/index.php?id=1100000002579528773&open=prime	8177207	http://www.primenumbers.net/prptop/prptop.php
Pépin primality testing (https://en.wikipedia.org/wiki/P%C3%A9pin%27s_test, https://t5k.org/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://t5k.org/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 (the largest known Fermat prime (https://en.wikipedia.org/wiki/Fermat_number, https://t5k.org/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, http://www.prothsearch.com/fermat.html, https://t5k.org/top20/page.php?id=8, https://t5k.org/primes/search.php?Comment=Divides&OnList=all&Number=1000000&Style=HTML, http://www.fermatsearch.org/, https://64ordle.au/fermat/, https://64ordle.au/fermat/small/, https://www.primegrid.com/forum_thread.php?id=8778, https://www.primegrid.com/stats_div_llr.php, https://www.primegrid.com/primes/primes.php?project=DIV&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.rieselprime.de/ziki/PrimeGrid_Fermat_Divisor_Search, http://www.fermatsearch.org/factors/faclist.php, http://www.fermatsearch.org/factors/composite.php))	http://factordb.com/index.php?id=65537&open=prime	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://t5k.org/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://t5k.org/glossary/xpage/MersenneNumber.html, https://t5k.org/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 (the largest known Mersenne prime (https://en.wikipedia.org/wiki/Mersenne_prime, https://t5k.org/glossary/xpage/MersenneNumber.html, https://t5k.org/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, https://t5k.org/top20/page.php?id=4, https://t5k.org/primes/search.php?Comment=Mersenne%20[[:digit:]]&OnList=all&Number=1000000&Style=HTML, https://www.mersenne.org/, https://www.mersenne.ca/, https://www.mersenne.org/primes/, https://www.mersenne.ca/prime.php, https://t5k.org/mersenne/))	http://www.factordb.com/index.php?id=1100000001257221107&open=prime	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ⁿ, such numbers are called "Proth numbers" (https://en.wikipedia.org/wiki/Proth_prime, https://t5k.org/glossary/xpage/ProthPrime.html, https://www.rieselprime.de/ziki/Proth_prime, https://mathworld.wolfram.com/ProthNumber.html, http://www.prothsearch.com/frequencies.html, http://www.prothsearch.com/history.html, https://www.rieselprime.de/Data/PStatistics.htm, https://www.rieselprime.de/Data/PRanges50.htm, https://www.rieselprime.de/Data/PRanges300.htm, https://www.rieselprime.de/Data/PRanges1200.htm, http://irvinemclean.com/maths/pfaq6.htm, https://www.numbersaplenty.com/set/Proth_number/, https://web.archive.org/web/20230706041914/https://pzktupel.de/Primetables/TableProthTOP10KK.php, https://web.archive.org/web/20231030081449/https://pzktupel.de/Primetables/ProthK.txt, https://pzktupel.de/Primetables/TableProthTOP10KS.php, https://pzktupel.de/Primetables/ProthS.txt, https://t5k.org/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, https://www.primegrid.com/primes/primes.php?project=PPS&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PPSE&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=MEG&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, http://boincvm.proxyma.ru:30080/test4vm/public/pps_dc_status.php, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search_Extended, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Mega_Prime_Search), and such primes are called "Proth primes"	10223×2^31172165+1 (the largest known Proth prime (https://en.wikipedia.org/wiki/Proth_prime, https://t5k.org/glossary/xpage/ProthPrime.html, https://www.rieselprime.de/ziki/Proth_prime, https://mathworld.wolfram.com/ProthNumber.html, http://www.prothsearch.com/frequencies.html, http://www.prothsearch.com/history.html, https://www.rieselprime.de/Data/PStatistics.htm, https://www.rieselprime.de/Data/PRanges50.htm, https://www.rieselprime.de/Data/PRanges300.htm, https://www.rieselprime.de/Data/PRanges1200.htm, http://irvinemclean.com/maths/pfaq6.htm, https://www.numbersaplenty.com/set/Proth_number/, https://web.archive.org/web/20230706041914/https://pzktupel.de/Primetables/TableProthTOP10KK.php, https://web.archive.org/web/20231030081449/https://pzktupel.de/Primetables/ProthK.txt, https://pzktupel.de/Primetables/TableProthTOP10KS.php, https://pzktupel.de/Primetables/ProthS.txt, https://t5k.org/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, https://www.primegrid.com/primes/primes.php?project=PPS&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PPSE&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=MEG&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, http://boincvm.proxyma.ru:30080/test4vm/public/pps_dc_status.php, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search_Extended, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Mega_Prime_Search))	http://factordb.com/index.php?id=1100000000881266827&open=prime	9383761	https://t5k.org/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ⁿ, such numbers are called "Proth numbers of the second kind" (https://www.rieselprime.de/ziki/Riesel_prime, https://www.rieselprime.de/Data/Statistics.htm, http://irvinemclean.com/maths/pfaq6.htm, https://web.archive.org/web/20230628151418/https://pzktupel.de/Primetables/TableRieselTOP10KK.php, https://web.archive.org/web/20231030081316/https://pzktupel.de/Primetables/RieselK.txt, https://pzktupel.de/Primetables/TableRieselTOP10KS.php, https://pzktupel.de/Primetables/RieselS.txt, http://www.noprimeleftbehind.net/stats/index.php?content=prime_list, http://www.noprimeleftbehind.net/prpnet/, http://www.noprimeleftbehind.net:9000/all.html, http://www.noprimeleftbehind.net:4000/all.html, http://www.noprimeleftbehind.net:2000/all.html, http://www.noprimeleftbehind.net:1468/all.html, http://www.noprimeleftbehind.net:1400/all.html, https://www.rieselprime.de/ziki/NPLB_Drive_17, https://www.rieselprime.de/ziki/NPLB_Drive_18, https://www.rieselprime.de/ziki/NPLB_Drive_19, https://www.rieselprime.de/ziki/NPLB_Drive_High-n), and such primes are called "Proth primes of the second kind"	3×2^20928756−1 (the largest known Proth prime of the second kind (https://www.rieselprime.de/ziki/Riesel_prime, https://www.rieselprime.de/Data/Statistics.htm, http://irvinemclean.com/maths/pfaq6.htm, https://web.archive.org/web/20230628151418/https://pzktupel.de/Primetables/TableRieselTOP10KK.php, https://web.archive.org/web/20231030081316/https://pzktupel.de/Primetables/RieselK.txt, https://pzktupel.de/Primetables/TableRieselTOP10KS.php, https://pzktupel.de/Primetables/RieselS.txt, http://www.noprimeleftbehind.net/stats/index.php?content=prime_list, http://www.noprimeleftbehind.net/prpnet/, http://www.noprimeleftbehind.net:9000/all.html, http://www.noprimeleftbehind.net:4000/all.html, http://www.noprimeleftbehind.net:2000/all.html, http://www.noprimeleftbehind.net:1468/all.html, http://www.noprimeleftbehind.net:1400/all.html, https://www.rieselprime.de/ziki/NPLB_Drive_17, https://www.rieselprime.de/ziki/NPLB_Drive_18, https://www.rieselprime.de/ziki/NPLB_Drive_19, https://www.rieselprime.de/ziki/NPLB_Drive_High-n))	http://factordb.com/index.php?id=1100000004660727594&open=prime	6300184	https://t5k.org/primes/lists/all.txt
Pocklington (N−1) primality testing (https://t5k.org/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://irvinemclean.com/maths/pfaq4.htm, 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 (i.e. the product of the known prime factors of n−1 is ≥ the square root (https://en.wikipedia.org/wiki/Square_root, https://www.rieselprime.de/ziki/Square_root, https://mathworld.wolfram.com/SquareRoot.html) of it)	1963736^1048576+1 (the largest known generalized Proth prime (https://en.wikipedia.org/wiki/Proth_prime, https://t5k.org/glossary/xpage/ProthPrime.html, https://www.rieselprime.de/ziki/Proth_prime, https://mathworld.wolfram.com/ProthNumber.html, http://www.prothsearch.com/frequencies.html, http://www.prothsearch.com/history.html, https://www.rieselprime.de/Data/PStatistics.htm, https://www.rieselprime.de/Data/PRanges50.htm, https://www.rieselprime.de/Data/PRanges300.htm, https://www.rieselprime.de/Data/PRanges1200.htm, http://irvinemclean.com/maths/pfaq6.htm, https://www.numbersaplenty.com/set/Proth_number/, https://web.archive.org/web/20230706041914/https://pzktupel.de/Primetables/TableProthTOP10KK.php, https://web.archive.org/web/20231030081449/https://pzktupel.de/Primetables/ProthK.txt, https://pzktupel.de/Primetables/TableProthTOP10KS.php, https://pzktupel.de/Primetables/ProthS.txt, https://pzktupel.de/Primetables/TableProthGen.php, https://pzktupel.de/Primetables/TableProthGen.txt, https://sites.google.com/view/proth-primes, https://t5k.org/primes/search_proth.php, https://t5k.org/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, https://www.primegrid.com/primes/primes.php?project=PPS&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PPSE&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=MEG&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, http://boincvm.proxyma.ru:30080/test4vm/public/pps_dc_status.php, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search_Extended, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Mega_Prime_Search) with base b > 2)	http://factordb.com/index.php?id=1100000003905175851&open=prime	6598776	https://t5k.org/primes/lists/all.txt
Morrison (N+1) primality testing (https://t5k.org/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://irvinemclean.com/maths/pfaq4.htm, http://factordb.com/nmoverview.php?method=2)	O(log(n))	numbers n such that n+1 can be ≥ 1/2 factored (i.e. the product of the known prime factors of n+1 is ≥ the square root (https://en.wikipedia.org/wiki/Square_root, https://www.rieselprime.de/ziki/Square_root, https://mathworld.wolfram.com/SquareRoot.html) of it)	3622×5^7558139−1 (the largest known generalized Proth prime of the second kind (https://www.rieselprime.de/ziki/Riesel_prime, https://www.rieselprime.de/Data/Statistics.htm, http://irvinemclean.com/maths/pfaq6.htm, https://web.archive.org/web/20230628151418/https://pzktupel.de/Primetables/TableRieselTOP10KK.php, https://web.archive.org/web/20231030081316/https://pzktupel.de/Primetables/RieselK.txt, https://pzktupel.de/Primetables/TableRieselTOP10KS.php, https://pzktupel.de/Primetables/RieselS.txt, https://pzktupel.de/Primetables/TableRieselGen.php, https://pzktupel.de/Primetables/TableRieselGen.txt, https://sites.google.com/view/proth-primes, http://www.noprimeleftbehind.net/stats/index.php?content=prime_list, https://t5k.org/primes/search_proth.php, http://www.noprimeleftbehind.net/prpnet/, http://www.noprimeleftbehind.net:9000/all.html, http://www.noprimeleftbehind.net:4000/all.html, http://www.noprimeleftbehind.net:2000/all.html, http://www.noprimeleftbehind.net:1468/all.html, http://www.noprimeleftbehind.net:1400/all.html, https://www.rieselprime.de/ziki/NPLB_Drive_17, https://www.rieselprime.de/ziki/NPLB_Drive_18, https://www.rieselprime.de/ziki/NPLB_Drive_19, https://www.rieselprime.de/ziki/NPLB_Drive_High-n) with base b > 2)	http://factordb.com/index.php?id=1100000002920355417&open=prime	5282917	https://t5k.org/primes/lists/all.txt
elliptic curve (ECPP) primality testing (https://t5k.org/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://t5k.org/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html, http://irvinemclean.com/maths/pfaq7.htm, https://t5k.org/top20/page.php?id=27, https://t5k.org/primes/search.php?Comment=ECPP&OnList=all&Number=1000000&Style=HTML, http://www.ellipsa.eu/public/primo/records.html, http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html, https://www.multiprecision.org/cm/ecpp.html, https://www.ams.org/journals/mcom/1993-61-203/S0025-5718-1993-1199989-X/S0025-5718-1993-1199989-X.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_256.pdf), https://arxiv.org/pdf/2404.05506.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_428.pdf))	O(log(n)^4+ε) for some ε > 0	any number	(10⁸⁶⁴⁵³−1)/9 (the largest known proven ordinary prime (https://t5k.org/glossary/xpage/OrdinaryPrime.html))	http://factordb.com/index.php?id=1100000000046752372&open=prime	86453	https://t5k.org/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://t5k.org/prove/prove4_1.html, https://t5k.org/primes/search.php?Comment=APR-CL%20assisted&OnList=all&Number=1000000&Style=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://t5k.org/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), http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_231.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, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (sections "Special number field sieve by size of number factored:" and "Special number field sieve by SNFS difficulty:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=snfs&maxrows=10000, https://stdkmd.net/nrr/wanted.htm#smallpolynomial, https://www.mersenne.ca/userfactors/nfs/1, http://escatter11.fullerton.edu/nfs/)	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&open=ecm	360 (SNFS difficulty)	https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (sections "Special number field sieve by size of number factored:" and "Special number field sieve by SNFS difficulty:")
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, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (section "General number field sieve by size of number factored:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=gnfs&maxrows=10000, https://stdkmd.net/nrr/wanted.htm#suitableforgnfs, https://www.mersenne.ca/userfactors/nfs/1, http://escatter11.fullerton.edu/nfs/)	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	the RSA number (https://en.wikipedia.org/wiki/RSA_numbers, https://t5k.org/glossary/xpage/RSAExample.html, https://mathworld.wolfram.com/RSANumber.html, http://www.ontko.com/pub/rayo/primes/rsa_fact.html, http://www.loria.fr/~zimmerma/records/rsa.html, https://web.archive.org/web/20061209135708/http://www.rsasecurity.com/rsalabs/node.asp?id=2093, https://web.archive.org/web/20130521030319/https://www.rsa.com/rsalabs/challenges/factoring/challengenumbers.txt) RSA-250 (see https://www.mersenneforum.org/showthread.php?t=25312 for more information of this number)	http://factordb.com/index.php?id=1100000000104374168&open=ecm	250 (GNFS difficulty)	https://en.wikipedia.org/wiki/Integer_factorization_records#Numbers_of_a_general_form
trial division (https://en.wikipedia.org/wiki/Trial_division, https://t5k.org/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, https://www.mersenne.ca/tf1G/, https://www.mersenne.ca/tfmissed.php, https://oeis.org/A189172)	O(p)	any prime factor	9999999999999937 (the largest prime < 10¹⁶)	http://factordb.com/index.php?id=9999999999999937&open=ecm	16	(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, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (section "Pollard p-1:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=p-1&maxrows=10000, http://www.numericana.com/answer/factoring.htm#p-1, http://factordb.com/listecm.php?c=2, http://www.loria.fr/~zimmerma/records/Pminus1.html, https://web.archive.org/web/20021015212913/http://www.users.globalnet.co.uk/~aads/Pminus1.html, https://web.archive.org/web/20231002022529/https://colin.barker.pagesperso-orange.fr/lpa/big_pm1.htm, https://www.mersenne.org/report_pminus1/, https://www.mersenne.ca/userfactors/pm1/1, https://www.mersenne.ca/smooth.php, https://www.mersenne.ca/p1missed.php, https://www.mersenne.ca/prob.php)	O(log(p))	prime factors p such that p−1 is smooth (https://en.wikipedia.org/wiki/Smooth_number, https://mathworld.wolfram.com/SmoothNumber.html, https://oeis.org/A003586, https://oeis.org/A051037, https://oeis.org/A002473, https://oeis.org/A051038, https://oeis.org/A080197, https://oeis.org/A080681, https://oeis.org/A080682, https://oeis.org/A080683) (i.e. the greatest prime factor (http://mathworld.wolfram.com/GreatestPrimeFactor.html, https://oeis.org/A006530) of p−1 is small)	prime factor of 960¹¹⁹−1	http://factordb.com/index.php?id=1100000000216738427&open=ecm	66	http://www.loria.fr/~zimmerma/records/Pminus1.html
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, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (section "p+1:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=p%2b1&maxrows=10000, http://www.numericana.com/answer/factoring.htm#p+1, http://factordb.com/listecm.php?c=3, http://www.loria.fr/~zimmerma/records/Pplus1.html, https://www.mersenne.org/report_pplus1/, https://www.mersenne.ca/userfactors/pp1/1, https://www.mersenne.ca/pplus1.php)	O(log(p))	prime factors p such that p+1 is smooth (https://en.wikipedia.org/wiki/Smooth_number, https://mathworld.wolfram.com/SmoothNumber.html, https://oeis.org/A003586, https://oeis.org/A051037, https://oeis.org/A002473, https://oeis.org/A051038, https://oeis.org/A080197, https://oeis.org/A080681, https://oeis.org/A080682, https://oeis.org/A080683) (i.e. the greatest prime factor (http://mathworld.wolfram.com/GreatestPrimeFactor.html, https://oeis.org/A006530) of p+1 is small)	prime factor of the Lucas number (https://en.wikipedia.org/wiki/Lucas_number, https://t5k.org/glossary/xpage/LucasNumber.html, https://mathworld.wolfram.com/LucasNumber.html, https://www.numbersaplenty.com/set/Lucas_number/, https://t5k.org/top20/page.php?id=48, https://t5k.org/primes/search.php?Comment=^Lucas%20number&OnList=all&Number=1000000&Style=HTML, https://pzktupel.de/Primetables/TableLucas.php, https://oeis.org/A000032, https://oeis.org/A000204, https://oeis.org/A005479, https://oeis.org/A001606) L₂₃₆₆	http://factordb.com/index.php?id=1100000000216896584&open=ecm	60	http://www.loria.fr/~zimmerma/records/Pplus1.html
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://factordb.com/listecm.php?c=4, 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, http://www.loria.fr/~zimmerma/records/ecm/params.html, https://oeis.org/wiki/OEIS_sequences_needing_factors#ECM_efforts, https://stdkmd.net/nrr/records.htm#largefactorecm, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (section "Elliptic curve method:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=ecm&maxrows=10000, 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, http://www.mersenne.org/report_ECM/, https://www.mersenne.ca/userfactors/ecm/1, https://stdkmd.net/nrr/c.cgi?q=37771_259#ecm, https://stdkmd.net/nrr/c.cgi?q=23333_233#ecm, https://kurtbeschorner.de/ecm-efforts.htm, http://www.rechenkraft.net/yoyo//y_factors_ecm.php, http://www.rechenkraft.net/yoyo/y_status_ecm.php, http://www.wraithx.net/math/ecmprobs/ecmprobs.html, http://www.loria.fr/~zimmerma/papers/ecm-entry.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_460.pdf))	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	http://www.loria.fr/~zimmerma/records/top50.html

(Since the largest prime factor found by Lenstra elliptic-curve (ECM) integer factoring has 83 decimal digits, and the largest prime factor found by Pollard (P−1) integer factoring has 66 decimal digits, and the largest prime factor found by Williams (P+1) integer factoring has 60 decimal digits, thus there are no numbers which are not fully factored (i.e. have status (http://factordb.com/status.html, http://factordb.com/distribution.php) "CF" instead of "FF" in factordb) and have a known prime factor (other than the algebraic factors, e.g. the repunit number R₈₄₂ has a known 401-digit prime factor but is not fully factored (i.e. have status (http://factordb.com/status.html, http://factordb.com/distribution.php) "CF" instead of "FF" in factordb) (with a 413-digit composite factor without known proper factor > 1) (see http://factordb.com/index.php?id=1000000000043587866&open=ecm), but the repunit number R₈₄₂ has three algebraic factors, namely Φ₂(10) and Φ₄₂₁(10) and Φ₈₄₂(10) (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, https://oeis.org/A013595, https://oeis.org/A013596, https://oeis.org/A253240)), and the 401-digit prime factor is a prime factor of Φ₄₂₁(10), but the 413-digit composite factor without known proper factor > 1 is a prime factor of Φ₈₄₂(10), thus this number is not a counterexample) with > 83 decimal digits)

Thus, for these numbers, we usually use the general purpose tests (https://t5k.org/prove/prove4.html), which do not require factorization of N±1 and can be used for ordinary primes (https://t5k.org/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://t5k.org/prove/prove2_2.html, https://en.wikipedia.org/wiki/Fermat_primality_test, https://en.wikipedia.org/wiki/Fermat_pseudoprime, https://t5k.org/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://www.cecm.sfu.ca/Pseudoprimes/psps-below-2-to-64.txt.bz2, https://www.cecm.sfu.ca/Pseudoprimes/factored-psps-below-2-to-64.txt.bz2, https://www.cecm.sfu.ca/Pseudoprimes/annotated-psps-below-2-to-64.txt.bz2, 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/A005936, https://oeis.org/A005938, https://oeis.org/A052155, https://oeis.org/A083737, https://oeis.org/A083739, https://oeis.org/A083876, https://oeis.org/A271221, https://oeis.org/A348258, 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, https://www.mathpages.com/home/kmath127/kmath127.htm, http://ntheory.org/data/lpsps-baillie.txt, http://www.hoegge.dk/lucasselfridgeprps.txt, https://oeis.org/A217120)
Miller–Rabin probable primality test (https://t5k.org/prove/prove2_3.html, https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, https://en.wikipedia.org/wiki/Strong_pseudoprime, https://t5k.org/glossary/xpage/MillersTest.html, https://t5k.org/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://faculty.lynchburg.edu/~nicely/misc/mpzspsp.html, https://miller-rabin.appspot.com/, http://www.pi-e.de/Miller-Rabin-Pseudoprimzahlen.htm (in German), http://factordb.com/prooffailed.php, 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/A020231, https://oeis.org/A020233, https://oeis.org/A072276, https://oeis.org/A056915, https://oeis.org/A074773, https://oeis.org/A014233, https://oeis.org/A006945, https://oeis.org/A089825, 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/Strong_Lucas_pseudoprime, https://mathworld.wolfram.com/StrongLucasPseudoprime.html, http://ntheory.org/data/slpsps-baillie.txt, http://www.hoegge.dk/lucasselfridgeprps.txt, https://oeis.org/A217255)
Carmichael number (https://oeis.org/A002997, https://en.wikipedia.org/wiki/Carmichael_number, https://t5k.org/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, http://www.s369624816.websitehome.co.uk/rgep/carpsp.html, http://www.s369624816.websitehome.co.uk/rgep/cartable.html)	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://t5k.org/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://t5k.org/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://t5k.org/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://t5k.org/notes/proofs/LucasLehmer.html, http://www.numericana.com/answer/primes.htm#lucas-lehmer) for Mersenne numbers (https://en.wikipedia.org/wiki/Mersenne_prime, https://t5k.org/glossary/xpage/MersenneNumber.html, https://t5k.org/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://t5k.org/glossary/xpage/ProthPrime.html, https://www.rieselprime.de/ziki/Proth_prime, https://mathworld.wolfram.com/ProthNumber.html, http://www.prothsearch.com/frequencies.html, http://www.prothsearch.com/history.html, https://www.rieselprime.de/Data/PStatistics.htm, https://www.rieselprime.de/Data/PRanges50.htm, https://www.rieselprime.de/Data/PRanges300.htm, https://www.rieselprime.de/Data/PRanges1200.htm, http://irvinemclean.com/maths/pfaq6.htm, https://www.numbersaplenty.com/set/Proth_number/, https://web.archive.org/web/20230706041914/https://pzktupel.de/Primetables/TableProthTOP10KK.php, https://web.archive.org/web/20231030081449/https://pzktupel.de/Primetables/ProthK.txt, https://pzktupel.de/Primetables/TableProthTOP10KS.php, https://pzktupel.de/Primetables/ProthS.txt, https://t5k.org/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, https://www.primegrid.com/primes/primes.php?project=PPS&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PPSE&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=MEG&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, http://boincvm.proxyma.ru:30080/test4vm/public/pps_dc_status.php, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Prime_Search_Extended, https://www.rieselprime.de/ziki/PrimeGrid_Proth_Mega_Prime_Search), 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://www.rieselprime.de/Data/Statistics.htm, http://irvinemclean.com/maths/pfaq6.htm, https://web.archive.org/web/20230628151418/https://pzktupel.de/Primetables/TableRieselTOP10KK.php, https://web.archive.org/web/20231030081316/https://pzktupel.de/Primetables/RieselK.txt, https://pzktupel.de/Primetables/TableRieselTOP10KS.php, https://pzktupel.de/Primetables/RieselS.txt, http://www.noprimeleftbehind.net/stats/index.php?content=prime_list, http://www.noprimeleftbehind.net/prpnet/, http://www.noprimeleftbehind.net:9000/all.html, http://www.noprimeleftbehind.net:4000/all.html, http://www.noprimeleftbehind.net:2000/all.html, http://www.noprimeleftbehind.net:1468/all.html, http://www.noprimeleftbehind.net:1400/all.html, https://www.rieselprime.de/ziki/NPLB_Drive_17, https://www.rieselprime.de/ziki/NPLB_Drive_18, https://www.rieselprime.de/ziki/NPLB_Drive_19, https://www.rieselprime.de/ziki/NPLB_Drive_High-n), 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://t5k.org/prove/prove3_1.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://irvinemclean.com/maths/pfaq4.htm, 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 (i.e. the product of the known prime factors of N−1 is ≥ the square root (https://en.wikipedia.org/wiki/Square_root, https://www.rieselprime.de/ziki/Square_root, https://mathworld.wolfram.com/SquareRoot.html) of it)	Morrison N+1 primality test (https://t5k.org/prove/prove3_2.html, http://bln.curtisbright.com/2013/10/09/the-n-1-and-n1-primality-tests/, http://irvinemclean.com/maths/pfaq4.htm, http://factordb.com/nmoverview.php?method=2) for numbers N such that N+1 can be ≥ 1/2 factored (i.e. the product of the known prime factors of N+1 is ≥ the square root (https://en.wikipedia.org/wiki/Square_root, https://www.rieselprime.de/ziki/Square_root, https://mathworld.wolfram.com/SquareRoot.html) of it)
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://www.prothsearch.com/Proth-k-1200-I.txt, http://www.prothsearch.com/Proth-k-1200-II.txt, http://www.prothsearch.com/Proth-k-1200-III.txt, http://www.prothsearch.com/Proth-k-10000-I.txt, http://www.prothsearch.com/Proth-k-10000-II.txt, http://www.prothsearch.com/Proth-k-10000-III.txt, http://www.prothsearch.com/Proth-k-100000-I.txt, http://www.prothsearch.com/Proth-k-100000-II.txt, http://www.prothsearch.com/Proth-k-mega.txt, http://irvinemclean.com/maths/sierpin.htm, http://irvinemclean.com/maths/sierpin2.htm, http://irvinemclean.com/maths/sierpin3.htm, http://irvinemclean.com/maths/sierhigh.txt, https://www.rieselprime.de/Data/P00001.htm, https://www.rieselprime.de/Data/P00300.htm, https://www.rieselprime.de/Data/P02000.htm, https://www.rieselprime.de/Data/P04000.htm, https://www.rieselprime.de/Data/P06000.htm, https://www.rieselprime.de/Data/P08000.htm, https://www.rieselprime.de/ziki/Proth_2_1-300, https://www.rieselprime.de/ziki/Proth_2_300-2000, https://www.rieselprime.de/ziki/Proth_2_2000-4000, https://www.rieselprime.de/ziki/Proth_2_4000-6000, https://www.rieselprime.de/ziki/Proth_2_6000-8000, https://www.rieselprime.de/ziki/Proth_2_8000-10000, https://www.rieselprime.de/ziki/Proth_2_10e4-10e5, https://www.rieselprime.de/ziki/Proth_2_10e5-10e6, https://www.rieselprime.de/ziki/Proth_2_10e6-10e7, https://www.rieselprime.de/ziki/Proth_2_10e7-10e8, https://www.rieselprime.de/ziki/Proth_2_10e8-10e9, https://www.rieselprime.de/ziki/Proth_2_10e9-10e10, https://www.rieselprime.de/ziki/Proth_2_10e10-infinity, https://harvey563.tripod.com/proths.txt, https://sites.google.com/view/proth-primes, https://www.primegrid.com/forum_thread.php?id=7945, https://www.primegrid.com/forum_thread.php?id=2665, https://www.primegrid.com/stats_321_llr.php, https://www.primegrid.com/stats_pps_llr.php, https://www.primegrid.com/stats_ppse_llr.php, https://www.primegrid.com/stats_mega_llr.php, https://www.primegrid.com/primes/primes.php?project=321&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=27&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=121&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PPS&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PPSE&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=MEG&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://web.archive.org/web/20231223043356/https://www.mersenneforum.org/321search/index.html, https://web.archive.org/web/20110601231527/http://www.bodang.com/12121/, https://web.archive.org/web/20100518081012/http://www.bodang.com/12121/27k/, https://oeis.org/A002253, https://oeis.org/A002254, https://oeis.org/A032353, https://oeis.org/A002256, https://oeis.org/A002261, https://oeis.org/A032356, https://oeis.org/A002258, https://oeis.org/A002259, https://oeis.org/A032359, https://oeis.org/A032360, https://oeis.org/A032361, https://oeis.org/A032362, https://oeis.org/A032363, https://oeis.org/A032364, https://oeis.org/A032365, https://oeis.org/A032366, https://oeis.org/A032367, https://oeis.org/A032368, https://oeis.org/A002269, https://oeis.org/A032370, https://oeis.org/A032371, https://oeis.org/A032372, https://oeis.org/A032373, https://oeis.org/A032374, https://oeis.org/A032375, https://oeis.org/A032376, https://oeis.org/A032377, https://oeis.org/A002274, https://oeis.org/A032379, https://oeis.org/A032380, https://oeis.org/A032381, https://oeis.org/A032382, https://oeis.org/A032383, https://oeis.org/A032384, https://oeis.org/A032385, https://oeis.org/A032386, https://oeis.org/A032387, https://oeis.org/A032388, https://oeis.org/A032389, https://oeis.org/A032390, https://oeis.org/A032391, https://oeis.org/A032392, https://oeis.org/A032393, https://oeis.org/A032394, https://oeis.org/A032395, https://oeis.org/A032396, https://oeis.org/A032397, https://oeis.org/A032398, https://oeis.org/A032399)	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, https://web.archive.org/web/20091027083904/http://www.geocities.com/primes_r_us/riesel/prime300.html, https://web.archive.org/web/20091027083901/http://www.geocities.com/primes_r_us/riesel/prime400.html, https://web.archive.org/web/20091027083903/http://www.geocities.com/primes_r_us/riesel/prime500.html, https://web.archive.org/web/20091027083858/http://www.geocities.com/primes_r_us/riesel/prime600.html, https://web.archive.org/web/20091027083905/http://www.geocities.com/primes_r_us/riesel/prime700.html, https://web.archive.org/web/20091027083900/http://www.geocities.com/primes_r_us/riesel/prime800.html, https://web.archive.org/web/20091027083906/http://www.geocities.com/primes_r_us/riesel/prime900.html, http://www.noprimeleftbehind.net/gary/primes-kx2n-1-001.htm, http://www.noprimeleftbehind.net/gary/Rieselprimes-ranges.htm, https://www.rieselprime.de/Data/00001.htm, https://www.rieselprime.de/Data/00300.htm, https://www.rieselprime.de/Data/02000.htm, https://www.rieselprime.de/Data/04000.htm, https://www.rieselprime.de/Data/06000.htm, https://www.rieselprime.de/Data/08000.htm, https://www.rieselprime.de/Data/10e04.htm, https://www.rieselprime.de/Data/10e05.htm, https://www.rieselprime.de/Data/10e06.htm, https://www.rieselprime.de/Data/10e07.htm, https://www.rieselprime.de/Data/10e08.htm, https://www.rieselprime.de/Data/10e09.htm, https://www.rieselprime.de/Data/10e10.htm, https://www.rieselprime.de/Data/10e04a.txt, https://www.rieselprime.de/ziki/Riesel_2_1-300, https://www.rieselprime.de/ziki/Riesel_2_300-2000, https://www.rieselprime.de/ziki/Riesel_2_2000-4000, https://www.rieselprime.de/ziki/Riesel_2_4000-6000, https://www.rieselprime.de/ziki/Riesel_2_6000-8000, https://www.rieselprime.de/ziki/Riesel_2_8000-10000, https://www.rieselprime.de/ziki/Riesel_2_10e4-10e5, https://www.rieselprime.de/ziki/Riesel_2_10e5-10e6, https://www.rieselprime.de/ziki/Riesel_2_10e6-10e7, https://www.rieselprime.de/ziki/Riesel_2_10e7-10e8, https://www.rieselprime.de/ziki/Riesel_2_10e8-10e9, https://www.rieselprime.de/ziki/Riesel_2_10e9-10e10, https://www.rieselprime.de/ziki/Riesel_2_10e10-infinity, https://harvey563.tripod.com/reisels.txt, https://sites.google.com/view/proth-primes, https://www.primegrid.com/forum_thread.php?id=7945, https://www.primegrid.com/stats_321_llr.php, https://www.primegrid.com/primes/primes.php?project=321&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=27&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=121&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://web.archive.org/web/20231223043356/https://www.mersenneforum.org/321search/index.html, https://web.archive.org/web/20110601231527/http://www.bodang.com/12121/, https://web.archive.org/web/20100518081012/http://www.bodang.com/12121/27k/, https://oeis.org/A002235, https://oeis.org/A001770, https://oeis.org/A001771, https://oeis.org/A002236, https://oeis.org/A001772, https://oeis.org/A001773, https://oeis.org/A002237, https://oeis.org/A001774, https://oeis.org/A001775, https://oeis.org/A002238, https://oeis.org/A050537, https://oeis.org/A050538, https://oeis.org/A050539, https://oeis.org/A050540, https://oeis.org/A050541, https://oeis.org/A002240, https://oeis.org/A050543, https://oeis.org/A050544, https://oeis.org/A050545, https://oeis.org/A050546, https://oeis.org/A050547, https://oeis.org/A002242, https://oeis.org/A050549, https://oeis.org/A050550, https://oeis.org/A050551, https://oeis.org/A050552, https://oeis.org/A050553, https://oeis.org/A050554, https://oeis.org/A050555, https://oeis.org/A050556, https://oeis.org/A050557, https://oeis.org/A050558, https://oeis.org/A050559, https://oeis.org/A050560, https://oeis.org/A050561, https://oeis.org/A050562, https://oeis.org/A050563, https://oeis.org/A050564, https://oeis.org/A050565, https://oeis.org/A050566, https://oeis.org/A050567, https://oeis.org/A050568, https://oeis.org/A050569, https://oeis.org/A050570, https://oeis.org/A050571, https://oeis.org/A050572, https://oeis.org/A050573, https://oeis.org/A050574, https://oeis.org/A050575)
List of primes of the form k×10ⁿ+1 with k neither divisible by 10 nor == 2 mod 3 (https://stdkmd.net/nrr/prime/prime_p1.htm, https://stdkmd.net/nrr/prime/prime_p1.txt, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#k10np1, https://oeis.org/A056807, https://oeis.org/A056806, https://oeis.org/A056805, https://oeis.org/A056804, https://oeis.org/A056797, https://oeis.org/A294396, https://oeis.org/A289051, https://oeis.org/A295325, https://oeis.org/A273002, https://oeis.org/A282456, https://oeis.org/A267420, https://oeis.org/A109397, https://oeis.org/A171612, https://oeis.org/A293824, https://oeis.org/A271107, https://oeis.org/A282280, https://oeis.org/A276118, https://oeis.org/A267865, https://oeis.org/A004203, https://oeis.org/A109800, https://oeis.org/A271361, https://oeis.org/A109503, https://oeis.org/A293001, https://oeis.org/A109749, https://oeis.org/A109713 (unfortunately, currently there are no OEIS sequences for k = 21, 24, 27, 31, 34, 36, 37, 43, 45, 46, 48, 51, 52, 57, 58, 61, 64, 67, 72, 73, 75, 76, 78, 79, 81, 82, 84, 85, 87, 91, 93, 94, 96, 97))	List of primes of the form k×10ⁿ−1 with k neither divisible by 10 nor == 1 mod 3 (http://www.noprimeleftbehind.net/gary/primes-kx10n-1.htm, https://stdkmd.net/nrr/prime/prime_m1.htm, https://stdkmd.net/nrr/prime/prime_m1.txt, https://web.archive.org/web/20240202224722/https://stdkmd.net/nrr/records.htm#k10nm1, https://oeis.org/A002957, https://oeis.org/A056703, https://oeis.org/A056712, https://oeis.org/A056716, https://oeis.org/A056721, https://oeis.org/A056725, https://oeis.org/A111391, https://oeis.org/A257036, https://oeis.org/A257037, https://oeis.org/A257038, https://oeis.org/A257039, https://oeis.org/A257040, https://oeis.org/A257041 (unfortunately, currently there are no OEIS sequences for 12 ≤ k ≤ 89))
Sierpinski problem (http://www.prothsearch.com/sierp.html, https://www.primegrid.com/forum_thread.php?id=1647, https://www.primegrid.com/forum_thread.php?id=972, https://www.primegrid.com/forum_thread.php?id=1750, https://www.primegrid.com/forum_thread.php?id=5758, https://www.primegrid.com/stats_sob_llr.php, https://www.primegrid.com/stats_psp_llr.php, https://www.primegrid.com/stats_esp_llr.php, https://www.primegrid.com/primes/primes.php?project=SOB&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=PSP&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.primegrid.com/primes/primes.php?project=ESP&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://web.archive.org/web/20160405211049/http://www.seventeenorbust.com/, https://en.wikipedia.org/wiki/Sierpi%C5%84ski_number, https://t5k.org/glossary/xpage/SierpinskiNumber.html, https://www.rieselprime.de/ziki/Sierpi%C5%84ski_number, https://www.rieselprime.de/ziki/Sierpi%C5%84ski_problem, https://www.rieselprime.de/ziki/Proth_2_Sierpinski, https://www.rieselprime.de/ziki/Proth_2_Count-0, 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), http://jpenne.free.fr/Sierpeven/, https://www.ams.org/journals/mcom/1983-40-161/S0025-5718-1983-0679453-8/S0025-5718-1983-0679453-8.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_40.pdf), https://www.fq.math.ca/Scanned/33-3/izotov.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_46.pdf), http://www.digizeitschriften.de/download/PPN378850199_0015/PPN378850199_0015___log24.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_213.pdf), https://www.ams.org/journals/mcom/1981-37-155/S0025-5718-1981-0616376-2/S0025-5718-1981-0616376-2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_214.pdf), https://www.ams.org/journals/mcom/1983-41-164/S0025-5718-1983-0717710-7/S0025-5718-1983-0717710-7.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_215.pdf), http://www.iakovlev.org/zip/riesel2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_8.pdf), https://doi.org/10.1016/j.jnt.2008.02.004 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_47.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_51.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL18/Baczkowski/bacz2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_61.pdf), https://arxiv.org/pdf/1110.4671.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_62.pdf), 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 Sierpinski numbers	Riesel problem (http://www.prothsearch.com/rieselprob.html, https://www.primegrid.com/forum_thread.php?id=1731, https://www.primegrid.com/stats_trp_llr.php, https://www.primegrid.com/primes/primes.php?project=TRP&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://web.archive.org/web/20061021145019/http://rieselsieve.com/, https://web.archive.org/web/20061021153313/http://stats.rieselsieve.com//queue.php, https://en.wikipedia.org/wiki/Riesel_number, https://t5k.org/glossary/xpage/RieselNumber.html, https://www.rieselprime.de/ziki/Riesel_number, https://www.rieselprime.de/ziki/Riesel_problem_1, https://www.rieselprime.de/ziki/Riesel_problem_2, https://www.rieselprime.de/ziki/Riesel_problem_3, https://www.rieselprime.de/ziki/Riesel_problem_4, https://www.rieselprime.de/ziki/Riesel_2_Riesel, https://www.rieselprime.de/ziki/Riesel_2_Count-0, https://mathworld.wolfram.com/RieselNumber.html, https://en.wikipedia.org/wiki/Riesel_Sieve, https://www.rieselprime.de/ziki/Riesel_Sieve, https://www.rieselprime.de/ziki/PrimeGrid_The_Riesel_Problem, http://www.bitman.name/math/article/203 (in Italian), http://www.iakovlev.org/zip/riesel2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_8.pdf), https://doi.org/10.1016/j.jnt.2008.02.004 (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_47.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL16/Ismailescu/ismailescu3.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_51.pdf), https://cs.uwaterloo.ca/journals/JIS/VOL18/Baczkowski/bacz2.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_61.pdf), https://arxiv.org/pdf/1110.4671.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_62.pdf), 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, k replaced by k+1), 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), https://oeis.org/A046068 (odd k, n = 0 allowed, second n))	Smallest n such that k×2ⁿ−1 is prime (https://oeis.org/A050412 (k replaced by k−1), https://oeis.org/A052333 (corresponding primes, k replaced by k−1), 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), https://oeis.org/A257495 (k such that k−1 is prime, k replaced by k−1), https://oeis.org/A046070 (odd k, n = 0 allowed, second n))
Smallest k such that k×2ⁿ+1 is prime (https://oeis.org/A035050, https://oeis.org/A035089 (corresponding primes), https://oeis.org/A057778 (only odd k allowed), https://oeis.org/A057775 (only odd k allowed, corresponding primes), https://oeis.org/A051886 (only prime k allowed), https://oeis.org/A051900 (only prime k allowed, corresponding primes), https://oeis.org/A134855 (only odd prime k allowed), https://oeis.org/A134854 (only odd prime k allowed, corresponding primes))	Smallest k such that k×2ⁿ−1 is prime (https://oeis.org/A085427, https://oeis.org/A127582 (corresponding primes), https://oeis.org/A126717 (only odd k allowed), https://oeis.org/A201914 (only odd k allowed, corresponding primes), https://oeis.org/A126715 (only odd prime k allowed))
Smallest k such that k×10ⁿ+1 is prime (https://oeis.org/A121172, https://oeis.org/A070854 (corresponding primes))	Smallest k such that k×10ⁿ−1 is prime (https://oeis.org/A120642, https://oeis.org/A065582 (only k not divisible by 10 allowed, corresponding primes))
Real Sierpinski problem (http://boincvm.proxyma.ru:30080/test4vm/public/pps_snob_problem.php, https://www.primegrid.com/forum_thread.php?id=9107, https://www.rieselprime.de/ziki/PrimeGrid_New_Sierpi%C5%84ski_Problem), finding and proving the smallest odd k such that k×2ⁿ+1 is composite for all n such that 2ⁿ > k (i.e. all "Proth numbers" of the form k×2ⁿ+1 are composite, i.e. there is no "Proth prime" of the form k×2ⁿ+1), the smallest such k is conjectured to be 78557	Real Riesel problem (http://www.noprimeleftbehind.net/crus/Real-Riesel-conjectures.htm, http://www.noprimeleftbehind.net/crus/Real-Riesel-conjecture-reserves.htm, http://www.noprimeleftbehind.net/crus/Real-Riesel-conjecture-base2-remain.htm, http://www.noprimeleftbehind.net/crus/all-ks-real-riesel-base2.zip, https://www.rieselprime.de/ziki/Riesel_problem_real_1, https://www.mersenneforum.org/showthread.php?t=29051), finding and proving the smallest odd k such that k×2ⁿ−1 is composite for all n such that 2ⁿ > k (i.e. all "Proth numbers of the second kind" of the form k×2ⁿ−1 are composite, i.e. there is no "Proth prime of the second kind" of the form k×2ⁿ−1), the smallest such k is conjectured to be 509203
Dual Sierpinski 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://www.mersenneforum.org/showthread.php?t=10761), finding and proving the smallest odd k such that 2ⁿ+k is composite for all n ≥ 1, the smallest such k is conjectured to be 78557	Dual Riesel problem (https://www.mersenneforum.org/showthread.php?t=6545), finding and proving the smallest odd k such that \|2ⁿ−k\| is composite for all n ≥ 1, the smallest such k is conjectured to be 509203
List of primes of the form 2ⁿ+k with odd k (https://sites.google.com/view/proth-primes, https://oeis.org/A057732, https://oeis.org/A059242, https://oeis.org/A057195, https://oeis.org/A057196, https://oeis.org/A102633, https://oeis.org/A102634, https://oeis.org/A057197, https://oeis.org/A057200, https://oeis.org/A057221, https://oeis.org/A057201, https://oeis.org/A057203, https://oeis.org/A157006, https://oeis.org/A157007, https://oeis.org/A156982, https://oeis.org/A247952, https://oeis.org/A247953, https://oeis.org/A220077 (unfortunately, currently there are no OEIS sequences for 37 ≤ k ≤ 99))	List of primes of the form 2ⁿ−k with odd k (https://sites.google.com/view/proth-primes, https://oeis.org/A050414, https://oeis.org/A059608, https://oeis.org/A059609, https://oeis.org/A059610, https://oeis.org/A096817, https://oeis.org/A096818, https://oeis.org/A059612, https://oeis.org/A059611, https://oeis.org/A096819, https://oeis.org/A096820, https://oeis.org/A057202 (allow negative primes), https://oeis.org/A057220 (allow negative primes), https://oeis.org/A356826 (unfortunately, currently there are no OEIS sequences for 25 ≤ k ≤ 99 except k = 29, also for k = 23 only "allow negative primes" version exists in OEIS))
List of primes of the form 10ⁿ+k with k coprime to 10 and not == 2 mod 3 (https://stdkmd.net/nrr/prime/prime_pk.htm, https://stdkmd.net/nrr/prime/prime_pk.txt, https://oeis.org/A049054, https://oeis.org/A088274, https://oeis.org/A088275, https://oeis.org/A095688, https://oeis.org/A108052, https://oeis.org/A108050, https://oeis.org/A108312, https://oeis.org/A107083, https://oeis.org/A107084, https://oeis.org/A135109, https://oeis.org/A135108, https://oeis.org/A108049, https://oeis.org/A108054, https://oeis.org/A135118, https://oeis.org/A135119, https://oeis.org/A135116, https://oeis.org/A135115, https://oeis.org/A135113, https://oeis.org/A135114, https://oeis.org/A135132, https://oeis.org/A135131, https://oeis.org/A137848, https://oeis.org/A135117, https://oeis.org/A110918, https://oeis.org/A135112, https://oeis.org/A135107, https://oeis.org/A110980)	List of primes of the form 10ⁿ−k with k coprime to 10 and not == 1 mod 3 (https://stdkmd.net/nrr/prime/prime_mk.htm, https://stdkmd.net/nrr/prime/prime_mk.txt, https://oeis.org/A089675, https://oeis.org/A095714, https://oeis.org/A092767, https://oeis.org/A108326, https://oeis.org/A108327, https://oeis.org/A108328, https://oeis.org/A108329, https://oeis.org/A108330, https://oeis.org/A108364, https://oeis.org/A108365, https://oeis.org/A178406, https://oeis.org/A178175, https://oeis.org/A178429, https://oeis.org/A178430, https://oeis.org/A108493, https://oeis.org/A108506, https://oeis.org/A178433, https://oeis.org/A177866, https://oeis.org/A178434, https://oeis.org/A178436, https://oeis.org/A178437, https://oeis.org/A178438, https://oeis.org/A108331, https://oeis.org/A108332, https://oeis.org/A178531, https://oeis.org/A178439)
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), https://oeis.org/A252168 (allow negative primes), https://oeis.org/A276417 (only negative primes), https://oeis.org/A188903 (only negative primes, n replaced by 2ⁿ))
Smallest k such that 2ⁿ+k is prime (https://oeis.org/A013597, https://oeis.org/A092131 (k = 0 allowed), https://oeis.org/A014210 (corresponding primes), https://oeis.org/A104080 (k = 0 allowed, corresponding primes))	Smallest k such that 2ⁿ−k is prime (https://oeis.org/A013603 (k = 0 allowed), https://oeis.org/A014234 (k = 0 allowed, corresponding primes))
Smallest k such that 10ⁿ+k is prime (https://oeis.org/A033873, https://oeis.org/A003617 (corresponding primes, n replaced by n−1))	Smallest k such that 10ⁿ−k is prime (https://oeis.org/A033874, https://oeis.org/A003618 (corresponding primes))
Generalized Sierpinski 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, https://web.archive.org/web/20230928115832/http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_sierpinski.txt, https://web.archive.org/web/20231011144408/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, https://web.archive.org/web/20230928115850/http://www.noprimeleftbehind.net/crus/vstats_new/all_ck_riesel.txt, http://www.bitman.name/math/article/2005 (in Italian), https://oeis.org/A273987), finding and proving the smallest k such that k×bⁿ−1 is composite for all n ≥ 1
Sophie Germain prime (https://en.wikipedia.org/wiki/Sophie_Germain_prime, https://t5k.org/glossary/xpage/SophieGermainPrime.html, https://www.rieselprime.de/ziki/Sophie_Germain_prime, https://mathworld.wolfram.com/SophieGermainPrime.html, https://www.numbersaplenty.com/set/Sophie_Germain_prime/, https://oeis.org/A005384, https://t5k.org/top20/page.php?id=2, https://t5k.org/primes/search.php?Comment=Sophie%20Germain&OnList=all&Number=1000000&Style=HTML, https://www.primegrid.com/forum_thread.php?id=1450, https://www.primegrid.com/stats_sgs_llr.php, https://www.primegrid.com/primes/primes.php?project=SGS&factors=XGF&only=ALL&announcements=ALL&sortby=size&dc=yes&search=, https://www.rieselprime.de/Related/RieselTwinSG.htm, https://www.primepuzzles.net/problems/prob_049.htm, https://www.rieselprime.de/ziki/PrimeGrid_Sophie_Germain_Search)	Sophie Germain prime of the second kind (https://oeis.org/A005382, https://harvey563.tripod.com/cunninghams.txt)
Safe prime (https://en.wikipedia.org/wiki/Safe_prime, https://t5k.org/glossary/xpage/SafePrime.html, https://oeis.org/A005385, https://www.rieselprime.de/Related/RieselTwinSG.htm, https://www.primepuzzles.net/problems/prob_049.htm)	Safe prime of the second kind (https://oeis.org/A005383, https://harvey563.tripod.com/cunninghams.txt)
Cunningham chain of the first kind (https://en.wikipedia.org/wiki/Cunningham_chain, https://t5k.org/glossary/xpage/CunninghamChain.html, https://mathworld.wolfram.com/CunninghamChain.html, https://t5k.org/top20/page.php?id=19, https://t5k.org/primes/search.php?Comment=Cunningham%20chain&OnList=all&Number=1000000&Style=HTML, https://www.pzktupel.de/JensKruseAndersen/CC.php, http://www.primerecords.dk/Cunningham_Chain_records.htm, http://www.primenumbers.net/Henri/us/NouvTh1us.htm, https://web.archive.org/web/20050406075848/http://ksc9.th.com/warut/cunningham.html, https://oeis.org/A005602, https://oeis.org/A057331)	Cunningham chain of the second kind (https://en.wikipedia.org/wiki/Cunningham_chain, https://t5k.org/glossary/xpage/CunninghamChain.html, https://mathworld.wolfram.com/CunninghamChain.html, https://t5k.org/top20/page.php?id=20, https://t5k.org/primes/search.php?Comment=Cunningham%20chain&OnList=all&Number=1000000&Style=HTML, https://www.pzktupel.de/JensKruseAndersen/CC.php, http://www.primerecords.dk/Cunningham_Chain_records.htm, http://www.primenumbers.net/Henri/us/NouvTh1us.htm, https://web.archive.org/web/20050406075848/http://ksc9.th.com/warut/cunningham.html, https://oeis.org/A005603, https://oeis.org/A057330)
Pierpont prime (class 1− prime) (https://en.wikipedia.org/wiki/Pierpont_prime, https://t5k.org/glossary/xpage/PierpontPrime.html, https://mathworld.wolfram.com/PierpontPrime.html, https://www.numbersaplenty.com/set/Pierpont_prime/, 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, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (section "Pollard p-1:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=p-1&maxrows=10000, http://www.numericana.com/answer/factoring.htm#p-1, http://factordb.com/listecm.php?c=2, http://www.loria.fr/~zimmerma/records/Pminus1.html, https://web.archive.org/web/20021015212913/http://www.users.globalnet.co.uk/~aads/Pminus1.html, https://web.archive.org/web/20231002022529/https://colin.barker.pagesperso-orange.fr/lpa/big_pm1.htm, https://www.mersenne.org/report_pminus1/, https://www.mersenne.ca/userfactors/pm1/1, https://www.mersenne.ca/smooth.php, https://www.mersenne.ca/p1missed.php, https://www.mersenne.ca/prob.php)	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, https://homes.cerias.purdue.edu/~ssw/cun/champ.txt (section "p+1:"), http://mklasson.com/factors/viewlog.php?sort=2&order=desc&method=p%2b1&maxrows=10000, http://www.numericana.com/answer/factoring.htm#p+1, http://factordb.com/listecm.php?c=3, http://www.loria.fr/~zimmerma/records/Pplus1.html, https://www.mersenne.org/report_pplus1/, https://www.mersenne.ca/userfactors/pp1/1, https://www.mersenne.ca/pplus1.php)

Two references of many types of pseudoprimes: http://ntheory.org/pseudoprimes.html and http://gilchrist.ca/jeff/factoring/pseudoprimes.html; also references of data for all base 2 Fermat pseudoprimes < 2⁶⁴: http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html and https://web.archive.org/web/20220921163920/http://www.janfeitsma.nl/math/psp2/index; 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://ceur-ws.org/Vol-1326/020-Forisek.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_481.pdf), https://t5k.org/curios/page.php?number_id=4265, https://t5k.org/prove/prove2_3.html, https://faculty.lynchburg.edu/~nicely/misc/mpzspsp.html, https://miller-rabin.appspot.com/, http://www.pi-e.de/Miller-Rabin-Pseudoprimzahlen.htm (in German), 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 A3₅₉₂₁₉₇A (base 13) is in fact composite, then A{3}A 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://t5k.org/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html, https://web.archive.org/web/20230911032453/https://www.utm.edu/staff/caldwell/preprints/Heuristics.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_112.pdf), https://arxiv.org/pdf/2103.04483.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_113.pdf)) that all unsolved families have a prime, this is reasonable, references: https://t5k.org/mersenne/heuristic.html, https://t5k.org/notes/faq/NextMersenne.html, https://t5k.org/glossary/xpage/Repunit.html, https://web.archive.org/web/20100628035147/http://www.math.niu.edu/~rusin/known-math/98/exp_primes, https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;417ab0d6.0906, https://mathoverflow.net/questions/268918/density-of-primes-in-sequences-of-the-form-anb, https://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Archives/Mathematics/2023_September_25#Are_there_infinitely_many_primes_of_the_form_1000%E2%80%A60007.2C_333%E2%80%A63331.2C_7111%E2%80%A6111.2C_or_3444%E2%80%A64447_in_base_10?, https://arxiv.org/pdf/2307.07894.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_203.pdf), https://web.archive.org/web/20231002020455/http://yves.gallot.pagesperso-orange.fr/papers/weight.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_216.pdf), https://www.mersenneforum.org/showthread.php?t=12327, https://oeis.org/A234285 (the comment by Farideh Firoozbakht, although this comment is not true, there is no prime for s = 509203 and s = −78557, s = 509203 has a covering set of {3, 5, 7, 13, 17, 241}, and s = −78557 has a covering set of {3, 5, 7, 13, 19, 37, 73}), https://www.mersenneforum.org/showpost.php?p=564786&postcount=3, https://www.mersenneforum.org/showpost.php?p=461665&postcount=7, https://www.mersenneforum.org/showpost.php?p=354505&postcount=5, https://www.mersenneforum.org/showpost.php?p=344985&postcount=293, https://www.mersenneforum.org/showpost.php?p=625978&postcount=1027, https://www.primegrid.com/forum_thread.php?id=5093&nowrap=true#66471, https://www.primegrid.com/forum_thread.php?id=4935&nowrap=true#63813, also the graphs https://t5k.org/gifs/lg_lg_Mn.gif (for the family {1} in base b = 2) and https://t5k.org/gifs/repunits.gif (for the family {1} in base b = 10) and https://www.mersenneforum.org/attachment.php?attachmentid=4010&d=1642088235 (for the family 2{0}1 in base b = 3), we can only definitely say that there are either 25528 or 25529 minimal primes in base 28 if we assume the heuristic argument (https://en.wikipedia.org/wiki/Heuristic_argument, https://t5k.org/glossary/xpage/Heuristic.html, https://mathworld.wolfram.com/Heuristic.html, https://web.archive.org/web/20230911032453/https://www.utm.edu/staff/caldwell/preprints/Heuristics.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_112.pdf), https://arxiv.org/pdf/2103.04483.pdf (cached copy at https://github.com/xayahrainie4793/pdf-files-cached-copy/blob/main/pdf_113.pdf)) that all unsolved families have a prime).
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, this n is written in decimal)
File "unprovenPRPalgebraic b": The algebraic ((a×bⁿ+c)/gcd(a+c,b−1)) form of the unproven probable primes which are minimal primes in base b (assuming their primality)
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://t5k.org/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 (for more input files for Primo in factordb, see http://factordb.com/primobatch.php and http://factordb.com/primobatch.php?digits=300&files=10&parts=1&start=Generate+zip and http://factordb.com/primobatch.php?digits=300&files=32000&parts=32&start=Generate+zip). (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) and A3₅₉₂₁₉₇A in base 13 (which equals the probable prime (41×13⁵⁹²¹⁹⁸+27)/4) since these two probable primes are 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))

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Files

unproven-probable-primes

unproven-probable-primes

README.md

Files

unproven-probable-primes

Directory actions

More options

Directory actions

More options

Latest commit

History

unproven-probable-primes

Folders and files

parent directory

README.md