Primality Certificate for (5984^3061-1)/5983 | ||
| Andy Steward | 11,558 digits | 23 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 29.236369% factorization of N-1:
| From | Factorisation |
|---|---|
| 5984 | 2 · 2 · 2 · 2 · 2 · 11 · 17 |
| Φ2 | 3 · 3 · 5 · 7 · 19 |
| Φ3 | 35814241 |
| Φ4 | 35808257 |
| Φ5 | 131 · 25741 · 380313911 |
| Φ6 | 3 · 13 · 37 · 43 · 577 |
| Φ9 | 613 · 74901244666959191917 |
| Φ10 | 5 · 600371 · 427074911 |
| Φ12 | 1282231161953281 |
| Φ15 | 104512591 · 1252238341 · 12560429360131 |
| Φ17 | 443 · 9407053 · 229955261 · 2556956115149 · p31 |
| Φ18 | 3 · 73 · 209655082102362700627 |
| Φ20 | 41 · 1173541 · 1742021 · 125029141 · 156886621 |
| Φ30 | 310894062121 · 5289234491753618041 |
| Φ34 | 103 · 4217 · p55 |
| Φ36 | 1046449 · 5745447289 · 239331232258093 · 1465067820745117 |
| Φ45 | 4861 · 235517807152081 · p73 |
| Φ51 | 33049 · 550189 · 595394809 · 26271886397812543179247 · 70717903990185189826828398531515162017 · p42 |
| Φ60 | 61 · 146701 · 562201 · 22952330701 · 36246825804546361 · 645823841325529131901 |
| Φ68 | 137 · 1635401 · 2112826301 · 55394683544506310116289885785201 · p72 |
| Φ85 | 78031 · 212161 · p232 |
| Φ90 | 181 · 2341 · 9654631111 · 664989301261 · 29480112847744694684351281 · p38 |
| Φ102 | p121 |
| Φ153 | 188201017 · 8077063295647639 · p339 |
| Φ170 | 30091 · 52259058727291321 · p221 |
| Φ180 | 541 · 11701 · 12241 · 20161 · 3095821 · 10584001 · c153 |
| Φ204 | 125053 · c237 |
| Φ255 | 6121 · 109141 · 23738463444587166841 · c456 |
| Φ306 | 307 · 1011331 · p355 |
| Φ340 | 1021 · 8501 · 14019983641 · c467 |
| Φ510 | 7559221 · 16493189924178157937941 · c455 |
| Φ612 | 949213 · 101571388817268529 · 259902361937281427491902553 · c676 |
| Φ765 | 7900187574099925356661 · 3353837079042037790347403431 · c1401 |
| Φ1020 | 22441 · 608941 · 1056176793398950908977161 · 9579824692949631113912968921 · p905 |
| Φ1530 | 1531 · c1448 |
| Φ3060 | 3061 · 59614921 · c2890 |
We need the product F of all the prime factors from this partial factorization:
| 58767 0792646417 4660179348 8302767174 8838904939 5086913481 2752942287 5852274671 8871669612 0127839011 9283027355 4686615007 7198740720 4219615599 4621555306 3275132812 2922875066 9975902828 1744792335 5239601984 7211683058 9483750669 1514602742 9700123803 2259714923 2792665601 9123408926 6554574825 6855221743 8081302554 8050828531 0191695538 1958281137 6942091621 2382395415 2096683944 7395567211 3387346228 0330498004 2712145645 5842818762 2387843995 3169377606 1423721226 0475454543 2961009824 8673701341 9466409392 1231859921 2366269617 1826716779 6959160248 2598897374 8584692990 6659984083 3713085028 7260804099 8525783524 0629578642 6656465468 3119295028 2531145398 7586598422 8578828162 5048879332 9441929830 7735417079 0699174902 6912849469 8506111453 1277933048 4509595565 6276603690 2322655456 9761794070 8423193957 0463973332 8899076798 5958412562 9891400926 9224946013 8327670082 4393148484 5942525591 6397479165 7421198975 7402631018 1097360185 9507177212 6449820317 4854027261 |
| 12564 9409233191 2694833776 1711717024 5470951938 1473455443 4195727748 4931759187 0308233890 9592194744 8966268236 5214123175 0138088189 1887628685 4383770441 6427897189 0130626699 8185788146 1006900052 4565784709 0904988897 0800438126 1565047041 2899434016 0306221693 7042488967 5311455608 5035033728 3852776086 5917042859 9623031600 9517061824 3972416012 9183535989 1988739330 4714044713 |
| 256635477 8725630886 5599296699 6899830994 5211717111 0283694943 4223218092 2075038976 7196178559 8769805501 4172843057 0077912098 2488795869 6515713819 4031563607 2285376827 1990936129 8119611055 3854370559 3399118515 4358897806 3009571541 8477232181 0316441211 6941578025 5012128702 1465072369 3564361415 2330894753 0699930805 6089484903 3944867046 1396354903 1650454367 |
| 32 2445353049 8621705000 6270369469 4412362693 9769640893 8288180546 6001150737 1791878438 0693350190 7335524007 7273691863 0498669562 8038885920 2407509574 9570399352 9024377499 2723808778 0743788749 2656075201 3072686034 4363043735 6980418553 7472269391 |
| 3 3957506845 8183726619 7334749706 8103692013 8444902302 1904985945 7790942400 1728497636 3757882805 8042426791 2543964671 8555811437 3103453958 9495016067 1439841339 2363704495 2386547316 9125030048 8559907587 3721948420 6525791064 6153642971 |
| 7 3080798730 0231300113 4678161307 5093092384 7525260513 3574993026 9556304114 3209786971 7674929218 5737329336 7590227993 8248447841 |
| 388 1938639943 0456153989 9880864848 5010378936 3069094534 9959440118 5511881541 |
| 27 8646759611 6919066672 7796935281 7947431599 3005926351 3577054164 0937059093 |
| 62223 1455494604 7475751741 9991899413 9612867909 6893938607 |
| 36 3213703583 8783518424 0098342507 1146232891 |
| 70717903 9901851898 2682839853 1515162017 |
| 55416432 4201928545 2213786269 8472139211 |
| 55 3946835445 0631011628 9885785201 |
| 1 1033517757 8390703968 3145327991 |
| 95798246 9294963111 3912968921 |
| 33538370 7904203779 0347403431 |
| 2599023 6193728142 7491902553 |
| 294801 1284774469 4684351281 |
| 10561 7679339895 0908977161 |
| 262 7188639781 2543179247 |
| 164 9318992417 8157937941 |
| 79 0018757409 9925356661 |
| 6 4582384132 5529131901 |
| 2 0965508210 2362700627 |
| 7490124466 6959191917 |
| 2373846344 4587166841 |
| 528923449 1753618041 |
| 10157138 8817268529 |
| 5225905 8727291321 |
| 3624682 5804546361 |
| 807706 3295647639 |
| 146506 7820745117 |
| 128223 1161953281 |
| 23933 1232258093 |
| 23551 7807152081 |
| 1256 0429360131 |
| 255 6956115149 |
| 66 4989301261 |
| 31 0894062121 |
| 2 2952330701 |
| 1 4019983641 |
| 9654631111 |
| 5745447289 |
| 2112826301 |
| 1252238341 |
| 595394809 |
| 427074911 |
| 380313911 |
| 229955261 |
| 188201017 |
| 156886621 |
| 125029141 |
| 104512591 |
| 59614921 |
| 35814241 |
| 35808257 |
| 10584001 |
| 9407053 |
| 7559221 |
| 3095821 |
| 1742021 |
| 1635401 |
| 1173541 |
| 1046449 |
| 1011331 |
| 949213 |
| 608941 |
| 600371 |
| 562201 |
| 550189 |
| 212161 |
| 146701 |
| 125053 |
| 109141 |
| 78031 |
| 33049 |
| 30091 |
| 25741 |
| 22441 |
| 20161 |
| 12241 |
| 11701 |
| 8501 |
| 6121 |
| 4861 |
| 4217 |
| 3061 |
| 2341 |
| 1531 |
| 1021 |
| 613 |
| 577 |
| 541 |
| 443 |
| 307 |
| 181 |
| 137 |
| 131 |
| 103 |
| 73 |
| 61 |
| 43 |
| 41 |
| 37 |
| 19 |
| 17 |
| 13 |
| 11 |
| 7 |
| 52 |
| 34 |
| 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) = 29.236369%
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 = 667 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 ≡ 26 (mod 63) 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\17600BF5.cin
Certificate file is: IO\17600BF5.chg
Found values of n, F and G.
Number to be tested has 11558 digits.
Modulus has 3380 digits.
Modulus is 29.23636890% 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 = 6, u = 2. Right endpoint has 1421 digits.
Done! Time elapsed: 119344ms.
Running CHG with h = 6, u = 2. Right endpoint has 1260 digits.
Done! Time elapsed: 121406ms.
Running CHG with h = 5, u = 1. Right endpoint has 1019 digits.
Done! Time elapsed: 8938ms.
Running CHG with h = 5, u = 1. Right endpoint has 910 digits.
Done! Time elapsed: 8172ms.
Running CHG with h = 5, u = 1. Right endpoint has 694 digits.
Done! Time elapsed: 55343ms.
Running CHG with h = 5, u = 1. Right endpoint has 261 digits.
Done! Time elapsed: 36844ms.
A certificate has been saved to the file: IO\17600BF5.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\17600BF5.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=1.118381429 E-548 at X, ratio=4.76219432 E-808 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=2.268928257 E-434 at X, ratio=7.16294178 E-434 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.268593007 E-217 at X, ratio=3.525879166 E-217 at Y, witness=3.
Pol[4, 1] with [h, u]=[4, 1] has ratio=4.007574268 E-109 at X, ratio=4.352033570 E-109 at Y, witness=11.
Pol[5, 1] with [h, u]=[6, 2] has ratio=2.115850570 E-79 at X, ratio=4.312532578 E-484 at Y, witness=7.
Pol[6, 1] with [h, u]=[6, 2] has ratio=2.588777981 E-162 at X, ratio=5.053684538 E-323 at Y, witness=2.
Validated in 2 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.