Primality Certificate for (9945^3541-1)/9944

Andy Steward14,152 digits25 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.487154% factorization of N-1:

From Factorisation
99453 · 3 · 5 · 13 · 17
Φ22 · 4973
Φ331 · 67 · 47623
Φ42 · 241 · 449 · 457
Φ571 · 7001 · 19680874651
Φ67 · 19 · 103 · 7219
Φ1041 · 751 · 317652069191
Φ1237 · 421 · 17713 · 35452201
Φ15541 · 1335991 · 132371298851503606156051
Φ20262901 · 23285761 · 195257441 · 80047547101
Φ3015513132762031 · 6168541031637076591
Φ591257409 · 41840441 · 12010741747 · 9308454432529531 · 16772260974909555610008089 · p167
Φ6061 · 261841544256081852854571361 · p36
Φ11852752019 · 88036535207008025249503457 · 5840696858128371664067441173 · p171
Φ177709 · 210277 · 746233 · 1335289 · 30895351 · c437
Φ2361619669 · 1252852474301 · 476928834027921049 · c428
Φ295285389491 · 73968301530818131 · 20827950958552730891 · 220570910310716587561 · c863
Φ3543541 · 31153 · 96370671037 · c445
Φ590591181 · 46511471 · p915
Φ7082833 · 53101 · 82837 · 21261241 · 16769709241 · c897
Φ88584961 · 7707907731226139491 · 3486002606660332449751 · c1810
Φ11801181 · 4721 · 1204781 · 23884381 · p1835
Φ17708909942671135921 · 64102248583868607310441 · c1817
Φ3540c3710

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

48229 7918683027 9483283611 9118687842 0096806748 3842225626 3929224475 6252080405 1506971660 5508206984 0313358406 5603318994 6011815964 0839888991 4592802647 6202894737 7959553016 3707891828 6575262485 9031786531 6623341776 5575937049 4003648382 3330696747 5459193668 5571592036 9641476006 3009597620 8165100891 1587661665 0155165579 7804158243 9467471858 1079884832 1715508232 0405889408 3525498347 0948018817 8100456497 2434149372 1566875923 5179600738 0372648934 3677382297 5946661755 6232101790 8022325403 2309958086 8953572318 1519619453 0028593340 2480454283 6971872666 6101747691 3030764080 2355868150 4165639642 5247269429 1893899871 0546031558 5327071083 9919051559 2536939505 5016186919 0960928617 6487618856 4272044747 4847202756 3931755906 6127967197 7772356480 5651289570 5627119088 0883944712 8009267507 2448485799 3194923278 8740517861 7492271280 7937084971 2220282425 4925372802 6159801768 8009674071 3640251561 4343250484 2292615342 2105054156 1204758038 9506929620 1179212893 5634514281 1894580914 0905572594 7525359834 2718455695 2526988555 6636032371 5629477160 7583248717 8484481273 6335790762 1637284062 8371392764 4853166914 2651888376 5041725203 9403716615 2422045295 9458518579 9376462170 3508306897 0195429771 2653407532 1687151206 8880615934 9021439757 0011922065 0618846302 3372293051 6266552784 1383744473 3101253574 7259329973 6431494833 7564179624 1219402113 1900476366 9347895831 8004956039 9046194651 2713320471 0718159785 2981786012 0081631249 0814787382 4034156789 7824643378 8980275354 2754020012 7049236843 3799696652 7556075578 4143544245 6035178163 9834776311 7452757594 1378028267 1496295319 6562536468 3481766903 0447465642 3950720112 2728318509 8176846774 1540472238 2826368052 3818453725 9327587023 5601506062 8095905958 6628829797 0134279488 6540987895 6548385535 7244935679 0680443919 0851199460 6981594537 1461638105 7729606762 8453921606 0800596145 1582164829 7172773346 4409857071 4498498272 6624876947 9479217462 0780849343 6343131863 6797693333 2056445481 4886644941
10117 5140340487 9029191417 3895744563 0019674964 1475588074 1622277709 8749416046 7553316168 9782738410 7919276626 0038856780 1046209924 2229627067 1384395499 9764776325 9884255148 7746169213 3667592175 5306226703 5635380337 8803153493 4985819557 4030574169 9664494417 6038368901 3329863391 6643844851 2097860268 1603187454 5431694969 0990680392 6783172468 0698503677 8303617530 1702437267 4222706038 8537398808 8580303815 3410511546 1396819727 0035894342 2709084719 2609993582 0870222904 2889143830 9545453622 6340599666 9732734612 0661584996 5744109711 2469892167 7327478203 2362719957 0439901648 1961827350 7140410195 8599466163 1358911094 2580982565 5646817274 9844667201 5280528592 6970299839 4885979177 2085594360 1089957325 0301038500 6389295756 0464694454 3285312367 5045606276 4383647473 5975688294 3245909142 5681504483 9428000702 0629656924 0934385060 6009006701 8210302165 6811838687 2611893795 8762212335 0448370549 5120253152 3407318466 9125956035 8795877090 9532363080 7598660001 1169374571
2 6771167469 4825743475 1059681312 9960137021 8016542641 4095426885 3546215512 9875323864 1308831728 0253730696 8183700577 6395156153 4033114067 2623162107 0778729328 7304712402 4409054359
7362232 1753677006 8237226196 4275878320 5630342285 7242370653 8110019978 6636410729 6724267523 4387625117 1451665681 2908075114 6662641090 2632493101 8275224908 1126135505 9448503283
573202 6837560660 7624627746 6056193781
58406968 5812837166 4067441173
2618415 4425608185 2854571361
880365 3520700802 5249503457
167722 6097490955 5610008089
1323 7129885150 3606156051
641 0224858386 8607310441
34 8600260666 0332449751
2 2057091031 0716587561
2082795095 8552730891
770790773 1226139491
616854103 1637076591
47692883 4027921049
7396830 1530818131
930845 4432529531
890994 2671135921
1551 3132762031
125 2852474301
31 7652069191
9 6370671037
8 0047547101
1 9680874651
1 6769709241
1 2010741747
285389491
195257441
52752019
46511471
41840441
35452201
30895351
23884381
23285761
21261241
1619669
1335991
1335289
1257409
1204781
746233
591181
262901
210277
84961
82837
53101
47623
31153
17713
7219
7001
4973
4721
3541
2833
1181
751
709
541
457
449
421
241
103
71
67
61
41
37
31
19
17
13
7
5
32
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.487154%

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 ≡ 45 (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 = 6001 significant digits (6000 digits displayed)
Input file is:  IO\26D90DD5.cin
Certificate file is:  IO\26D90DD5.chg
Found values of n, F and G.
    Number to be tested has 14152 digits.
    Modulus has 3749 digits.
Modulus is 26.48715424% 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 2907 digits.
        Done!  Time elapsed:  29596797ms.
    Running CHG with h = 18, u = 8. Right endpoint has 2878 digits.
        Done!  Time elapsed:  25143328ms.
    Running CHG with h = 18, u = 8. Right endpoint has 2847 digits.
        Done!  Time elapsed:  69801407ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2814 digits.
        Done!  Time elapsed:  18140265ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2798 digits.
        Done!  Time elapsed:  18370594ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2779 digits.
        Done!  Time elapsed:  19810344ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2758 digits.
        Done!  Time elapsed:  123679656ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2733 digits.
        Done!  Time elapsed:  132512016ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2705 digits.
        Done!  Time elapsed:  142562468ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2673 digits.
        Done!  Time elapsed:  35056422ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2636 digits.
        Done!  Time elapsed:  35332969ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2594 digits.
        Done!  Time elapsed:  21182734ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2580 digits.
        Done!  Time elapsed:  21206719ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2564 digits.
        Done!  Time elapsed:  21041500ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2545 digits.
        Done!  Time elapsed:  20841484ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2523 digits.
        Done!  Time elapsed:  11916313ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2497 digits.
        Done!  Time elapsed:  15645844ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2467 digits.
        Done!  Time elapsed:  17763062ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2432 digits.
        Done!  Time elapsed:  21563063ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2391 digits.
        Done!  Time elapsed:  24902609ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2343 digits.
        Done!  Time elapsed:  13544688ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2329 digits.
        Done!  Time elapsed:  13898843ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2313 digits.
        Done!  Time elapsed:  3604328ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2292 digits.
        Done!  Time elapsed:  4106922ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2268 digits.
        Done!  Time elapsed:  4814547ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2239 digits.
        Done!  Time elapsed:  5542641ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2205 digits.
        Done!  Time elapsed:  6456890ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2163 digits.
        Done!  Time elapsed:  7951782ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2109 digits.
        Done!  Time elapsed:  8969453ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2048 digits.
        Done!  Time elapsed:  1770187ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2027 digits.
        Done!  Time elapsed:  2301797ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2002 digits.
        Done!  Time elapsed:  1772453ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1970 digits.
        Done!  Time elapsed:  828282ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1927 digits.
        Done!  Time elapsed:  2162359ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1867 digits.
        Done!  Time elapsed:  1721437ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1797 digits.
        Done!  Time elapsed:  576250ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1777 digits.
        Done!  Time elapsed:  617313ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1747 digits.
        Done!  Time elapsed:  629031ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1726 digits.
        Done!  Time elapsed:  639656ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1698 digits.
        Done!  Time elapsed:  640157ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1660 digits.
        Done!  Time elapsed:  616531ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1604 digits.
        Done!  Time elapsed:  386141ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1520 digits.
        Done!  Time elapsed:  660953ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1407 digits.
        Done!  Time elapsed:  154093ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1262 digits.
        Done!  Time elapsed:  155782ms.
    Running CHG with h = 7, u = 2. Right endpoint has 973 digits.
        Done!  Time elapsed:  140953ms.
    Running CHG with h = 5, u = 1. Right endpoint has 142 digits.
        Done!  Time elapsed:  27015ms.
A certificate has been saved to the file:  IO\26D90DD5.chg

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

Testing a PRP called "IO\26D90DD5.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.532149054 E-635 at X, ratio=1.045964725 E-776 at Y, witness=5.
Pol[2, 1] with [h, u]=[7, 2] has ratio=1.858529181 E-23 at X, ratio=2.416229194 E-1662 at Y, witness=3.
Pol[3, 1] with [h, u]=[7, 2] has ratio=9.80546973 E-579 at X, ratio=9.91305623 E-579 at Y, witness=2.
Pol[4, 1] with [h, u]=[7, 2] has ratio=4.497267866 E-290 at X, ratio=9.32934950 E-290 at Y, witness=43.
Pol[5, 1] with [h, u]=[9, 3] has ratio=0.4096973843 at X, ratio=1.631687890 E-340 at Y, witness=5.
Pol[6, 1] with [h, u]=[9, 3] has ratio=3.274233705 E-85 at X, ratio=2.763893838 E-253 at Y, witness=11.
Pol[7, 1] with [h, u]=[9, 3] has ratio=3.779692602 E-57 at X, ratio=4.092661878 E-169 at Y, witness=5.
Pol[8, 1] with [h, u]=[9, 3] has ratio=0.3813006019 at X, ratio=1.217531975 E-113 at Y, witness=5.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.3486556426 at X, ratio=1.920457154 E-85 at Y, witness=2.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.2925049949 at X, ratio=3.115370316 E-64 at Y, witness=13.
Pol[11, 1] with [h, u]=[10, 3] has ratio=0.2229256289 at X, ratio=1.095817865 E-89 at Y, witness=3.
Pol[12, 1] with [h, u]=[10, 3] has ratio=0.4255497106 at X, ratio=4.452594180 E-60 at Y, witness=2.
Pol[13, 1] with [h, u]=[11, 4] has ratio=0.502750537 at X, ratio=1.910630397 E-283 at Y, witness=7.
Pol[14, 1] with [h, u]=[11, 4] has ratio=3.462401374 E-61 at X, ratio=2.517237101 E-239 at Y, witness=7.
Pol[15, 1] with [h, u]=[11, 4] has ratio=1.356962763 E-44 at X, ratio=2.880366118 E-174 at Y, witness=7.
Pol[16, 1] with [h, u]=[11, 4] has ratio=0.1111895405 at X, ratio=4.450068246 E-127 at Y, witness=7.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.3026517780 at X, ratio=5.700905486 E-102 at Y, witness=7.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.02021611826 at X, ratio=1.335710362 E-81 at Y, witness=7.
Pol[19, 1] with [h, u]=[13, 5] has ratio=0.3778085599 at X, ratio=2.335233027 E-310 at Y, witness=3.
Pol[20, 1] with [h, u]=[13, 5] has ratio=2.554073103 E-55 at X, ratio=5.180434424 E-269 at Y, witness=5.
Pol[21, 1] with [h, u]=[13, 5] has ratio=0.3023758812 at X, ratio=7.06869416 E-209 at Y, witness=5.
Pol[22, 1] with [h, u]=[13, 5] has ratio=0.3204438217 at X, ratio=3.585254250 E-174 at Y, witness=7.
Pol[23, 1] with [h, u]=[13, 5] has ratio=0.3747393172 at X, ratio=2.779659019 E-145 at Y, witness=2.
Pol[24, 1] with [h, u]=[13, 5] has ratio=0.1799103775 at X, ratio=2.819335300 E-121 at Y, witness=5.
Pol[25, 1] with [h, u]=[13, 5] has ratio=0.0710587134 at X, ratio=3.586723391 E-101 at Y, witness=3.
Pol[26, 1] with [h, u]=[13, 5] has ratio=0.04284364824 at X, ratio=1.910687969 E-84 at Y, witness=11.
Pol[27, 1] with [h, u]=[13, 5] has ratio=0.1311020502 at X, ratio=2.109767900 E-70 at Y, witness=2.
Pol[28, 1] with [h, u]=[15, 6] has ratio=0.2252527167 at X, ratio=1.929472184 E-287 at Y, witness=31.
Pol[29, 1] with [h, u]=[15, 6] has ratio=0.1817761256 at X, ratio=1.843102670 E-246 at Y, witness=11.
Pol[30, 1] with [h, u]=[15, 6] has ratio=0.1970467064 at X, ratio=2.095589326 E-211 at Y, witness=3.
Pol[31, 1] with [h, u]=[15, 6] has ratio=0.4173485225 at X, ratio=2.435916001 E-181 at Y, witness=3.
Pol[32, 1] with [h, u]=[15, 6] has ratio=0.3386763848 at X, ratio=1.752077742 E-155 at Y, witness=41.
Pol[33, 1] with [h, u]=[15, 6] has ratio=0.2472875231 at X, ratio=2.233722985 E-133 at Y, witness=13.
Pol[34, 1] with [h, u]=[15, 6] has ratio=0.1861996246 at X, ratio=2.013537250 E-114 at Y, witness=7.
Pol[35, 1] with [h, u]=[15, 6] has ratio=0.4724563008 at X, ratio=3.356685964 E-98 at Y, witness=37.
Pol[36, 1] with [h, u]=[15, 6] has ratio=0.1194105938 at X, ratio=2.900996386 E-84 at Y, witness=7.
Pol[37, 1] with [h, u]=[17, 7] has ratio=0.3136079361 at X, ratio=2.380410923 E-294 at Y, witness=3.
Pol[38, 1] with [h, u]=[17, 7] has ratio=0.1411459968 at X, ratio=1.124543578 E-257 at Y, witness=2.
Pol[39, 1] with [h, u]=[17, 7] has ratio=0.0884251091 at X, ratio=1.602780900 E-225 at Y, witness=2.
Pol[40, 1] with [h, u]=[17, 7] has ratio=0.0893007721 at X, ratio=1.992324757 E-197 at Y, witness=3.
Pol[41, 1] with [h, u]=[17, 7] has ratio=0.2625159608 at X, ratio=7.29915405 E-173 at Y, witness=23.
Pol[42, 1] with [h, u]=[17, 7] has ratio=0.00866319143 at X, ratio=2.206876492 E-151 at Y, witness=3.
Pol[43, 1] with [h, u]=[17, 7] has ratio=0.2952633768 at X, ratio=1.655299069 E-132 at Y, witness=7.
Pol[44, 1] with [h, u]=[17, 7] has ratio=0.05569113400 at X, ratio=4.896068246 E-116 at Y, witness=17.
Pol[45, 1] with [h, u]=[18, 8] has ratio=0.2899631908 at X, ratio=1.782179168 E-260 at Y, witness=3.
Pol[46, 1] with [h, u]=[18, 8] has ratio=0.2827782411 at X, ratio=4.036149882 E-245 at Y, witness=5.
Pol[47, 1] with [h, u]=[18, 8] has ratio=0.1700676635 at X, ratio=3.033498616 E-239 at Y, witness=13.

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.