Primality Certificate for (8397^2389-1)/8396

Andy Steward9,371 digits03 March 2010
Originally by A.A.D.Steward 2010

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.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 26.252361% factorization of N-1:

From Factorisation
83973 · 3 · 3 · 311
Φ22 · 13 · 17 · 19
Φ37 · 7 · 79 · 18217
Φ42 · 5 · 53 · 173 · 769
Φ61543 · 45691
Φ1261 · 313 · 409 · 2281 · 279109
Φ19919020537876059 · c764
Φ3985573 · 935347418951303483840933 · p750
Φ597c1554
Φ796797 · p1552
Φ11942389 · 44179 · 15303499 · 131172770749 · 28405437741229 · 50861035769873827 · c1498
Φ23881880003916937 · c3096

We need the product F of all the prime factors from this partial factorization:

11 2643551317 1699454159 6918456648 2113208350 8883562673 9206584579 8603638097 9497101848 1656269084 3999824995 3587983521 7018383587 9315346848 5794569792 2895790157 1053402326 2647468916 0406166569 0698215577 4494122665 4274327421 6897350456 7796870079 6728762197 3463292824 1832183371 5990778410 9058889587 6937823273 1058677869 5289928896 7178460225 1624549081 9853869664 3141705658 4972404873 1004262794 3814623359 3226045964 4512452744 1846078525 9833562131 0936416379 5154020522 5048783614 0659579370 1156867399 7414237907 0358063341 4217723649 5428803656 7346832652 2692967517 7607058105 3175582325 2114379331 0587087489 9735581166 9897692484 1619118250 7217126352 3257158038 4192877420 5543802798 1677456328 8905221923 5163720495 4001156813 1338994879 6368302053 0276343284 7701518847 2785507186 7831049409 7189434546 8046406830 6429986282 6817007809 2869373469 9987941579 9155812436 9654893611 6270958253 9060193013 0025246794 7521143270 9604032201 3335179187 5170118365 4973975629 7624649404 9180588999 7156592961 3176871271 6788416351 6604510370 1559596108 3010208632 5960395425 9359374230 3514291899 5017741999 9948168761 8939706576 6759095617 6923569463 2589901714 3493854958 7796278446 6272224849 7508134901 5009333069 7165584026 8596790564 7173166046 2592393586 1908260101 8248657865 3427271790 4226286900 8792599976 2068488231 7100994777 4904588918 9346158838 0668027237 1536058490 9020616673 6583494729 6160073840 4812756910 4292634735 1018662561 0583531056 5180258435 1802412807 4753228387 5186553556 6563777572 7866826900 5533690538 4757618898 3741021166 2223586611 5748905975 2887181187 3784840638 0302090487 0885329219 0701325793 0034267000 8966671688 7177762811 6099268703 4050793037
1817475722 9613684383 8821142236 3896481526 4851110787 7584750337 8092212670 0570761866 6829488633 5580026657 1463334213 8884338790 2556274907 2614700477 6745431180 7931354558 8826185921 4798557077 6700741571 3207295332 1808495831 6518520447 7110434140 7936856781 5952703924 3368988725 1737659302 5543797997 1887572870 4793312165 2467262353 5961066107 9104605488 8043884233 0293196041 9954251301 7543228430 0088985190 8143874175 7773084081 3427534748 5826640513 8730598282 5334533734 9128252739 4447075030 1306072663 3933102553 1032519191 9834659862 6127325340 9505496240 8377386234 8650282649 7785602545 7913568177 9959107371 7489193277 3932077795 7905306391 2666715363 9090922150 5461442285 2857537775 6055444026 5083697259 0380371831 5187352063 3144894290 8424941464 5626112233 9598299936 4771069422 0237801623 0662343837
9353 4741895130 3483840933
5086103 5769873827
2840 5437741229
1902 0537876059
188 0003916937
13 1172770749
15303499
279109
45691
44179
18217
5573
2389
2281
1543
797
769
409
313
311
173
79
61
53
19
17
13
72
5
33
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) = 26.252361%

Finding a Witness to Primality

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 = 22 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.

Express N in base F

As F2 < N < F3 and N ≡ 1 (mod F), we can let N = c2·F2 + c1·F + 1.

Brillhart, Lehmer and Selfridge

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.

Coppersmith and Howgrave-Graham

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:

Welcome to the CHG primality prover!
------------------------------------

realprecision = 4007 significant digits (4000 digits displayed)
Input file is:  IO\20CD0955.cin
Certificate file is:  IO\20CD0955.chg
Found values of n, F and G.
    Number to be tested has 9371 digits.
    Modulus has 2461 digits.
Modulus is 26.25236087% 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 = 22, u = 10. Right endpoint has 1991 digits.
        Done!  Time elapsed:  32741500ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1974 digits.
        Done!  Time elapsed:  19859094ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1964 digits.
        Done!  Time elapsed:  25351250ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1953 digits.
        Done!  Time elapsed:  27650750ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1942 digits.
        Done!  Time elapsed:  160935031ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1928 digits.
        Done!  Time elapsed:  176523469ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1914 digits.
        Done!  Time elapsed:  39153484ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1898 digits.
        Done!  Time elapsed:  45467531ms.
    Running CHG with h = 21, u = 9. Right endpoint has 1880 digits.
        Done!  Time elapsed:  50883750ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1860 digits.
        Done!  Time elapsed:  24916735ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1851 digits.
        Done!  Time elapsed:  9774640ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1842 digits.
        Done!  Time elapsed:  9828688ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1832 digits.
        Done!  Time elapsed:  16230062ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1820 digits.
        Done!  Time elapsed:  12692829ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1807 digits.
        Done!  Time elapsed:  18068359ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1792 digits.
        Done!  Time elapsed:  22282922ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1776 digits.
        Done!  Time elapsed:  26307453ms.
    Running CHG with h = 19, u = 8. Right endpoint has 1757 digits.
        Done!  Time elapsed:  13285125ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1736 digits.
        Done!  Time elapsed:  10398922ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1729 digits.
        Done!  Time elapsed:  10781906ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1721 digits.
        Done!  Time elapsed:  10877438ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1711 digits.
        Done!  Time elapsed:  10851640ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1701 digits.
        Done!  Time elapsed:  10879844ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1689 digits.
        Done!  Time elapsed:  11440734ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1675 digits.
        Done!  Time elapsed:  11569422ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1659 digits.
        Done!  Time elapsed:  12059313ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1641 digits.
        Done!  Time elapsed:  12351359ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1619 digits.
        Done!  Time elapsed:  11784141ms.
    Running CHG with h = 16, u = 6. Right endpoint has 1595 digits.
        Done!  Time elapsed:  8025172ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1583 digits.
        Done!  Time elapsed:  8502265ms.
    Running CHG with h = 16, u = 6. Right endpoint has 1573 digits.
        Done!  Time elapsed:  9000563ms.
    Running CHG with h = 16, u = 6. Right endpoint has 1556 digits.
        Done!  Time elapsed:  7779390ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1534 digits.
        Done!  Time elapsed:  15984469ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1515 digits.
        Done!  Time elapsed:  2800453ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1494 digits.
        Done!  Time elapsed:  4018016ms.
    Running CHG with h = 14, u = 5. Right endpoint has 1470 digits.
        Done!  Time elapsed:  4145484ms.
    Running CHG with h = 14, u = 5. Right endpoint has 1458 digits.
        Done!  Time elapsed:  3878766ms.
    Running CHG with h = 14, u = 5. Right endpoint has 1443 digits.
        Done!  Time elapsed:  3919328ms.
    Running CHG with h = 14, u = 5. Right endpoint has 1421 digits.
        Done!  Time elapsed:  4582781ms.
    Running CHG with h = 14, u = 5. Right endpoint has 1395 digits.
        Done!  Time elapsed:  6538610ms.
    Running CHG with h = 14, u = 5. Right endpoint has 1361 digits.
        Done!  Time elapsed:  7502359ms.
    Running CHG with h = 12, u = 4. Right endpoint has 1318 digits.
        Done!  Time elapsed:  2230484ms.
    Running CHG with h = 12, u = 4. Right endpoint has 1302 digits.
        Done!  Time elapsed:  494516ms.
    Running CHG with h = 12, u = 4. Right endpoint has 1279 digits.
        Done!  Time elapsed:  269922ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1246 digits.
        Done!  Time elapsed:  2230297ms.
    Running CHG with h = 12, u = 4. Right endpoint has 1223 digits.
        Done!  Time elapsed:  2477531ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1174 digits.
        Done!  Time elapsed:  1365266ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1137 digits.
        Done!  Time elapsed:  182093ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1120 digits.
        Done!  Time elapsed:  158313ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1092 digits.
        Done!  Time elapsed:  173109ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1047 digits.
        Done!  Time elapsed:  116953ms.
    Running CHG with h = 9, u = 3. Right endpoint has 992 digits.
        Done!  Time elapsed:  152547ms.
    Running CHG with h = 8, u = 2. Right endpoint has 880 digits.
        Done!  Time elapsed:  60094ms.
    Running CHG with h = 5, u = 1. Right endpoint has 488 digits.
        Done!  Time elapsed:  6141ms.
A certificate has been saved to the file:  IO\20CD0955.chg

Running David Broadhurst's verifier on the saved certificate...

Testing a PRP called "IO\20CD0955.cin".

Pol[1, 1] with [h, u]=[4, 1] has ratio=1.523832063 E-161 at X, ratio=8.29915984 E-649 at Y, witness=3.
Pol[2, 1] with [h, u]=[7, 2] has ratio=4.555722764 E-1297 at X, ratio=2.114698322 E-785 at Y, witness=3.
Pol[3, 1] with [h, u]=[8, 3] has ratio=2.260707600 E-785 at X, ratio=5.287466120 E-337 at Y, witness=3.
Pol[4, 1] with [h, u]=[8, 3] has ratio=5.992704154 E-164 at X, ratio=6.044707344 E-164 at Y, witness=2.
Pol[5, 1] with [h, u]=[10, 3] has ratio=1.295844894 E-46 at X, ratio=1.848371955 E-137 at Y, witness=3.
Pol[6, 1] with [h, u]=[10, 3] has ratio=2.364648954 E-28 at X, ratio=9.10669267 E-83 at Y, witness=2.
Pol[7, 1] with [h, u]=[10, 3] has ratio=0.625135384 at X, ratio=3.571140222 E-53 at Y, witness=13.
Pol[8, 1] with [h, u]=[11, 4] has ratio=0.520809013 at X, ratio=3.832713996 E-148 at Y, witness=3.
Pol[9, 1] with [h, u]=[12, 4] has ratio=0.1055151052 at X, ratio=1.500867930 E-197 at Y, witness=2.
Pol[10, 1] with [h, u]=[11, 4] has ratio=0.2650297980 at X, ratio=7.620834032 E-93 at Y, witness=3.
Pol[11, 1] with [h, u]=[12, 4] has ratio=0.05928610768 at X, ratio=6.07251810 E-132 at Y, witness=2.
Pol[12, 1] with [h, u]=[12, 4] has ratio=1.408378404 E-24 at X, ratio=3.226496465 E-94 at Y, witness=7.
Pol[13, 1] with [h, u]=[12, 4] has ratio=1.486938081 E-16 at X, ratio=4.530412658 E-63 at Y, witness=3.
Pol[14, 1] with [h, u]=[14, 5] has ratio=0.05271632602 at X, ratio=8.60303392 E-219 at Y, witness=7.
Pol[15, 1] with [h, u]=[14, 5] has ratio=0.04686232712 at X, ratio=1.548428634 E-168 at Y, witness=3.
Pol[16, 1] with [h, u]=[14, 5] has ratio=0.2674896381 at X, ratio=1.703121626 E-131 at Y, witness=7.
Pol[17, 1] with [h, u]=[14, 5] has ratio=0.539519526 at X, ratio=2.550856785 E-108 at Y, witness=2.
Pol[18, 1] with [h, u]=[14, 5] has ratio=5.535424730 E-17 at X, ratio=4.436601676 E-79 at Y, witness=2.
Pol[19, 1] with [h, u]=[14, 5] has ratio=2.215476083 E-12 at X, ratio=1.114179522 E-56 at Y, witness=3.
Pol[20, 1] with [h, u]=[15, 6] has ratio=0.4006120478 at X, ratio=9.56753001 E-148 at Y, witness=2.
Pol[21, 1] with [h, u]=[15, 6] has ratio=0.1671428895 at X, ratio=9.11376278 E-127 at Y, witness=11.
Pol[22, 1] with [h, u]=[15, 6] has ratio=0.0895031602 at X, ratio=2.924873195 E-113 at Y, witness=2.
Pol[23, 1] with [h, u]=[16, 6] has ratio=0.1493773499 at X, ratio=1.066040397 E-132 at Y, witness=3.
Pol[24, 1] with [h, u]=[16, 6] has ratio=0.3933998531 at X, ratio=8.55064136 E-103 at Y, witness=5.
Pol[25, 1] with [h, u]=[15, 6] has ratio=8.99305098 E-12 at X, ratio=3.747923580 E-62 at Y, witness=11.
Pol[26, 1] with [h, u]=[16, 6] has ratio=0.2178197124 at X, ratio=5.165465864 E-70 at Y, witness=13.
Pol[27, 1] with [h, u]=[17, 7] has ratio=0.2074260525 at X, ratio=3.667496440 E-168 at Y, witness=31.
Pol[28, 1] with [h, u]=[17, 7] has ratio=0.0000000847054905 at X, ratio=7.360791894 E-155 at Y, witness=5.
Pol[29, 1] with [h, u]=[17, 7] has ratio=0.02081220246 at X, ratio=6.29108911 E-128 at Y, witness=43.
Pol[30, 1] with [h, u]=[17, 7] has ratio=0.2002402458 at X, ratio=4.915784356 E-112 at Y, witness=2.
Pol[31, 1] with [h, u]=[17, 7] has ratio=0.0870377907 at X, ratio=4.038207119 E-98 at Y, witness=3.
Pol[32, 1] with [h, u]=[17, 7] has ratio=0.01344765978 at X, ratio=5.822613918 E-86 at Y, witness=2.
Pol[33, 1] with [h, u]=[17, 7] has ratio=0.1464165279 at X, ratio=2.612613801 E-75 at Y, witness=2.
Pol[34, 1] with [h, u]=[17, 7] has ratio=0.1572391497 at X, ratio=5.02962524 E-66 at Y, witness=2.
Pol[35, 1] with [h, u]=[17, 7] has ratio=0.2391078516 at X, ratio=7.92804961 E-58 at Y, witness=2.
Pol[36, 1] with [h, u]=[17, 7] has ratio=0.2606935390 at X, ratio=1.089460964 E-50 at Y, witness=2.
Pol[37, 1] with [h, u]=[19, 8] has ratio=0.4270220141 at X, ratio=8.75242343 E-169 at Y, witness=2.
Pol[38, 1] with [h, u]=[19, 8] has ratio=0.3184354337 at X, ratio=5.23667851 E-150 at Y, witness=3.
Pol[39, 1] with [h, u]=[19, 8] has ratio=0.2771064074 at X, ratio=1.720671963 E-133 at Y, witness=5.
Pol[40, 1] with [h, u]=[19, 8] has ratio=0.0766525628 at X, ratio=9.09495006 E-119 at Y, witness=23.
Pol[41, 1] with [h, u]=[19, 8] has ratio=0.3532836050 at X, ratio=1.447082021 E-105 at Y, witness=3.
Pol[42, 1] with [h, u]=[19, 8] has ratio=0.4009536407 at X, ratio=5.92930200 E-94 at Y, witness=5.
Pol[43, 1] with [h, u]=[19, 8] has ratio=0.1978293817 at X, ratio=1.177429482 E-83 at Y, witness=5.
Pol[44, 1] with [h, u]=[19, 8] has ratio=0.002661224049 at X, ratio=1.984644189 E-74 at Y, witness=11.
Pol[45, 1] with [h, u]=[19, 8] has ratio=0.2794506900 at X, ratio=3.026810224 E-66 at Y, witness=2.
Pol[46, 1] with [h, u]=[21, 9] has ratio=0.1013489991 at X, ratio=4.460887618 E-181 at Y, witness=5.
Pol[47, 1] with [h, u]=[21, 9] has ratio=0.2502438200 at X, ratio=4.424763800 E-163 at Y, witness=13.
Pol[48, 1] with [h, u]=[21, 9] has ratio=0.0765745380 at X, ratio=7.83318141 E-147 at Y, witness=3.
Pol[49, 1] with [h, u]=[21, 9] has ratio=0.1522847986 at X, ratio=2.673759132 E-132 at Y, witness=7.
Pol[50, 1] with [h, u]=[21, 9] has ratio=0.2527912015 at X, ratio=4.942192438 E-119 at Y, witness=2.
Pol[51, 1] with [h, u]=[21, 9] has ratio=0.0722938133 at X, ratio=2.878913416 E-107 at Y, witness=3.
Pol[52, 1] with [h, u]=[21, 9] has ratio=0.1661329929 at X, ratio=1.489703081 E-96 at Y, witness=7.
Pol[53, 1] with [h, u]=[21, 9] has ratio=0.3858484567 at X, ratio=4.856979770 E-87 at Y, witness=3.
Pol[54, 1] with [h, u]=[22, 10] has ratio=0.1773882484 at X, ratio=4.778963590 E-178 at Y, witness=3.

Validated in 56 sec.


Congratulations! n is prime!

The actual input file containing N and F and the output certificate are included in this file.