Primality Certificate for (6655^4051-1)/6654

Andy Steward15,484 digits26 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.462135% factorization of N-1:

From Factorisation
66555 · 11 · 11 · 11
Φ22 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 2 · 13
Φ33 · 14765227
Φ51961812523207681
Φ67 · 6326053
Φ93 · 19 · 15823 · 15859 · 17551 · 346056499
Φ10181 · 3881 · 2791931561
Φ15145928791 · 825802981 · 31922859356251
Φ18441690859 · 196684414569289
Φ25182139271052457600225090701 · p51
Φ273 · 163 · 1459 · 1567 · 38366677 · 1382923684036831357243 · p32
Φ3031 · 50461 · 244381 · 10066181290734628711
Φ455581 · 6121 · 59581 · 11235476332557349320545902125721 · p49
Φ5012460501 · 9730936630477080430771729800581101 · p36
Φ549978027899923 · 4254053689895515567507 · p35
Φ75151 · 1671307201 · 2967341998548751 · c127
Φ813 · 487 · 1157675977 · 363599513050447 · 107325077734798309 · c163
Φ9017761771 · 1122765620590142731 · p67
Φ135271 · 756280801 · 507392058891961 · p250
Φ1501911359290687625804838112186351 · p123
Φ16286462658097891399 · c190
Φ2252223552151 · 1960595603636894101 · 3394792799834734590584485779451 · c401
Φ270644491 · 142651872384721593292624383024931 · 6571509527458181677461416343282023191 · c201
Φ405811 · 1621 · 775410417615511 · c805
Φ45010932568651 · c449
Φ675157951 · 217351 · 996301 · 113822551 · 539403703651 · 5912670550135051 · p1325
Φ8104051 · 17011 · 57494674801 · c808
Φ1350328051 · 364192333651 · 1609495760701 · 416231331958564544051551 · p1324
Φ20258101 · 49345201 · c4118
Φ4050c4129

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

17350 0616846551 2412589522 3003541311 8683780103 9212815778 5490947228 7563310539 5063050314 0306140368 7005253426 4801808986 7581937243 7490081351 8746163323 9912923655 8925512220 6503837790 3288687490 2052134764 7463678687 0931037277 6514641992 8658416584 0193982964 6846443532 8319527870 2156481998 2028712159 8082071181 4719716814 8103674036 6760627838 0021986082 2582948853 4174528036 5491018607 4545353705 1552457998 6440719426 0284411274 2464888699 9787096111 9191484796 9839377902 5894952599 9722664324 3447402555 3570098963 9385370077 5158132584 9283519976 3038449134 8169154450 0935210720 4171326163 2433131976 6181618106 7596668202 1659260201 0807054190 1585115532 7406025219 8553847350 5110608762 3149316155 6514550265 9790956716 4492603004 8643417359 2544058195 0015286396 7114650092 2217316038 6548651968 5650406467 3458082709 2486037966 6784213255 2480996375 1590676165 5184554568 4052153577 0557725269 9692868656 5136285936 0863619844 9222352859 3195759250 4568026701 4833069420 5775503722 1899247255 0320242603 9045238285 9916552648 3817287234 1163069109 3275485849 0937488558 0714934584 3923095955 3186830570 0007897618 6036934895 7482436231 5944821509 4209732016 0541709702 5178028530 6100083548 2442285285 1494265903 0990125837 6220622724 1262820786 3740039198 9253637040 0754209526 9876481570 0145315210 9941438680 6858239655 0252967916 4247560671 1260352968 2167432142 8151397518 0886883792 8694905002 0942390275 5012473526 8937274651
2691 5643069738 9276325695 6734951759 1238930793 9121908150 8020710636 9974059786 4540751885 9131085043 9837909399 6259620794 4347934195 1963807922 7522426796 1576985987 2346297712 0871891503 2676329206 2164978563 1487593400 9171982489 9456154594 2232299988 5161528619 5068605836 9391288492 3382615574 1972136987 4828186551 9642908746 0640284352 5110390539 5121338548 0414272608 7842945953 5272043536 5197524605 8757485932 0474753105 0267267573 2036680339 3228574842 6510958638 8549366692 7776922578 4970726323 3739650177 7279068868 9580276829 7638422337 3321616526 2249991485 5311014476 0267023569 6686460264 0020544490 5507355454 9851129000 5429807540 4492516325 1180742753 9818699051 5421706886 9250983620 1782434778 4964440337 2676052870 6159464358 6292367484 8166002203 1911927471 8475989352 5763309322 4862948182 0228852047 0423040273 9137267151 4872994972 8825193552 6187794975 4669845424 6972483664 9672194276 9354028245 9861370355 2392466626 7293295742 8132686600 3093558757 9448346998 3058028549 6435996469 3137431787 2571931113 0768941710 2382676381 0375419810 6442066744 0744518501 2473577281 7661423645 3548420037 7763634426 5065536569 8630624737 7243422716 7346619697 6282769134 0559657695 4699821429 5724149934 2636346402 8400123354 9793635157 6633498849 8300104807 6077510353 1747724843 1310041612 6842044953 4607438001 3980501657 5614718091 3619318425 3299137677 4658697987 1594201127 5596678684 5483351356 5218675379 3083683807 7044336051
1776905264 7465046323 1468789141 0816773398 3659284986 4934901958 9850475128 9818165950 3132382198 5150070350 7405666849 3842206642 9022848659 6372505498 4014022041 3722401680 5390017242 3772972536 4518718113 3595302275 3316829596 7068580425 6463581933 0117232762 2882409671
441 1436787783 8423134779 4333337854 4914992657 6641467656 8720351199 0936912418 3118968326 0158709927 7544801670 1565086319 5466811151
2856130 6056344360 0588818596 4353977718 8319985350 5044756670 3951375401
1 5942543185 2247487127 2829109709 2666512556 7335199301
249069045 3249897842 4629222172 6316730985 4067173801
6571509 5274581816 7746141634 3282023191
239480 9914605089 9902070623 2704730901
15446 0485600854 8904913170 3143194891
9730 9366304770 8043077172 9800581101
142 6518723847 2159329262 4383024931
11 2354763325 5734932054 5902125721
11 0529836802 0033351623 2595585323
3 3947927998 3473459058 4485779451
1 9113592906 8762580483 8112186351
1821392 7105245760 0225090701
4162 3133195856 4544051551
42 5405368989 5515567507
13 8292368403 6831357243
1006618129 0734628711
196059560 3636894101
112276562 0590142731
10732507 7734798309
8646265 8097891399
591267 0550135051
296734 1998548751
196181 2523207681
77541 0417615511
50739 2058891961
36359 9513050447
19668 4414569289
3192 2859356251
997 8027899923
160 9495760701
53 9403703651
36 4192333651
5 7494674801
1 0932568651
2791931561
2223552151
1671307201
1157675977
825802981
756280801
441690859
346056499
145928791
113822551
49345201
38366677
17761771
14765227
12460501
6326053
996301
644491
328051
244381
217351
157951
59581
50461
17551
17011
15859
15823
8101
6121
5581
4051
3881
1621
1567
1459
811
487
271
181
163
151
31
19
13
113
7
5
34
29

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.462135%

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 = 629 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 ≡ 47 (mod 63) 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 = 6502 significant digits (6500 digits displayed)
Input file is:  IO\19FF0FD3.cin
Certificate file is:  IO\19FF0FD3.chg
Found values of n, F and G.
    Number to be tested has 15484 digits.
    Modulus has 4098 digits.
Modulus is 26.46213525% 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 = 18, u = 8. Right endpoint has 3193 digits.
        Done!  Time elapsed:  39397469ms.
    Running CHG with h = 18, u = 8. Right endpoint has 3164 digits.
        Done!  Time elapsed:  16107718ms.
    Running CHG with h = 18, u = 8. Right endpoint has 3135 digits.
        Done!  Time elapsed:  31590579ms.
    Running CHG with h = 18, u = 8. Right endpoint has 3105 digits.
        Done!  Time elapsed:  46755156ms.
    Running CHG with h = 17, u = 7. Right endpoint has 3073 digits.
        Done!  Time elapsed:  34572094ms.
    Running CHG with h = 17, u = 7. Right endpoint has 3058 digits.
        Done!  Time elapsed:  38037437ms.
    Running CHG with h = 17, u = 7. Right endpoint has 3040 digits.
        Done!  Time elapsed:  25253406ms.
    Running CHG with h = 17, u = 7. Right endpoint has 3021 digits.
        Done!  Time elapsed:  130655282ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2998 digits.
        Done!  Time elapsed:  140929875ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2972 digits.
        Done!  Time elapsed:  159077281ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2943 digits.
        Done!  Time elapsed:  37041281ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2909 digits.
        Done!  Time elapsed:  42164266ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2871 digits.
        Done!  Time elapsed:  43949937ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2827 digits.
        Done!  Time elapsed:  8684985ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2814 digits.
        Done!  Time elapsed:  9467312ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2798 digits.
        Done!  Time elapsed:  9838469ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2780 digits.
        Done!  Time elapsed:  58140390ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2759 digits.
        Done!  Time elapsed:  9206735ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2734 digits.
        Done!  Time elapsed:  10599469ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2706 digits.
        Done!  Time elapsed:  4910093ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2672 digits.
        Done!  Time elapsed:  12684578ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2633 digits.
        Done!  Time elapsed:  14572375ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2588 digits.
        Done!  Time elapsed:  13899938ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2535 digits.
        Done!  Time elapsed:  7851937ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2517 digits.
        Done!  Time elapsed:  7352672ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2497 digits.
        Done!  Time elapsed:  4740453ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2472 digits.
        Done!  Time elapsed:  6267391ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2442 digits.
        Done!  Time elapsed:  8843250ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2406 digits.
        Done!  Time elapsed:  7856000ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2363 digits.
        Done!  Time elapsed:  7324141ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2306 digits.
        Done!  Time elapsed:  16484547ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2242 digits.
        Done!  Time elapsed:  1853078ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2224 digits.
        Done!  Time elapsed:  2248156ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2202 digits.
        Done!  Time elapsed:  2212109ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2174 digits.
        Done!  Time elapsed:  1944110ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2136 digits.
        Done!  Time elapsed:  1590265ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2084 digits.
        Done!  Time elapsed:  3761110ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2016 digits.
        Done!  Time elapsed:  3656718ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1939 digits.
        Done!  Time elapsed:  694219ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1908 digits.
        Done!  Time elapsed:  544922ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1887 digits.
        Done!  Time elapsed:  845547ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1830 digits.
        Done!  Time elapsed:  709125ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1759 digits.
        Done!  Time elapsed:  640531ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1601 digits.
        Done!  Time elapsed:  469438ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1231 digits.
        Done!  Time elapsed:  154437ms.
A certificate has been saved to the file:  IO\19FF0FD3.chg

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

Testing a PRP called "IO\19FF0FD3.cin".

Pol[1, 1] with [h, u]=[7, 2] has ratio=2.794681358 E-1126 at X, ratio=8.94888212 E-2588 at Y, witness=3.
Pol[2, 1] with [h, u]=[8, 3] has ratio=9.56675740 E-2588 at X, ratio=1.894395319 E-1109 at Y, witness=3.
Pol[3, 1] with [h, u]=[8, 3] has ratio=1.894395319 E-1109 at X, ratio=6.81085588 E-476 at Y, witness=3.
Pol[4, 1] with [h, u]=[8, 3] has ratio=1.148445963 E-213 at X, ratio=5.060804732 E-213 at Y, witness=2.
Pol[5, 1] with [h, u]=[10, 3] has ratio=0.2140411187 at X, ratio=2.605223063 E-172 at Y, witness=2.
Pol[6, 1] with [h, u]=[9, 3] has ratio=0.4683962622 at X, ratio=8.33323623 E-63 at Y, witness=5.
Pol[7, 1] with [h, u]=[10, 3] has ratio=0.4151972293 at X, ratio=1.582709123 E-94 at Y, witness=3.
Pol[8, 1] with [h, u]=[11, 4] has ratio=0.2527515335 at X, ratio=5.03050235 E-308 at Y, witness=11.
Pol[9, 1] with [h, u]=[11, 4] has ratio=0.02999846922 at X, ratio=1.025540833 E-273 at Y, witness=3.
Pol[10, 1] with [h, u]=[11, 4] has ratio=9.00843222 E-55 at X, ratio=1.368056446 E-208 at Y, witness=2.
Pol[11, 1] with [h, u]=[11, 4] has ratio=2.508478891 E-39 at X, ratio=6.161202396 E-152 at Y, witness=5.
Pol[12, 1] with [h, u]=[11, 4] has ratio=0.2272831709 at X, ratio=2.956388156 E-112 at Y, witness=3.
Pol[13, 1] with [h, u]=[11, 4] has ratio=0.4576390258 at X, ratio=5.460972214 E-90 at Y, witness=7.
Pol[14, 1] with [h, u]=[11, 4] has ratio=0.1352763327 at X, ratio=3.366577260 E-72 at Y, witness=2.
Pol[15, 1] with [h, u]=[13, 5] has ratio=0.01424935102 at X, ratio=6.33041427 E-321 at Y, witness=3.
Pol[16, 1] with [h, u]=[13, 5] has ratio=4.004251868 E-58 at X, ratio=1.276158065 E-284 at Y, witness=17.
Pol[17, 1] with [h, u]=[13, 5] has ratio=7.18156345 E-45 at X, ratio=3.872921894 E-219 at Y, witness=7.
Pol[18, 1] with [h, u]=[13, 5] has ratio=0.1453309488 at X, ratio=2.082172196 E-179 at Y, witness=5.
Pol[19, 1] with [h, u]=[13, 5] has ratio=0.2507917230 at X, ratio=1.288404756 E-149 at Y, witness=5.
Pol[20, 1] with [h, u]=[13, 5] has ratio=0.05030857154 at X, ratio=7.47190781 E-125 at Y, witness=13.
Pol[21, 1] with [h, u]=[13, 5] has ratio=0.1784157376 at X, ratio=3.485672304 E-104 at Y, witness=3.
Pol[22, 1] with [h, u]=[13, 5] has ratio=0.0629230129 at X, ratio=6.700393800 E-87 at Y, witness=7.
Pol[23, 1] with [h, u]=[15, 6] has ratio=0.01497327696 at X, ratio=1.298768645 E-319 at Y, witness=3.
Pol[24, 1] with [h, u]=[15, 6] has ratio=0.1798019854 at X, ratio=4.64598606 E-274 at Y, witness=7.
Pol[25, 1] with [h, u]=[15, 6] has ratio=0.0695648050 at X, ratio=5.213916244 E-235 at Y, witness=41.
Pol[26, 1] with [h, u]=[15, 6] has ratio=0.1802481721 at X, ratio=1.463983051 E-201 at Y, witness=7.
Pol[27, 1] with [h, u]=[15, 6] has ratio=0.2981336064 at X, ratio=7.19241823 E-173 at Y, witness=11.
Pol[28, 1] with [h, u]=[15, 6] has ratio=0.03814363067 at X, ratio=3.197275162 E-148 at Y, witness=3.
Pol[29, 1] with [h, u]=[15, 6] has ratio=0.03979837007 at X, ratio=3.194398123 E-127 at Y, witness=5.
Pol[30, 1] with [h, u]=[15, 6] has ratio=0.1306391913 at X, ratio=4.164375340 E-109 at Y, witness=5.
Pol[31, 1] with [h, u]=[15, 6] has ratio=0.1332309478 at X, ratio=1.055044442 E-93 at Y, witness=11.
Pol[32, 1] with [h, u]=[15, 6] has ratio=0.2812036945 at X, ratio=2.327253955 E-80 at Y, witness=31.
Pol[33, 1] with [h, u]=[17, 7] has ratio=0.2854386929 at X, ratio=2.581451275 E-308 at Y, witness=3.
Pol[34, 1] with [h, u]=[17, 7] has ratio=0.0937849043 at X, ratio=7.88947467 E-270 at Y, witness=11.
Pol[35, 1] with [h, u]=[17, 7] has ratio=0.3089334567 at X, ratio=3.294357766 E-236 at Y, witness=2.
Pol[36, 1] with [h, u]=[17, 7] has ratio=0.01222873130 at X, ratio=8.65707116 E-207 at Y, witness=2.
Pol[37, 1] with [h, u]=[17, 7] has ratio=0.0760356172 at X, ratio=4.607929590 E-181 at Y, witness=19.
Pol[38, 1] with [h, u]=[17, 7] has ratio=0.03721772896 at X, ratio=1.722012514 E-158 at Y, witness=3.
Pol[39, 1] with [h, u]=[17, 7] has ratio=0.2540722450 at X, ratio=9.81811691 E-139 at Y, witness=5.
Pol[40, 1] with [h, u]=[17, 7] has ratio=0.1886014866 at X, ratio=1.514870951 E-121 at Y, witness=2.
Pol[41, 1] with [h, u]=[17, 7] has ratio=0.2945952901 at X, ratio=2.018388110 E-106 at Y, witness=2.
Pol[42, 1] with [h, u]=[18, 8] has ratio=0.1727624749 at X, ratio=7.04071195 E-259 at Y, witness=3.
Pol[43, 1] with [h, u]=[18, 8] has ratio=0.0930746276 at X, ratio=9.42101617 E-244 at Y, witness=2.
Pol[44, 1] with [h, u]=[18, 8] has ratio=0.04632371778 at X, ratio=1.297898731 E-230 at Y, witness=37.
Pol[45, 1] with [h, u]=[18, 8] has ratio=5.356653402 E-30 at X, ratio=1.167947391 E-227 at Y, witness=2.

Validated in 70 sec.


Congratulations! n is prime!

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