Primality Certificate for (896^3361-1)/895 | ||
| Andy Steward | 9,920 digits | 31 July 2009 |
|---|---|---|
| Originally by A.A.D.Steward 2009 | ||
| A066180 #474 | ||
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 27.180352% factorization of N-1:
| From | Factorisation |
|---|---|
| 896 | 2 · 2 · 2 · 2 · 2 · 2 · 2 · 7 |
| Φ2 | 3 · 13 · 23 |
| Φ3 | 43 · 18691 |
| Φ4 | 281 · 2857 |
| Φ5 | 5 · 11 · 1951 · 6013081 |
| Φ6 | 3 · 267307 |
| Φ7 | 379 · 1366764916467763 |
| Φ8 | 761 · 5441 · 155657 |
| Φ10 | 273181 · 2356661 |
| Φ12 | 37 · 37 · 457 · 709 · 1453 |
| Φ14 | 3361 · 153778320040801 |
| Φ15 | 31 · 61 · 3181 · 68980113655858711 |
| Φ16 | 17 · 24435158245143588434161 |
| Φ20 | 641 · 4882721 · 132722207821921 |
| Φ21 | 673 · 77651910644953 · 5117335982756084809 |
| Φ24 | 313 · 601 · 2208234891617253937 |
| Φ28 | 29 · 113 · 1877 · 4789 · 449566153 · 20216986326784997 |
| Φ30 | 991 · 2671 · 71761 · 2189336338561 |
| Φ32 | 193 · p45 |
| Φ35 | 7561 · 17921 · p63 |
| Φ40 | 41 · 61757881 · 1899431023185567041 · 35878013135938797601 |
| Φ42 | 9417507963572017 · 28460632835902719313 |
| Φ48 | 1727135957650462081 · 99908313663496233055703460481 |
| Φ56 | 795466842196490408929489 · p47 |
| Φ60 | 84906061 · 1965734931171001 · 1033867889695201871366701 |
| Φ70 | 71 · 35786521 · p62 |
| Φ80 | 128321 · 2136081862167603295543090874081 · p60 |
| Φ84 | 4699801 · 8820421 · 17603713 · 179275069 · 281587153 · 31789265129161 · 61207759964175273121 |
| Φ96 | 97 · 1249 · 4513 · 24266287393 · 163724613728903643414617457659955073 · p41 |
| Φ105 | 211 · 1051 · 4661161 · 1240562539441 · p118 |
| Φ112 | 20161 · 62273 · p133 |
| Φ120 | 275914321 · 439105103761 · 17993736588241 · 692326025557081 · 108188409479895933104041 · 182347926514796190491281 |
| Φ140 | 9661 · 33181 · 723661 · 1356369281 · 1317285462698804341 · 10955544224513259265438601 · 17050440684908907294587862721 · p47 |
| Φ160 | 5281 · c186 |
| Φ168 | 337 · 1009 · 10753 · 25563692472401401034822113 · p107 |
| Φ210 | 141961 · 9878130621241 · 453121465473728679601 · 95658739844342145858876051361 · p74 |
| Φ224 | 449 · 15233 · 13900097 · c270 |
| Φ240 | 241 · 2161 · 8792241841 · p174 |
| Φ280 | 2567041 · 11841761 · 971339041 · 2127320711962807479035681 · c237 |
| Φ336 | 189363151444152599200897 · p261 |
| Φ420 | 421 · 75918361 · 2240900341 · 283652158298845561 · 6597297921940484167081 · 2568030738201986193904938285462196179427036449228080320655447618498133135033635962135747081 · p134 |
| Φ480 | 7802565924961 · c366 |
| Φ560 | c567 |
| Φ672 | 81021697 · c559 |
| Φ840 | 190064001121 · 221651216641 · c545 |
| Φ1120 | c1134 |
| Φ1680 | 3974881 · c1128 |
| Φ3360 | 19992001 · 403072249565074827575041 · c2237 |
We need the product F of all the prime factors from this partial factorization:
| 1 3940342848 1088860030 7603100615 3358007308 6954447920 3190283088 2243092137 9347708527 8891127877 7719457145 5707620125 1581326345 2911753819 6464762466 0985955751 9716070570 7504894107 1334048657 0145069090 3071608234 7491360016 0805661630 8956183502 7408814830 8346110326 9427542913 |
| 1936 1597323316 1490878409 6434990623 2521106814 1950130147 9975719556 9075575885 7056355650 4904703478 9700037650 9312929651 5656384770 3862366047 1652347930 3776313512 6595159054 2691042801 |
| 7669 4552520289 1585443061 5917227237 1121454894 7714136030 3569065851 1096870163 6615724321 5154742076 9192195452 7854114348 6868384020 4023776921 |
| 409 2348454221 4370525477 4646950642 2588910306 4588451437 1587595067 6340791634 8658418867 6947103802 3606527178 7487909294 4312436942 3426571777 |
| 40111739 7868446093 9013984582 6683980157 4636009615 6356566023 3989502763 5418696093 8647703106 0120343528 4261216802 3140580521 |
| 5496802 9228635825 0154241065 3988103573 3032515545 4664530538 4364611713 0799085011 1042821813 8922441850 5268895713 |
| 2 5680307382 0198619390 4938285462 1961794270 3644922808 0320655447 6184981331 3503363596 2135747081 |
| 8443 3914569645 4646372880 0205379129 5730635406 3916004804 0372135050 7674815921 |
| 528 4036144298 8747347919 0463593026 6875929450 1013146952 1567042361 |
| 28 2422202900 7215714919 2781908198 1014564591 7331207681 4600868751 |
| 1086277243 1596809896 5256141952 5060390707 1265999148 0397361121 |
| 9010941 0894078039 2067886105 3964167037 5600926769 |
| 6636068 7268506901 0567579406 5664914369 4321017441 |
| 89406 8606199198 5080793592 7156905515 3271377729 |
| 1 3706907808 9214817899 3410590206 3869468801 |
| 163724 6137289036 4341461745 7659955073 |
| 2 1360818621 6760329554 3090874081 |
| 999083136 6349623305 5703460481 |
| 956587398 4434214585 8876051361 |
| 170504406 8490890729 4587862721 |
| 255636 9247240140 1034822113 |
| 109555 4422451325 9265438601 |
| 21273 2071196280 7479035681 |
| 10338 6788969520 1871366701 |
| 7954 6684219649 0408929489 |
| 4030 7224956507 4827575041 |
| 1893 6315144415 2599200897 |
| 1823 4792651479 6190491281 |
| 1081 8840947989 5933104041 |
| 244 3515824514 3588434161 |
| 65 9729792194 0484167081 |
| 4 5312146547 3728679601 |
| 6120775996 4175273121 |
| 3587801313 5938797601 |
| 2846063283 5902719313 |
| 511733598 2756084809 |
| 220823489 1617253937 |
| 189943102 3185567041 |
| 172713595 7650462081 |
| 131728546 2698804341 |
| 28365215 8298845561 |
| 6898011 3655858711 |
| 2021698 6326784997 |
| 941750 7963572017 |
| 196573 4931171001 |
| 136676 4916467763 |
| 69232 6025557081 |
| 15377 8320040801 |
| 13272 2207821921 |
| 7765 1910644953 |
| 3178 9265129161 |
| 1799 3736588241 |
| 987 8130621241 |
| 780 2565924961 |
| 218 9336338561 |
| 124 0562539441 |
| 43 9105103761 |
| 22 1651216641 |
| 19 0064001121 |
| 2 4266287393 |
| 8792241841 |
| 2240900341 |
| 1356369281 |
| 971339041 |
| 449566153 |
| 281587153 |
| 275914321 |
| 179275069 |
| 84906061 |
| 81021697 |
| 75918361 |
| 61757881 |
| 35786521 |
| 19992001 |
| 17603713 |
| 13900097 |
| 11841761 |
| 8820421 |
| 6013081 |
| 4882721 |
| 4699801 |
| 4661161 |
| 3974881 |
| 2567041 |
| 2356661 |
| 723661 |
| 273181 |
| 267307 |
| 155657 |
| 141961 |
| 128321 |
| 71761 |
| 62273 |
| 33181 |
| 20161 |
| 18691 |
| 17921 |
| 15233 |
| 10753 |
| 9661 |
| 7561 |
| 5441 |
| 5281 |
| 4789 |
| 4513 |
| 3361 |
| 3181 |
| 2857 |
| 2671 |
| 2161 |
| 1951 |
| 1877 |
| 1453 |
| 1249 |
| 1051 |
| 1009 |
| 991 |
| 761 |
| 709 |
| 673 |
| 641 |
| 601 |
| 457 |
| 449 |
| 421 |
| 379 |
| 337 |
| 313 |
| 281 |
| 241 |
| 211 |
| 193 |
| 113 |
| 97 |
| 71 |
| 61 |
| 43 |
| 41 |
| 372 |
| 31 |
| 29 |
| 23 |
| 17 |
| 13 |
| 11 |
| 7 |
| 5 |
| 32 |
| 27 |
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) = 27.180352%
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 = 2491 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 ≡ 37 (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\03800D21.cin
Certificate file is: IO\03800D21.chg
Found values of n, F and G.
Number to be tested has 9920 digits.
Modulus has 2697 digits.
Modulus is 27.18035161% 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 = 12, u = 5. Right endpoint has 1832 digits.
Done! Time elapsed: 4806594ms.
Running CHG with h = 12, u = 5. Right endpoint has 1796 digits.
Done! Time elapsed: 6047719ms.
Running CHG with h = 12, u = 5. Right endpoint has 1756 digits.
Done! Time elapsed: 8819922ms.
Running CHG with h = 11, u = 4. Right endpoint has 1715 digits.
Done! Time elapsed: 1411406ms.
Running CHG with h = 11, u = 4. Right endpoint has 1701 digits.
Done! Time elapsed: 1631625ms.
Running CHG with h = 11, u = 4. Right endpoint has 1684 digits.
Done! Time elapsed: 2020781ms.
Running CHG with h = 11, u = 4. Right endpoint has 1663 digits.
Done! Time elapsed: 2337422ms.
Running CHG with h = 11, u = 4. Right endpoint has 1637 digits.
Done! Time elapsed: 2626391ms.
Running CHG with h = 11, u = 4. Right endpoint has 1605 digits.
Done! Time elapsed: 3173203ms.
Running CHG with h = 11, u = 4. Right endpoint has 1565 digits.
Done! Time elapsed: 3427500ms.
Running CHG with h = 11, u = 4. Right endpoint has 1514 digits.
Done! Time elapsed: 10532953ms.
Running CHG with h = 9, u = 3. Right endpoint has 1451 digits.
Done! Time elapsed: 269375ms.
Running CHG with h = 9, u = 3. Right endpoint has 1442 digits.
Done! Time elapsed: 262438ms.
Running CHG with h = 9, u = 3. Right endpoint has 1431 digits.
Done! Time elapsed: 255000ms.
Running CHG with h = 9, u = 3. Right endpoint has 1417 digits.
Done! Time elapsed: 243609ms.
Running CHG with h = 9, u = 3. Right endpoint has 1397 digits.
Done! Time elapsed: 225984ms.
Running CHG with h = 9, u = 3. Right endpoint has 1371 digits.
Done! Time elapsed: 204766ms.
Running CHG with h = 9, u = 3. Right endpoint has 1336 digits.
Done! Time elapsed: 186156ms.
Running CHG with h = 9, u = 3. Right endpoint has 1289 digits.
Done! Time elapsed: 175110ms.
Running CHG with h = 9, u = 3. Right endpoint has 1227 digits.
Done! Time elapsed: 964203ms.
Running CHG with h = 9, u = 3. Right endpoint has 1144 digits.
Done! Time elapsed: 1824281ms.
Running CHG with h = 7, u = 2. Right endpoint has 1034 digits.
Done! Time elapsed: 121641ms.
Running CHG with h = 7, u = 2. Right endpoint has 980 digits.
Done! Time elapsed: 61046ms.
Running CHG with h = 7, u = 2. Right endpoint has 899 digits.
Done! Time elapsed: 100625ms.
Running CHG with h = 7, u = 2. Right endpoint has 779 digits.
Done! Time elapsed: 113860ms.
Running CHG with h = 5, u = 1. Right endpoint has 597 digits.
Done! Time elapsed: 13297ms.
Running CHG with h = 5, u = 1. Right endpoint has 309 digits.
Done! Time elapsed: 19422ms.
A certificate has been saved to the file: IO\03800D21.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\03800D21.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=1.189778934 E-96 at X, ratio=2.585881335 E-404 at Y, witness=5.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.897926521 at X, ratio=6.506119486 E-289 at Y, witness=5.
Pol[3, 1] with [h, u]=[7, 2] has ratio=0.2388479018 at X, ratio=1.599944601 E-363 at Y, witness=2.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.508193615 at X, ratio=1.403229491 E-242 at Y, witness=11.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.629668775 at X, ratio=5.74882874 E-162 at Y, witness=7.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.3706401685 at X, ratio=3.147264483 E-108 at Y, witness=2.
Pol[7, 1] with [h, u]=[9, 3] has ratio=0.1112160320 at X, ratio=4.851865010 E-332 at Y, witness=2.
Pol[8, 1] with [h, u]=[9, 3] has ratio=0.1202020019 at X, ratio=2.502339934 E-249 at Y, witness=11.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.3301848011 at X, ratio=4.73714303 E-187 at Y, witness=31.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.2655938293 at X, ratio=1.616652984 E-140 at Y, witness=3.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.1865882826 at X, ratio=1.576284928 E-105 at Y, witness=2.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.1531972795 at X, ratio=2.396390742 E-79 at Y, witness=29.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.1820215638 at X, ratio=1.067142548 E-59 at Y, witness=3.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.2337635364 at X, ratio=6.18682067 E-45 at Y, witness=2.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.3385347304 at X, ratio=6.830765972 E-34 at Y, witness=2.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.1328236443 at X, ratio=1.408394974 E-25 at Y, witness=3.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.1197706346 at X, ratio=1.129679081 E-253 at Y, witness=5.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.1963359314 at X, ratio=3.821274312 E-203 at Y, witness=19.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.04674867050 at X, ratio=1.136788143 E-162 at Y, witness=19.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.3213176427 at X, ratio=2.819051020 E-130 at Y, witness=5.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.0797915312 at X, ratio=2.512174132 E-104 at Y, witness=3.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.3211836961 at X, ratio=1.317667896 E-83 at Y, witness=23.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.3467473636 at X, ratio=4.577930464 E-67 at Y, witness=2.
Pol[24, 1] with [h, u]=[10, 4] has ratio=6.49502568 E-16 at X, ratio=2.631962833 E-60 at Y, witness=17.
Pol[25, 1] with [h, u]=[12, 5] has ratio=0.2275879142 at X, ratio=8.34298029 E-204 at Y, witness=7.
Pol[26, 1] with [h, u]=[12, 5] has ratio=0.1226743011 at X, ratio=1.928393465 E-199 at Y, witness=5.
Pol[27, 1] with [h, u]=[12, 5] has ratio=1.963976465 E-37 at X, ratio=7.23666001 E-181 at Y, witness=5.
Validated in 51 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.