Primality Certificate for (18371^3793-1)/18370

Andy Steward16,170 digits17 February 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.755778% factorization of N-1:

From Factorisation
1837118371
Φ22 · 2 · 3 · 1531
Φ3211 · 1599583
Φ42 · 149 · 1132529
Φ63 · 7 · 16070251
Φ82 · 41 · 89 · 617 · 25295435777
Φ1213 · 1201 · 7295328084157
Φ162 · 17 · 113 · 929 · 3634873513304362811014111409
Φ24p35
Φ48193 · 922339895623893175921 · p45
Φ79235810261 · c325
Φ158317 · c331
Φ2379630988909 · 26809190475499 · c642
Φ316820969 · 3766326275377 · 1219968537478681 · 10972475805436343246742102589673 · c601
Φ4741423 · c663
Φ6321629563053154089 · c1316
Φ948p1331
Φ126412641 · c2657
Φ18963793 · 34129 · 231514873 · p2645
Φ37921056178177 · c5313

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

21987 7166302517 5283251244 2670783070 4917408226 0483954868 4630046725 5325316275 6714391442 4708644694 5166471370 4317070975 7101012015 0831150105 3874373521 3024178225 7415933521 9939144979 3707555185 8682542840 5012868084 7927099992 1368734517 5234035410 5014187970 3872130396 4022412264 9756252891 0881400622 9727339511 3558188389 3728790868 2245739601 5869801720 5578137773 0242153717 5357467173 4491202606 7919645367 6533442535 3762885673 8839378830 6877837484 4991929509 1225715161 5688964707 3428541012 6236144798 3627725077 5126459196 0219317653 1798377716 2613723292 6923618757 1479001154 6512754808 7988646565 1108140559 4641448148 8636059014 9614696282 3897619824 0274647186 8361387838 7096135246 3490568961 3001806419 1012909189 2535157212 0774169559 6898462599 0073261891 9405354544 9157264542 0593191918 4896957697 5990587675 2310100015 7114136571 2862860357 2717676644 4072253996 9338635714 5441194762 8210498963 8760959149 5002984643 8061641713 6235040702 9405246764 0261933993 7175238159 0154163173 3510730644 4337341137 6061571211 3672218926 3454029406 9638710950 8652801450 3440074096 2932586061 3004948546 2798300252 6786950938 5566891633 7980902474 2159618793 5215891717 5078989183 0996075558 1330377965 7352573440 0504699237 1058340727 4911648371 0275182033 6743997135 6234565604 5709559391 6675234247 3375826880 6793098154 4796170428 5751591190 4760277354 5423977360 3048677007 4005028783 5440949836 0752914831 6895836082 8857244898 3937509756 1474933849 2980270770 3507523043 1848099921 5310840157 6384621320 4344861614 2911051892 8058046908 7807904145 0595676150 8396973388 4853422360 5965525599 5490904831 2954642757 0330021930 8372337175 5129110541 2692924613 5307085479 3226595115 5824168646 2209981791 1536087653 7376445703 7933824682 4163092287 1639449128 1410133563 5885856316 6377701416 3288360312 8697665194 3525823379 1437824813 1565439635 2528349980 1674959357 4817782209 3313605917 3823317547 2374886428 8133382689 9187074642 1417462458 5415940869 2919444356 9322575191 5234792880 7105963860 2638946994 0250384470 6356416741 3992410627 3014774409 5517420464 6425039903 3154910805 7164519160 3259771724 1267067013 6577007287 3629994593 9498875300 7656479695 2258351386 5908315772 8287614307 6784426212 5824246407 7264176330 1579362702 9959942685 8586902099 6987344062 6436650513 2672784082 4765351956 2378072017 7375746339 7486850386 4334362699 7468700158 8301506046 5661671773 0067611924 2107413738 2879421084 2243787939 1738393520 1935114807 6759815071 6602738836 7730157427 3249914240 1477732862 2551068976 3519867051 1256573064 5062464957 1184573016 2033349213 4298817905 4527673956 6851825904 2966832607 7925698394 0691127606 2383756217 7719099702 8278020571 9683475838 7093073216 1409420571 7342702174 2253032948 7239826137 2984167027 1165335691 1358443383 4626862384 9718183828 5711682587 5900823940 6080627162 7319181640 8303797575 0266677352 1747918156 8193594761
2 5670404854 5589933767 7387538810 6586651677 0479763869 2917782706 7643874789 8613089766 6515495320 8258036900 2614430819 2100586822 8117602854 1917502232 8067376483 0957197951 2226821544 8442772944 4103750395 9116327783 2200516723 3260068981 3126894294 3591936453 4807417324 0001789995 9582522045 9268169312 0260882211 2661242153 6591135672 3107588705 2901312861 6410363013 8232202572 3236344111 9884721313 7329222387 1109917950 8468703579 2698654090 8724582820 2093521828 2058531133 1407634088 3051695974 2878556414 3604972744 0322366654 0553791950 8623234371 5962696686 7135332687 5537037860 2561542991 6475115602 5177428885 3471864640 1047692095 7806046553 4006284893 6815879089 2110401700 4059560052 1851597778 8626369428 3149430079 1156132578 7734378461 9645308980 1868448501 0454146459 2527207709 7420003459 8055098966 3514258685 0747087615 1113365455 8030359062 9013838712 0173611172 3054027858 3675729638 7395017036 5756793633 7969742801 1641406745 8879354186 6306948345 3576131143 5772064875 8819455400 4390727675 8354891969 6386075327 1668825894 2918544540 6897261382 6225474364 1852720604 9171664865 5402941237 6379921683 3627946654 9874870260 6537684942 7359084701 9717438434 2471063853 7642234326 2671198359 2662989945 5917049850 2189764274 4776623384 2088568394 5612220932 2182943498 2913877364 6780103271 2118548955 8793652273 4381785152 2240320168 0149964571 6099434767 9532470733 3016298960 6211447551 0781200305 7349723410 1686544671 4161820721
94553 2478788989 4798935463 6489285353 0161172337
12973 6559714091 7110970020 6979571281
10 9724758054 3634324674 2102589673
36348735 1330436281 1014111409
9 2233989562 3893175921
162956 3053154089
121996 8537478681
2680 9190475499
729 5328084157
376 6326275377
2 5295435777
9630988909
1056178177
235810261
231514873
16070251
1599583
1132529
820969
34129
18371
12641
3793
1531
1423
1201
929
617
317
211
193
149
113
89
41
17
13
7
32
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) = 26.755778%

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 = 95 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 ≡ 29 (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:

realprecision = 6502 significant digits (6500 digits displayed)

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

Input file is:  IO\47C30ED1.cin
Certificate file is:  IO\47C30ED1.chg
Found values of n, F and G.
    Number to be tested has 16170 digits.
    Modulus has 4327 digits.
Modulus is 26.75577760% 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 = 14, u = 6. Right endpoint has 3191 digits.
        Done!  Time elapsed:  10148797ms.
    Running CHG with h = 15, u = 6. Right endpoint has 3172 digits.
        Done!  Time elapsed:  9631735ms.
    Running CHG with h = 15, u = 6. Right endpoint has 3148 digits.
        Done!  Time elapsed:  36840078ms.
    Running CHG with h = 15, u = 6. Right endpoint has 3119 digits.
        Done!  Time elapsed:  41154031ms.
    Running CHG with h = 15, u = 6. Right endpoint has 3085 digits.
        Done!  Time elapsed:  17086516ms.
    Running CHG with h = 15, u = 6. Right endpoint has 3046 digits.
        Done!  Time elapsed:  21428000ms.
    Running CHG with h = 14, u = 6. Right endpoint has 3000 digits.
        Done!  Time elapsed:  22695640ms.
    Running CHG with h = 14, u = 6. Right endpoint has 2966 digits.
        Done!  Time elapsed:  47340703ms.
    Running CHG with h = 14, u = 6. Right endpoint has 2930 digits.
        Done!  Time elapsed:  36644813ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2890 digits.
        Done!  Time elapsed:  2670906ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2873 digits.
        Done!  Time elapsed:  3533297ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2853 digits.
        Done!  Time elapsed:  4431953ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2829 digits.
        Done!  Time elapsed:  8149953ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2800 digits.
        Done!  Time elapsed:  6273156ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2765 digits.
        Done!  Time elapsed:  6822969ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2723 digits.
        Done!  Time elapsed:  7464406ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2673 digits.
        Done!  Time elapsed:  5218719ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2613 digits.
        Done!  Time elapsed:  2756281ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2541 digits.
        Done!  Time elapsed:  4174657ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2524 digits.
        Done!  Time elapsed:  4506375ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2504 digits.
        Done!  Time elapsed:  5250500ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2479 digits.
        Done!  Time elapsed:  5201843ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2447 digits.
        Done!  Time elapsed:  5356766ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2407 digits.
        Done!  Time elapsed:  5644422ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2358 digits.
        Done!  Time elapsed:  6527781ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2296 digits.
        Done!  Time elapsed:  6719610ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2218 digits.
        Done!  Time elapsed:  3486109ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2121 digits.
        Done!  Time elapsed:  694078ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2096 digits.
        Done!  Time elapsed:  720219ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2061 digits.
        Done!  Time elapsed:  773156ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2015 digits.
        Done!  Time elapsed:  882703ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1953 digits.
        Done!  Time elapsed:  1012531ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1872 digits.
        Done!  Time elapsed:  1176516ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1762 digits.
        Done!  Time elapsed:  1277469ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1600 digits.
        Done!  Time elapsed:  141937ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1539 digits.
        Done!  Time elapsed:  145532ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1447 digits.
        Done!  Time elapsed:  151843ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1309 digits.
        Done!  Time elapsed:  160172ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1101 digits.
        Done!  Time elapsed:  155688ms.
    Running CHG with h = 5, u = 1. Right endpoint has 751 digits.
        Done!  Time elapsed:  20812ms.
    Running CHG with h = 5, u = 1. Right endpoint has 373 digits.
        Done!  Time elapsed:  34703ms.
A certificate has been saved to the file:  IO\47C30ED1.chg

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

Testing a PRP called "IO\47C30ED1.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.508308765 E-349 at X, ratio=9.81836934 E-721 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.841750371 at X, ratio=4.840666252 E-379 at Y, witness=2.
Pol[3, 1] with [h, u]=[7, 2] has ratio=6.67942218 E-225 at X, ratio=1.453239645 E-701 at Y, witness=11.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.2591473823 at X, ratio=5.029439232 E-415 at Y, witness=5.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.2125699592 at X, ratio=5.98621221 E-277 at Y, witness=2.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.05699768870 at X, ratio=6.95643458 E-185 at Y, witness=2.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.02854057084 at X, ratio=1.602916170 E-123 at Y, witness=13.
Pol[8, 1] with [h, u]=[9, 3] has ratio=1.427237187 E-163 at X, ratio=2.779975489 E-487 at Y, witness=7.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.4282094721 at X, ratio=2.076121537 E-328 at Y, witness=2.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.706868980 at X, ratio=1.736327886 E-246 at Y, witness=5.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.1457902645 at X, ratio=4.333569662 E-185 at Y, witness=5.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.3257930300 at X, ratio=6.189221714 E-139 at Y, witness=3.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.00952040140 at X, ratio=2.323080592 E-104 at Y, witness=5.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.0916418319 at X, ratio=1.656243393 E-78 at Y, witness=5.
Pol[15, 1] with [h, u]=[11, 4] has ratio=0.004712676832 at X, ratio=5.382285506 E-388 at Y, witness=2.
Pol[16, 1] with [h, u]=[11, 4] has ratio=0.1870309152 at X, ratio=1.516156108 E-310 at Y, witness=2.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.2063414559 at X, ratio=1.399047631 E-248 at Y, witness=3.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.528917665 at X, ratio=5.574574510 E-199 at Y, witness=3.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.01431560030 at X, ratio=2.225035150 E-159 at Y, witness=37.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.1666261932 at X, ratio=1.250525215 E-127 at Y, witness=2.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.4955428858 at X, ratio=2.595613796 E-102 at Y, witness=3.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.539588766 at X, ratio=5.86949623 E-82 at Y, witness=5.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.4179002001 at X, ratio=1.108489718 E-65 at Y, witness=2.
Pol[24, 1] with [h, u]=[13, 5] has ratio=0.04882611536 at X, ratio=4.871550534 E-362 at Y, witness=2.
Pol[25, 1] with [h, u]=[13, 5] has ratio=0.05309371358 at X, ratio=8.21599204 E-302 at Y, witness=13.
Pol[26, 1] with [h, u]=[13, 5] has ratio=0.2102435069 at X, ratio=1.214881276 E-251 at Y, witness=5.
Pol[27, 1] with [h, u]=[13, 5] has ratio=0.1642882580 at X, ratio=7.21341042 E-210 at Y, witness=5.
Pol[28, 1] with [h, u]=[13, 5] has ratio=0.4720642362 at X, ratio=5.41218396 E-175 at Y, witness=2.
Pol[29, 1] with [h, u]=[13, 5] has ratio=0.3655230832 at X, ratio=5.444181912 E-146 at Y, witness=7.
Pol[30, 1] with [h, u]=[13, 5] has ratio=0.510038364 at X, ratio=1.007421496 E-121 at Y, witness=2.
Pol[31, 1] with [h, u]=[13, 5] has ratio=0.004088679165 at X, ratio=1.505865478 E-101 at Y, witness=2.
Pol[32, 1] with [h, u]=[13, 5] has ratio=0.507437204 at X, ratio=9.91005681 E-85 at Y, witness=2.
Pol[33, 1] with [h, u]=[14, 6] has ratio=0.517116137 at X, ratio=8.36181825 E-239 at Y, witness=19.
Pol[34, 1] with [h, u]=[14, 6] has ratio=0.05106092158 at X, ratio=1.501689208 E-220 at Y, witness=29.
Pol[35, 1] with [h, u]=[14, 6] has ratio=0.01637065279 at X, ratio=1.386240685 E-203 at Y, witness=3.
Pol[36, 1] with [h, u]=[15, 6] has ratio=0.01549206812 at X, ratio=6.16814851 E-275 at Y, witness=19.
Pol[37, 1] with [h, u]=[15, 6] has ratio=0.3130810564 at X, ratio=7.90286685 E-236 at Y, witness=2.
Pol[38, 1] with [h, u]=[15, 6] has ratio=0.1439495450 at X, ratio=3.130504716 E-202 at Y, witness=5.
Pol[39, 1] with [h, u]=[15, 6] has ratio=0.1873114650 at X, ratio=1.752350528 E-173 at Y, witness=19.
Pol[40, 1] with [h, u]=[15, 6] has ratio=0.3960422494 at X, ratio=7.700744584 E-149 at Y, witness=3.
Pol[41, 1] with [h, u]=[14, 6] has ratio=2.093965252 E-20 at X, ratio=3.113580364 E-116 at Y, witness=7.

Validated in 32 sec.


Congratulations! n is prime!

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