Primality Certificate for (7840^2671-1)/7839 | ||
| Andy Steward | 10,398 digits | 29 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.307684% factorization of N-1:
| From | Factorisation |
|---|---|
| 7840 | 2 · 2 · 2 · 2 · 2 · 5 · 7 · 7 |
| Φ2 | 7841 |
| Φ3 | 3 · 20491147 |
| Φ5 | 521 · 14401 · 503604121 |
| Φ6 | 19 · 3234619 |
| Φ10 | 11 · 9811 · 35002809041 |
| Φ15 | 31 · 271 · 89759281 · 18926170728454282081 |
| Φ30 | 52436971 · 772342891 · 352481349299881 |
| Φ89 | 851197 · c337 |
| Φ178 | 179 · 5482223 · 2703215681555503 · c319 |
| Φ267 | 2781593719 · c676 |
| Φ445 | 2671 · 138841 · c1363 |
| Φ534 | 605023 · 101441393842807 · c666 |
| Φ890 | 18691 · c1367 |
| Φ1335 | 3375288074791 · c2730 |
| Φ2670 | 53399284995361 · 7185893369378761 · p2713 |
We need the product F of all the prime factors from this partial factorization:
| 103 3800000975 5574603498 0730562926 0292254496 5245961742 7440739203 0642997402 0438231263 3061323101 0560450860 4712337058 8440765872 4496837050 4117697385 7409246517 0580843109 6191729980 7311013230 9365180152 2819270495 6841924319 8515711263 7672685314 7219017288 6270984696 2014708876 6771629284 5268223053 9575335023 0883687327 8570192094 5580369025 0990005554 7610401972 2370944192 1472914366 8731385985 9606041675 3687137251 2979186403 9688033910 6018130468 7963351773 5547570121 4790369945 2528700398 1205539916 9002820396 1223692143 1646861536 3165574017 9395142879 2390800185 3928971788 3182263407 3888608573 8317864950 9369312966 5885279949 1670249811 7425127208 4674079778 0481435004 2174633129 4884516635 0599424570 0118102067 7309399594 5062741744 8823553672 8018580500 6551915389 8308002246 6959745995 8705528427 3751675596 8558228399 4345241114 5974500240 3502848461 2779777312 8838002480 9298409015 5185576178 3512609842 9644687327 8061593345 7842067390 9866121144 4343118609 5675344119 1019088468 3594962436 9534390516 4777912542 7342235046 2454508260 7764029798 7359728741 7649171853 5607782862 5110161353 1495706096 5748394783 0324204067 9425651834 0200509677 4478698262 1039092363 0746648293 1555118060 8087502627 3464197442 7164892914 4699782563 1823549017 8311530584 6218773022 8826943286 0608859622 3139937815 5436428468 4008733609 2646662365 2212691941 1028604370 6474688035 4422796078 8540926289 5178232018 6942268773 2084311276 2703662652 0224222991 6421911662 5287975772 3552691276 6856067192 9650747140 0773259524 4567706568 2394656471 4325143472 5975270404 1382275664 4136436456 7438672307 4417724819 2429702711 5584376196 3661643054 6897707673 9099493912 9913613954 0736846145 5294025577 0754960885 2902139136 1247807822 5132080519 6033082259 2548203287 7840041117 1023387192 4176018598 6237440965 9805644325 3069526769 9032428949 8713309492 6573461407 3600078622 0346758749 5750693279 0575373940 5658217372 9585702399 9352316639 8735565595 3489068470 6138990893 2959756145 9704816444 3206611793 3713105081 4600395285 0234659682 9879386064 5514831715 6013407965 2531846470 5157718172 8154504432 4924173357 0139727044 1449314069 4774238017 2107124661 0996848838 5066270561 1391780719 1715482596 9542884660 7766064911 1919352080 1773261223 3836367279 0454578555 6806655268 5548454230 8447171252 8246821631 3329253462 8358321613 3586240211 7580284356 6358401245 3684033424 4455591461 8469793126 2669985243 4871795489 0681898568 2866722539 0010424534 2294875809 4779090439 0768052766 5996233975 2805143270 6390424385 5957932886 4557058436 9823569089 3675533843 0061157272 1096111468 2676360482 4653940897 3665813740 8056814139 0565238654 2502608764 7120175782 6258083708 1971670298 1181508811 8556917073 0325747218 7563772489 4200331106 9670023310 7015927526 4089103651 6168693310 0969747016 7942360526 5850349267 7819201581 2004652989 5240252358 6679561344 8100479125 0512526246 9495040143 8295639427 3971068882 7874480763 2599085938 6238950922 9070637241 |
| 1892617072 8454282081 |
| 718589 3369378761 |
| 270321 5681555503 |
| 35248 1349299881 |
| 10144 1393842807 |
| 5339 9284995361 |
| 337 5288074791 |
| 3 5002809041 |
| 2781593719 |
| 772342891 |
| 503604121 |
| 89759281 |
| 52436971 |
| 20491147 |
| 5482223 |
| 3234619 |
| 851197 |
| 605023 |
| 138841 |
| 18691 |
| 14401 |
| 9811 |
| 7841 |
| 2671 |
| 521 |
| 271 |
| 179 |
| 31 |
| 19 |
| 11 |
| 72 |
| 5 |
| 3 |
| 25 |
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.307684%
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 = 221 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 ≡ 29 (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 = 4007 significant digits (4000 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\1EA00A6F.cin
Certificate file is: IO\1EA00A6F.chg
Found values of n, F and G.
Number to be tested has 10398 digits.
Modulus has 2944 digits.
Modulus is 28.30768383% 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 1568 digits.
Done! Time elapsed: 222531ms.
Running CHG with h = 8, u = 3. Right endpoint has 1474 digits.
Done! Time elapsed: 278094ms.
Running CHG with h = 7, u = 2. Right endpoint has 1362 digits.
Done! Time elapsed: 57890ms.
Running CHG with h = 7, u = 2. Right endpoint has 1316 digits.
Done! Time elapsed: 57094ms.
Running CHG with h = 6, u = 2. Right endpoint has 1248 digits.
Done! Time elapsed: 48094ms.
Running CHG with h = 6, u = 2. Right endpoint has 1145 digits.
Done! Time elapsed: 43969ms.
Running CHG with h = 6, u = 2. Right endpoint has 1027 digits.
Done! Time elapsed: 37312ms.
Running CHG with h = 6, u = 2. Right endpoint has 908 digits.
Done! Time elapsed: 30438ms.
Running CHG with h = 5, u = 1. Right endpoint has 790 digits.
Done! Time elapsed: 24218ms.
Running CHG with h = 5, u = 1. Right endpoint has 599 digits.
Done! Time elapsed: 11657ms.
Running CHG with h = 5, u = 1. Right endpoint has 216 digits.
Done! Time elapsed: 32109ms.
A certificate has been saved to the file: IO\1EA00A6F.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\1EA00A6F.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=1.402445512 E-434 at X, ratio=5.263897470 E-649 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=7.47912652 E-228 at X, ratio=1.139364387 E-383 at Y, witness=7.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.785889395 E-192 at X, ratio=4.089989391 E-192 at Y, witness=2.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.0628589806 at X, ratio=3.074426105 E-237 at Y, witness=17.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.3491653550 at X, ratio=2.213403388 E-237 at Y, witness=3.
Pol[6, 1] with [h, u]=[6, 2] has ratio=0.612989780 at X, ratio=3.233750831 E-237 at Y, witness=2.
Pol[7, 1] with [h, u]=[6, 2] has ratio=1.268925242 E-103 at X, ratio=4.531736478 E-206 at Y, witness=7.
Pol[8, 1] with [h, u]=[6, 2] has ratio=4.674961968 E-70 at X, ratio=1.582371920 E-137 at Y, witness=41.
Pol[9, 1] with [h, u]=[6, 2] has ratio=1.813705692 E-47 at X, ratio=6.32222609 E-92 at Y, witness=2.
Pol[10, 1] with [h, u]=[8, 3] has ratio=0.532640240 at X, ratio=1.363836851 E-338 at Y, witness=5.
Pol[11, 1] with [h, u]=[8, 3] has ratio=2.297375047 E-95 at X, ratio=1.541256093 E-283 at Y, witness=3.
Validated in 7 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.