Primality Certificate for (6869^2381-1)/6868 | ||
| Andy Steward | 9,132 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.212563% factorization of N-1:
| From | Factorisation |
|---|---|
| 6869 | 6869 |
| Φ2 | 2 · 3 · 5 · 229 |
| Φ4 | 2 · 13 · 1814737 |
| Φ5 | 11 · 191 · 1059769076761 |
| Φ7 | 29 · 8946584417 · 404919848887 |
| Φ10 | 5 · 6121 · 72730816141 |
| Φ14 | 43 · 5279 · 310919099 · 1488093979 |
| Φ17 | 17 · 307 · 5247906263519747 · 11507560882266378373 · 77947617364311331524469 |
| Φ20 | 61 · 81249049079505757119277173061 |
| Φ28 | 1582589 · 949134733 · 1100746688609 · 6673271440379399857 |
| Φ34 | 13567 · 3124193 · p51 |
| Φ35 | 307895736082226228076538301 · p66 |
| Φ68 | 137 · 2344777 · 49969905863557 · 34485465427910054953 · p82 |
| Φ70 | 71 · 126631 · p86 |
| Φ85 | 1021 · 6971 · 3400424491 · 5476809931 · 11319853751 · 997659030981849331755761 · c186 |
| Φ119 | 2857 · 254899 · 919737711142909 · c345 |
| Φ140 | 281 · 421 · 19784946721 · p169 |
| Φ170 | 3571 · 2184224540083474698488431 · c218 |
| Φ238 | 239 · 9521 · 698293 · 487992821 · 920479519 · 114959006751275829815779 · c316 |
| Φ340 | 1361 · 751050821 · 1462013587421 · 41401203490061 · 817232661438494204341 · 16889737502325792884081 · c411 |
| Φ476 | 2087891893306052260393 · c716 |
| Φ595 | 30941 · 298416082231 · p1458 |
| Φ1190 | 2381 · 58403231741 · 95563500971 · c1449 |
| Φ2380 | 178501 · 26844643561 · 2294379281041 · c2919 |
We need the product F of all the prime factors from this partial factorization:
| 25224173 6887415940 7470581380 5599487420 4342883352 1049313867 6794233653 5648377374 1931511228 3368553456 3630230204 3310454435 5793326757 6720763074 2382733646 6728433133 5946968065 3876304311 0413731418 2703251733 3520816031 5782048312 6063143276 5580695099 3751759481 8252393501 0931359467 1760444669 6004833565 5744224391 7320346760 6113884193 2227851393 0043145819 9303279050 7481130490 8772907105 4061661822 3179800931 4429632805 4874299071 2666439212 8441242766 1969703956 9234719942 4080479726 9615561576 0895399540 8389263648 9595530638 2070671334 1932786402 6809848483 4414356369 1855477399 0491830997 1765018616 4909466338 7741177834 1203084071 6943941738 4216507778 8246882111 8699305900 4875519282 2923529771 1043918173 8013676585 5379091503 6402530359 4027740781 4449144976 4524467275 8683428361 8753739887 3841416167 4867324780 1977434718 2639344237 5631201529 6848492327 3653959186 2865454846 9726682109 0214199980 9372701148 3650803717 6212530200 0715704196 2207874479 0284595947 0497807598 3244438719 2762596185 4748576727 5635970900 6196666223 1010827805 3608654725 7224959834 7056110839 6742742284 7883946043 6437871752 2171011909 0232730442 0761541748 5795883364 8183897710 3776054829 0563674127 7799127780 3794032880 7717439586 3305052953 5570250241 2285276467 6478915926 3501859921 8113040549 1146189803 4042057110 6576249678 4580755658 5608840988 7912240966 9525920588 7602581054 1720319383 9303701184 1447299939 4120964027 2808489384 9246731787 4326040815 5906975797 7740913137 8159857343 9385292165 6917422500 7179159008 7612650521 9045622998 2902010925 0309723331 9646509491 |
| 633235850 6106711847 6492158587 0925525458 1335685160 8746596422 3045290857 0796572651 0857505890 5654748405 0520843298 0293939895 4121715724 1847793616 0352663613 8523766336 8682798901 |
| 135428 2381328426 9115887629 3992067554 8820836568 6879092080 8680131605 7616312596 9652071361 |
| 10 8999819608 4978321074 2961292036 1397620100 0889130351 8558725199 6901490312 7480678389 |
| 395346 1269680596 5499488860 1327042110 3807761600 6699726011 2385068261 |
| 5 7944385475 4846707209 5286197164 1187263227 1020052287 |
| 812490490 7950575711 9277173061 |
| 3078957 3608222622 8076538301 |
| 21842 2454008347 4698488431 |
| 9976 5903098184 9331755761 |
| 1149 5900675127 5829815779 |
| 779 4761736431 1331524469 |
| 168 8973750232 5792884081 |
| 20 8789189330 6052260393 |
| 8 1723266143 8494204341 |
| 3448546542 7910054953 |
| 1150756088 2266378373 |
| 667327144 0379399857 |
| 524790 6263519747 |
| 91973 7711142909 |
| 4996 9905863557 |
| 4140 1203490061 |
| 229 4379281041 |
| 146 2013587421 |
| 110 0746688609 |
| 105 9769076761 |
| 40 4919848887 |
| 29 8416082231 |
| 9 5563500971 |
| 7 2730816141 |
| 5 8403231741 |
| 2 6844643561 |
| 1 9784946721 |
| 1 1319853751 |
| 8946584417 |
| 5476809931 |
| 3400424491 |
| 1488093979 |
| 949134733 |
| 920479519 |
| 751050821 |
| 487992821 |
| 310919099 |
| 3124193 |
| 2344777 |
| 1814737 |
| 1582589 |
| 698293 |
| 254899 |
| 178501 |
| 126631 |
| 30941 |
| 13567 |
| 9521 |
| 6971 |
| 6869 |
| 6121 |
| 5279 |
| 3571 |
| 2857 |
| 2381 |
| 1361 |
| 1021 |
| 421 |
| 307 |
| 281 |
| 239 |
| 229 |
| 191 |
| 137 |
| 71 |
| 61 |
| 43 |
| 29 |
| 17 |
| 13 |
| 11 |
| 52 |
| 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.212563%
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 = 14 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 ≡ 45 (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\1AD5094D.cin
Certificate file is: IO\1AD5094D.chg
Found values of n, F and G.
Number to be tested has 9132 digits.
Modulus has 2577 digits.
Modulus is 28.21256254% 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 1404 digits.
Done! Time elapsed: 273704ms.
Running CHG with h = 8, u = 3. Right endpoint has 1336 digits.
Done! Time elapsed: 444859ms.
Running CHG with h = 8, u = 3. Right endpoint has 1246 digits.
Done! Time elapsed: 103781ms.
Running CHG with h = 7, u = 2. Right endpoint has 1156 digits.
Done! Time elapsed: 77797ms.
Running CHG with h = 7, u = 2. Right endpoint has 1102 digits.
Done! Time elapsed: 80078ms.
Running CHG with h = 6, u = 2. Right endpoint has 1020 digits.
Done! Time elapsed: 77641ms.
Running CHG with h = 6, u = 2. Right endpoint has 925 digits.
Done! Time elapsed: 68422ms.
Running CHG with h = 6, u = 2. Right endpoint has 831 digits.
Done! Time elapsed: 75109ms.
Running CHG with h = 5, u = 1. Right endpoint has 737 digits.
Done! Time elapsed: 29859ms.
Running CHG with h = 5, u = 1. Right endpoint has 614 digits.
Done! Time elapsed: 29172ms.
Running CHG with h = 5, u = 1. Right endpoint has 370 digits.
Done! Time elapsed: 16907ms.
A certificate has been saved to the file: IO\1AD5094D.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\1AD5094D.cin".
Pol[1, 1] with [h, u]=[4, 1] has ratio=1.174076451 E-22 at X, ratio=1.288368524 E-391 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=5.38078668 E-246 at X, ratio=2.625644828 E-245 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=2.976451463 E-123 at X, ratio=4.629040676 E-123 at Y, witness=11.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.619439655 at X, ratio=1.581469961 E-189 at Y, witness=2.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.1203247713 at X, ratio=3.934673799 E-189 at Y, witness=17.
Pol[6, 1] with [h, u]=[6, 2] has ratio=0.679026213 at X, ratio=2.679538572 E-189 at Y, witness=2.
Pol[7, 1] with [h, u]=[6, 2] has ratio=1.338983546 E-83 at X, ratio=1.444773735 E-164 at Y, witness=5.
Pol[8, 1] with [h, u]=[6, 2] has ratio=7.048035402 E-56 at X, ratio=6.24584917 E-110 at Y, witness=3.
Pol[9, 1] with [h, u]=[8, 3] has ratio=0.0917967847 at X, ratio=3.933510063 E-270 at Y, witness=3.
Pol[10, 1] with [h, u]=[8, 3] has ratio=0.4042950111 at X, ratio=3.688086140 E-270 at Y, witness=2.
Pol[11, 1] with [h, u]=[8, 3] has ratio=4.258710834 E-69 at X, ratio=3.084736851 E-204 at Y, witness=5.
Validated in 6 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.