Skip to content
main
Switch branches/tags

Name already in use

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

Files

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

These are the Primo (http://www.ellipsa.eu/public/primo/primo.html, http://www.rieselprime.de/dl/Primo309.zip, https://primes.utm.edu/bios/page.php?id=46, https://www.rieselprime.de/ziki/Primo, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/primo-433-lx64) (an elliptic curve primality proving (https://primes.utm.edu/prove/prove4_2.html, https://en.wikipedia.org/wiki/Elliptic_curve_primality, https://primes.utm.edu/glossary/xpage/ECPP.html, https://mathworld.wolfram.com/EllipticCurvePrimalityProving.html) implementation) primality certificates (https://en.wikipedia.org/wiki/Primality_certificate, https://primes.utm.edu/glossary/xpage/Certificate.html, https://mathworld.wolfram.com/PrimalityCertificate.html) for the minimal primes > 10300 in bases 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 28, 30 (local copy from factordb (http://factordb.com/)).

e.g. File "certificate9_149" is the primality certificate for the 149th minimal prime in base 9, i.e. the primality certificate for the prime 763292 in base 9, which equals the prime (31×9330−19)/4.

Primes which either N−1 or N+1 is trivially fully factored (i.e. primes of the form k×bn±1, with small k) do not need primality certificates, since they can be easily proven primes using N−1 test (https://primes.utm.edu/prove/prove3_1.html) or N+1 test (https://primes.utm.edu/prove/prove3_2.html), these primes are:

the 3176th minimal prime in base 13, 810104151, which equals 17746×13416+1, N−1 is trivially fully factored

the 3177th minimal prime in base 13, 81104351, which equals 1366×13436+1, N−1 is trivially fully factored

the 3188th minimal prime in base 13, 93015511, which equals 120×131552+1, N−1 is trivially fully factored

the 3191st minimal prime in base 13, 39062661, which equals 48×136267+1, N−1 is trivially fully factored

the 649th minimal prime in base 14, 34D708, which equals 47×14708−1, N+1 is trivially fully factored

the 650th minimal prime in base 14, 4D19698, which equals 5×1419698−1, N+1 is trivially fully factored

the 2335th minimal prime in base 16, 88F545, which equals 137×16545−1, N+1 is trivially fully factored

the 3310th minimal prime in base 20, JCJ629, which equals 393×20629−1, N+1 is trivially fully factored

the 3408th minimal prime in base 24, 88N5951, which equals 201×245951−1, N+1 is trivially fully factored

the 25509th minimal prime in base 28, EB04051, which equals 403×28406+1, N−1 is trivially fully factored

the 2616th minimal prime in base 30, C010221, which equals 12×301023+1, N−1 is trivially fully factored

the 2619th minimal prime in base 30, OT34205, which equals 25×3034205−1, N+1 is trivially fully factored

Also the case where N−1 or N+1 is product of a Cunningham number (of the form bn±1, see https://en.wikipedia.org/wiki/Cunningham_number, https://mathworld.wolfram.com/CunninghamNumber.html, https://en.wikipedia.org/wiki/The_Cunningham_project, https://primes.utm.edu/glossary/xpage/CunninghamProject.html, https://www.rieselprime.de/ziki/Cunningham_project, https://homes.cerias.purdue.edu/~ssw/cun/index.html, https://maths-people.anu.edu.au/~brent/factors.html, http://myfactors.mooo.com/) and a small number, and this Cunningham number is ≥ 1/4 factored (https://en.wikipedia.org/wiki/Integer_factorization, https://www.rieselprime.de/ziki/Factorization, https://mathworld.wolfram.com/PrimeFactorization.html), see the article http://www.ams.org/journals/mcom/1975-29-130/S0025-5718-1975-0384673-1/S0025-5718-1975-0384673-1.pdf for the case that either N−1 or N+1 (or both) can be ≥ 1/3 factored, if either N−1 or N+1 (or both) can be ≥ 1/4 factored but neither can be ≥ 1/3 factored, then we need to use CHG (https://mersenneforum.org/attachment.php?attachmentid=21133&d=1571237465, https://primes.utm.edu/bios/page.php?id=797, https://github.com/xayahrainie4793/prime-programs-cached-copy/tree/main/CHG) to prove its primality (see https://mersenneforum.org/showpost.php?p=528149&postcount=3), for the examples of the numbers which are proven prime by CHG, see https://primes.utm.edu/primes/page.php?id=126454, https://primes.utm.edu/primes/page.php?id=131964, https://primes.utm.edu/primes/page.php?id=123456, https://primes.utm.edu/primes/page.php?id=130933, https://stdkmd.net/nrr/cert/1/ (search for "CHG"), https://stdkmd.net/nrr/cert/2/ (search for "CHG"), https://stdkmd.net/nrr/cert/3/ (search for "CHG"), https://stdkmd.net/nrr/cert/4/ (search for "CHG"), https://stdkmd.net/nrr/cert/5/ (search for "CHG"), https://stdkmd.net/nrr/cert/6/ (search for "CHG"), https://stdkmd.net/nrr/cert/7/ (search for "CHG"), https://stdkmd.net/nrr/cert/8/ (search for "CHG"), https://stdkmd.net/nrr/cert/9/ (search for "CHG"), however, factordb (http://factordb.com/) lacks the ability to verify CHG proofs, see https://mersenneforum.org/showpost.php?p=608362&postcount=165: (thus these numbers also do not need primality certificates)

The Cunningham numbers bn±1 has algebraic factorization to product of Φd(b) with positive integers d dividing n (the bn−1 case) or positive integers d dividing 2×n but not dividing n (the bn+1 case), where Φ is the cyclotomic polynomial (https://en.wikipedia.org/wiki/Cyclotomic_polynomial, https://mathworld.wolfram.com/CyclotomicPolynomial.html) (see https://stdkmd.net/nrr/repunit/repunitnote.htm and https://www.mersenneforum.org/attachment.php?attachmentid=7727&d=1330555980 and https://homes.cerias.purdue.edu/~ssw/cun/mine.pdf)

(below, "Rn(b)" means the repunit (https://en.wikipedia.org/wiki/Repunit, https://primes.utm.edu/glossary/xpage/Repunit.html, https://primes.utm.edu/glossary/xpage/GeneralizedRepunitPrime.html, https://www.rieselprime.de/ziki/Repunit, https://mathworld.wolfram.com/Repunit.html) in base b with length n, i.e. Rn(b) = (bn−1)/(b−1), "Sn(b)" means bn+1, the special cases of Rn(10) and Sn(10) are in https://stdkmd.net/nrr/repunit/ and https://stdkmd.net/nrr/repunit/10001.htm, respectively, in fact, Rn(b) and Sn(b) are 111...111 and 1000...0001 in base b, respectively)

the 3168th minimal prime in base 13, 93081, N−1 is 117×R308(13), thus factor N−1 is equivalent to factor 13308−1, and for the factorization of 13308−1, see http://myfactorcollection.mooo.com:8090/cgi-bin/showSingleEntry?Base=13&Exp=308&c0=-&EN=

the 3179th minimal prime in base 13, B563C, N−1 is 11×R564(13), thus factor N−1 is equivalent to factor 13564−1, and for the factorization of 13564−1, see http://myfactorcollection.mooo.com:8090/cgi-bin/showSingleEntry?Base=13&Exp=564&c0=-&EN=

the 3180th minimal prime in base 13, 1B576, N−1 is 23×R576(13), thus factor N−1 is equivalent to factor 13576−1, and for the factorization of 13576−1, see http://myfactorcollection.mooo.com:8090/cgi-bin/showSingleEntry?Base=13&Exp=576&c0=-&EN=

Although these numbers also have N−1 or N+1 is product of a Cunningham number and a small number, but since the corresponding Cunningham numbers are < 25% factored, these numbers still need primality certificates:

the 151st minimal prime in base 9, 30115811, N−1 is 9×S2319(3), thus factor N−1 is equivalent to factor 32319+1, N−1 is only 12.693% factored, and for the factorization of 32319+1, see http://myfactorcollection.mooo.com:8090/cgi-bin/showSingleEntry?Base=3&Exp=2319&c0=%2B&EN=

the 3187th minimal prime in base 13, 715041, N−1 is 91×R1504(13), thus factor N−1 is equivalent to factor 131504−1, N−1 is only 28.604% factored (since 28.604% is between 1/4 and 1/3, CHG proof is possible, however, since factordb (http://factordb.com/) lacks the ability to verify CHG proofs, thus there is still primality certificate in factordb), and for the factorization of 131504−1, see http://myfactorcollection.mooo.com:8090/cgi-bin/showSingleEntry?Base=13&Exp=1504&c0=-&EN=

the 2342nd minimal prime in base 16, 90354291, N−1 is 144×S3543(16), thus factor N−1 is equivalent to factor 163543+1, N−1 is only 1.255% factored, and for the factorization of 163543+1, see http://myfactorcollection.mooo.com:8090/cgi-bin/showSingleEntry?Base=16&Exp=3543&c0=%2B&EN=