Primality Certificate for (1756^3613-1)/1755 | ||
| Andy Steward | 11,720 digits | 30 December 2006 |
|---|---|---|
| Originally by A.A.D.Steward 2006 | ||
This certificate uses a theorem of Coppersmith and Howgrave-Graham to prove an integer N prime by making use of a partial prime factorization of N-1.
As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 28.022816% factorization of N-1:
| From | Factorisation |
|---|---|
| 1756 | 2 · 2 · 439 |
| Φ2 | 7 · 251 |
| Φ3 | 3 · 43 · 23917 |
| Φ4 | 3083537 |
| Φ6 | 19 · 61 · 2659 |
| Φ7 | 29 · 697595039 · 1450083727 |
| Φ12 | 9508191179761 |
| Φ14 | 7 · 9437 · 443575779523199 |
| Φ21 | p39 |
| Φ28 | 14533 · 97508956049 · 606588563051666994170093 |
| Φ42 | 972091 · p33 |
| Φ43 | 431 · 371177 · 180335220420114931 · 208711688927909783186077333 · p85 |
| Φ84 | 3571562821 · 5657257033 · 7902295853564204737 · 37621619945172911677 · 123008022584164314073 |
| Φ86 | 737385673 · 208544320217 · c117 |
| Φ129 | 43 · 50053 · 14910357157 · 185699540087134681 · p239 |
| Φ172 | 173 · 825986657 · 134192876241509 · p248 |
| Φ258 | c273 |
| Φ301 | 38662386869 · c808 |
| Φ516 | p546 |
| Φ602 | 4817 · 30703 · 390097 · 7125987779 · 7322257269794110393 · c776 |
| Φ903 | 5419 · 234781 · 4381357 · c1620 |
| Φ1204 | 220333 · 41510821006490501 · p1614 |
| Φ1806 | 226689849840238746151 · c1615 |
| Φ3612 | 3613 · 10837 · 86689 · 84195812019313 · 108359961821161 · c3230 |
We need the product F of all the prime factors from this partial factorization:
| 1901 5734339708 6794556190 8106373936 9379615298 1091702118 7789729845 2365372604 1860702886 7154434876 0854583786 0881930789 8646507167 3231977954 6782427616 8308003795 6622108252 9290584984 9991105856 0847240662 1413241860 9071515802 9536101389 2482892897 3735661806 7600592031 2007954967 2529210148 0087411569 1389343871 5989982173 0994621927 8354503302 2538706975 6099105685 0391424369 1777284077 1440223171 8557470264 1038099019 7669369018 5533982939 8480012743 3262832663 9691757451 8237863901 2006039597 9404371885 8176644479 8692757938 8452194226 8901471756 6852907505 6186653402 8397324947 6455986914 6693087713 8218405355 6151809570 3862044383 7439198392 7070883762 2853134921 9746404710 5378006380 9518705081 3240251534 6715836580 1952604167 5452670807 5205041078 2505242088 3474115617 3673718608 3013556472 4276911775 9242369803 0795738944 0648453058 4814942594 1807870926 8062114317 0203146948 3744316527 8586094348 2895347775 7822905308 7030132869 0022599547 3231689792 6775197430 3301297670 3652597580 9918967358 8164418651 9884017378 0887073943 1689470650 0079090538 2793872106 7075621416 2607560751 7970533307 4900761288 1268816024 9626565925 4236171551 9120288461 0024196938 7733099478 1373359759 1599410095 6366234851 3485715805 5740734558 4572658632 1428432476 3846364855 4277545185 1136727395 1894159016 6949681794 8504584141 5421176925 0388014789 6748031387 8815884428 3307278187 6118661866 3761463642 7969120330 9196522576 6122862811 7825991052 9361298678 1438928292 3888603469 4316479144 5241558985 5966712914 4320994468 7169728883 4332543930 3283692379 5611866046 9961843594 5540475072 6188806843 8844735470 9586728531 6893275683 1608876126 2273396516 1597856459 2538856985 1835567438 2033820329 2936508746 7382344065 1175585666 5187689250 3700397617 |
| 120259 1374617103 8663047752 0627069665 1702797372 1486459590 2848925564 2898226949 9254232158 8318120843 4392567848 3389237795 4751449308 8075967317 7433281407 0000256376 1543021456 9734973151 2711032124 7117057743 0156568850 7936936812 3116003402 6548110407 8962706886 4931959235 9337862291 7269608184 1294680836 6315456232 3290729391 2395356250 0286151931 4953792135 7150337659 7795869862 1336458175 3144482078 2914367360 0547002503 6155393660 4128108392 8482243218 2008748426 1336950262 2232224727 4889279846 2602365500 5668090855 3620568806 1002948615 4146239257 7638312583 4621912198 8595023121 |
| 18084655 2694474836 6473512181 6403599732 9294781556 6413885279 8737854773 2569852438 0762084088 6109411894 8072090150 8207905542 9632839539 4751875644 9572269349 3872868717 5345243731 1795149562 8559961608 5875440353 7401714127 4595444767 7375643396 3046027473 5318347089 |
| 581586260 7406815307 3015454527 5352462961 1725954947 6079530193 9168603218 4164480163 9567807080 1841760724 4949008768 3616949793 6836375137 9976808047 9697597803 2386427460 8331412753 7086160934 4991444782 3936744082 4887611503 6220752075 6976637337 1661526527 |
| 30945 0523526965 5732778082 0286914561 5424013480 3500647598 0404334854 9302771157 5501998533 |
| 859105992 0721567929 8086386190 6804638181 |
| 884 7783077120 0901595798 7990150791 |
| 2087116 8892790978 3186077333 |
| 6065 8856305166 6994170093 |
| 2 2668984984 0238746151 |
| 1 2300802258 4164314073 |
| 3762161994 5172911677 |
| 790229585 3564204737 |
| 732225726 9794110393 |
| 18569954 0087134681 |
| 18033522 0420114931 |
| 4151082 1006490501 |
| 44357 5779523199 |
| 13419 2876241509 |
| 10835 9961821161 |
| 8419 5812019313 |
| 950 8191179761 |
| 20 8544320217 |
| 9 7508956049 |
| 3 8662386869 |
| 1 4910357157 |
| 7125987779 |
| 5657257033 |
| 3571562821 |
| 1450083727 |
| 825986657 |
| 737385673 |
| 697595039 |
| 4381357 |
| 3083537 |
| 972091 |
| 390097 |
| 371177 |
| 234781 |
| 220333 |
| 86689 |
| 50053 |
| 30703 |
| 23917 |
| 14533 |
| 10837 |
| 9437 |
| 5419 |
| 4817 |
| 3613 |
| 2659 |
| 439 |
| 431 |
| 251 |
| 173 |
| 61 |
| 432 |
| 29 |
| 19 |
| 72 |
| 3 |
| 22 |
Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.
We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 28.022816%
Next, we find an integer witness w such that for each prime factor p of N-1, w(N-1) ≡ 1 mod N and GCD(w(N-1)/p-1,N) = 1. In this case, w = 10 suffices.
Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F4>N, N can have no more than three prime factors.
As F2 < N < F3 and N ≡ 1 (mod F), we can let N = c2·F2 + c1·F + 1.
Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c12-4·c2 is a perfect square.
Here, c12-4·c2 is ≡ 5 (mod 64) and therefore cannot be a square and this stage of the proof is passed.
We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. Here is the stdout:
realprecision = 5009 significant digits (5000 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\06DC0E1D.cin
Certificate file is: IO\06DC0E1D.chg
Found values of n, F and G.
Number to be tested has 11720 digits.
Modulus has 3285 digits.
Modulus is 28.02281611% of n.
NOTICE: This program assumes that n has passed
a BLS PRP-test with n, F, and G as given. If
not, then any results will be invalid!
Square test passed for F >> G. Using modified right endpoint.
Search for factors congruent to 1.
Running CHG with h = 8, u = 3. Right endpoint has 1868 digits.
Done! Time elapsed: 286485ms.
Running CHG with h = 8, u = 3. Right endpoint has 1819 digits.
Done! Time elapsed: 303265ms.
Running CHG with h = 8, u = 3. Right endpoint has 1754 digits.
Done! Time elapsed: 455469ms.
Running CHG with h = 8, u = 3. Right endpoint has 1666 digits.
Done! Time elapsed: 345406ms.
Running CHG with h = 8, u = 3. Right endpoint has 1574 digits.
Done! Time elapsed: 856031ms.
Running CHG with h = 7, u = 2. Right endpoint has 1482 digits.
Done! Time elapsed: 147344ms.
Running CHG with h = 7, u = 2. Right endpoint has 1425 digits.
Done! Time elapsed: 154719ms.
Running CHG with h = 7, u = 2. Right endpoint has 1339 digits.
Done! Time elapsed: 158906ms.
Running CHG with h = 7, u = 2. Right endpoint has 1236 digits.
Done! Time elapsed: 155469ms.
Running CHG with h = 7, u = 2. Right endpoint has 1081 digits.
Done! Time elapsed: 190109ms.
Running CHG with h = 5, u = 1. Right endpoint has 848 digits.
Done! Time elapsed: 45735ms.
Running CHG with h = 5, u = 1. Right endpoint has 601 digits.
Done! Time elapsed: 27578ms.
Running CHG with h = 5, u = 1. Right endpoint has 129 digits.
Done! Time elapsed: 76000ms.
A certificate has been saved to the file: IO\06DC0E1D.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\06DC0E1D.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=3.445709319 E-684 at X, ratio=3.118683193 E-812 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.501191662 at X, ratio=7.14227482 E-473 at Y, witness=13.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.973203618 E-248 at X, ratio=1.137436401 E-247 at Y, witness=5.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.1592775671 at X, ratio=7.800900340 E-466 at Y, witness=7.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.3075786261 at X, ratio=8.98932065 E-311 at Y, witness=5.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.03837295931 at X, ratio=1.848666571 E-207 at Y, witness=13.
Pol[7, 1] with [h, u]=[6, 2] has ratio=3.549611824 E-87 at X, ratio=8.25265903 E-173 at Y, witness=2.
Pol[8, 1] with [h, u]=[6, 2] has ratio=1.804148008 E-58 at X, ratio=1.652555403 E-115 at Y, witness=11.
Pol[9, 1] with [h, u]=[8, 3] has ratio=0.2526188934 at X, ratio=1.214435394 E-276 at Y, witness=3.
Pol[10, 1] with [h, u]=[8, 3] has ratio=0.2447253986 at X, ratio=1.422323490 E-276 at Y, witness=5.
Pol[11, 1] with [h, u]=[8, 3] has ratio=4.804872052 E-88 at X, ratio=3.052428965 E-262 at Y, witness=3.
Pol[12, 1] with [h, u]=[8, 3] has ratio=2.652986059 E-66 at X, ratio=9.11724977 E-197 at Y, witness=5.
Pol[13, 1] with [h, u]=[8, 3] has ratio=2.242424286 E-51 at X, ratio=1.133380718 E-147 at Y, witness=7.
Validated in 13 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.