Primality Certificate for (15134^3697-1)/15133

Andy Steward15,450 digits09 January 2007
Originally by A.A.D.Steward 2007

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 27.223505% factorization of N-1:

From Factorisation
151342 · 7 · 23 · 47
Φ23 · 5 · 1009
Φ31567 · 146173
Φ417 · 13472821
Φ63 · 31 · 853 · 2887
Φ729 · 43 · 2689 · 3583387873324985237
Φ827409 · 1913910952193
Φ1167 · 89 · 727 · p36
Φ1213 · 4035260389201537
Φ14211 · 547 · 104093569308045126391
Φ16641 · 14321 · 124897 · 27126481 · 88481606184161
Φ21463 · 6007 · 11551 · 280183 · p35
Φ22p42
Φ245479892521 · 502178131513992756072841
Φ28113 · 174077 · 923708583080473 · 7944927482764130593781766217
Φ337223053003 · 45949498981 · p64
Φ42421891 · p45
Φ444104523237 · 91378330649 · p64
Φ4897 · 433 · 1061377 · 2575527757377003061249 · p35
Φ561840087369 · 2753480985083921 · p76
Φ66470970847495374899984653514920308412062751 · p42
Φ772927 · 683453 · 738878789419 · 15356201518986988133321 · c208
Φ843642183544907881 · 251317826171580427533188726114707772089 · p47
Φ88617 · 1999889 · p159
Φ112564257 · 43066129 · 343945057 · 3180825313 · 928693176053329 · c155
Φ132517201748317 · 7147056880261 · c143
Φ1543389 · 396822139483309 · 50934509260207873763 · p213
Φ16893016214257 · 633938661461589072174184475689 · c160
Φ176269281 · 392578913 · 124774585763454469968049 · c298
Φ23128183 · c498
Φ26412499227722999300449 · c316
Φ308p502
Φ336337 · 79479922033 · c388
Φ462c502
Φ528140449 · 373398664492129 · c650
Φ616105953 · 177409 · 2579809 · 2597057 · 50675857 · c973
Φ924237164570413 · c992
Φ1232325249 · c2001
Φ18483697 · 148474377115909153 · p1986
Φ36962790481 · 4124737 · 40279009 · 97989538417 · 1821928804774849 · c3966

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

434799 7248481893 3137781305 2767643842 9263118551 2370142766 1931578984 9250849936 4458422808 5537292357 9157850482 0201909165 3421400393 6343696740 4833444620 8471101155 1793682269 9326365060 0078272979 0276112439 7982792054 4954053554 7059998215 3566882049 5485225412 5286759461 1234469761 9410809415 3958122654 5062361528 2450350778 0205415121 7671424816 2632901214 5734466033 3705168302 5515861755 7801814227 8603090240 0299550066 2614988364 8917292820 8358148156 2159710964 2542770053 5892126444 7248316050 0800205608 0508917484 9269804096 4938499760 4417443816 9757909950 4082285295 7635755927 3006624401 9502742816 2396940727 6591922091 7137153712 6014029226 1996824549 7581677633 3109481460 7329720975 3119216661 5281128281 8728742520 3321880528 7101169591 6033701420 1913828108 9480322800 3054401963 4468789556 4765753319 0351646117 3825575274 7392746045 3564558929 6099929949 8647339686 2748884135 1523346246 5270027509 2469438929 9328720995 8343918356 2490102102 5474404876 5734348172 3900310854 8868791610 6969762222 3891913211 3795677637 3724376855 9113315279 0082581992 4311016260 5140184082 5069830231 5041477008 1267306141 7626820080 9792023913 7003438874 7015015984 4018727147 5120774476 5845146931 8336851598 9067499335 2110556536 9508640178 2873216664 9677399302 1823765939 7212879417 2213881390 0048592953 6675354353 6885243432 5703295114 6615356194 1052515885 9641727240 5101706595 9385445687 4790212246 1841628114 4968062493 1743619271 5593451066 0516553440 0287056830 8517813576 4178036348 1940603981 9946065892 1965237527 7519380610 3969872788 4344763924 7592384704 7710500205 1592247886 0126201030 5695230892 8318878658 3562892991 5396887886 1894071106 3742044898 2432451439 9801660360 7222780459 1631488674 5851895179 6470710092 5887290986 7632997542 4783325892 0402641747 0860261419 9420438923 6265678118 4930710393 6816084686 9959253508 5177927585 6497420433 5122768344 7197140352 2615946914 2942783391 4841723645 9529101912 6586014044 8851769723 5258756382 6379875948 0605580686 5962348632 7084161901 6063772800 1352887205 9393744988 7036517742 6170296365 1772296280 0761073352 5663439627 7957192692 3127863458 2750311179 9400461600 0046543986 9274494561
39 3049780141 0798093980 2340022176 2172675269 1539879980 7894069679 9991177984 9851303907 5425479904 9999755411 0827142892 9241431701 3655484432 1780634839 4059122436 4723980246 9590876979 2181492180 3570805014 5671989399 9326818064 2596368285 0730587710 9470417639 1571119384 9569524853 7512155277 3329320028 4757352949 0299084408 6951087353 6967349980 8340515517 2633826432 0893214510 0402339228 5518826374 1540418503 8242889866 6684191176 4531927522 8812034664 4087435710 7098144666 4447736390 3197401484 9505001580 8034560603 2898964946 3641216901
915 3198572921 4976276657 4347198115 4807858103 4019810388 4230981259 9304386080 3797853404 4037371552 4563697732 7778796074 5404590721 7762092306 1283377739 3231054306 8550834564 6072852408 3622866907 4285117893 4734112671 1852134077
127896343 8559606727 0613717174 0026530697 8115901722 2950351190 9531271730 3349337021 8243302877 8427288726 0403383352 6414587439 9120840299 6930444146 2751954003 2430325177
411309 7318152891 2831605173 0608923232 6296609450 7424191210 1534323379 9098724569
1196 8626462982 2155876903 2732746930 5970103968 7272602460 3038701357
1059 1772699504 1843059792 4523838002 8133612026 3968712736 4468288177
2276692 5718935447 8984782734 5107795864 2320993509
34219 4630318766 9186189533 1749135512 0135551901
84 3546956069 0534537476 5766063458 5561939401
63 0243827051 3360977934 4332413842 0824639711
47 0970847495 3748999846 5351492030 8412062751
251317826 1715804275 3318872611 4707772089
145400 7925125017 1706397580 7693877351
65957 4924536737 9459429096 5877115377
16036 7393340908 7304206174 0725392747
6339386614 6158907217 4184475689
79449274 8276413059 3781766217
5021 7813151399 2756072841
1247 7458576345 4469968049
153 5620151898 6988133321
25 7552775737 7003061249
1 0409356930 8045126391
5093450926 0207873763
1249922772 2999300449
358338787 3324985237
14847437 7115909153
403526 0389201537
364218 3544907881
275348 0985083921
182192 8804774849
92869 3176053329
92370 8583080473
39682 2139483309
37339 8664492129
8848 1606184161
714 7056880261
191 3910952193
73 8878789419
51 7201748317
23 7164570413
9 7989538417
9 3016214257
9 1378330649
7 9479922033
4 5949498981
7223053003
5479892521
4104523237
3180825313
1840087369
392578913
343945057
50675857
43066129
40279009
27126481
13472821
4124737
2790481
2597057
2579809
1999889
1061377
683453
564257
421891
325249
280183
269281
177409
174077
146173
140449
124897
105953
28183
27409
14321
11551
6007
3697
3389
2927
2887
2689
1567
1009
853
727
641
617
547
463
433
337
211
113
97
89
67
47
43
31
29
23
17
13
7
5
32
2

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) = 27.223505%

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 = 6 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:

realprecision = 6001 significant digits (6000 digits displayed)

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

Input file is:  IO\3B1E0E71.cin
Certificate file is:  IO\3B1E0E71.chg
Found values of n, F and G.
    Number to be tested has 15450 digits.
    Modulus has 4206 digits.
Modulus is 27.22350521% 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 = 12, u = 5. Right endpoint has 2833 digits.
        Done!  Time elapsed:  9669282ms.
    Running CHG with h = 12, u = 5. Right endpoint has 2767 digits.
        Done!  Time elapsed:  33303875ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2698 digits.
        Done!  Time elapsed:  2508718ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2676 digits.
        Done!  Time elapsed:  4986391ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2649 digits.
        Done!  Time elapsed:  5486672ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2617 digits.
        Done!  Time elapsed:  2944641ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2576 digits.
        Done!  Time elapsed:  8908875ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2526 digits.
        Done!  Time elapsed:  11337031ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2463 digits.
        Done!  Time elapsed:  14329375ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2384 digits.
        Done!  Time elapsed:  10957406ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2285 digits.
        Done!  Time elapsed:  656469ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2274 digits.
        Done!  Time elapsed:  634937ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2259 digits.
        Done!  Time elapsed:  1489844ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2239 digits.
        Done!  Time elapsed:  1615469ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2213 digits.
        Done!  Time elapsed:  1767203ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2178 digits.
        Done!  Time elapsed:  2115594ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2132 digits.
        Done!  Time elapsed:  2197687ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2070 digits.
        Done!  Time elapsed:  2325406ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1987 digits.
        Done!  Time elapsed:  3906922ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1876 digits.
        Done!  Time elapsed:  5261875ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1729 digits.
        Done!  Time elapsed:  119547ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1698 digits.
        Done!  Time elapsed:  127391ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1652 digits.
        Done!  Time elapsed:  172906ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1583 digits.
        Done!  Time elapsed:  123469ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1479 digits.
        Done!  Time elapsed:  202234ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1323 digits.
        Done!  Time elapsed:  380938ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1089 digits.
        Done!  Time elapsed:  57547ms.
    Running CHG with h = 5, u = 1. Right endpoint has 775 digits.
        Done!  Time elapsed:  41046ms.
    Running CHG with h = 5, u = 1. Right endpoint has 317 digits.
        Done!  Time elapsed:  77063ms.
A certificate has been saved to the file:  IO\3B1E0E71.chg

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

Testing a PRP called "IO\3B1E0E71.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.414807223 E-483 at X, ratio=8.54934797 E-800 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.2790536320 at X, ratio=1.354254375 E-458 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.908982503 E-314 at X, ratio=2.504478663 E-314 at Y, witness=3.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.1771903797 at X, ratio=1.059862219 E-468 at Y, witness=11.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.3883693521 at X, ratio=8.64997407 E-313 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.05521001606 at X, ratio=1.150410421 E-208 at Y, witness=5.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.1333079869 at X, ratio=2.049247452 E-139 at Y, witness=3.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.1113050195 at X, ratio=2.743696321 E-93 at Y, witness=3.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.1650300602 at X, ratio=2.871147523 E-62 at Y, witness=7.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.2082766229 at X, ratio=2.161036045 E-442 at Y, witness=2.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.528258009 at X, ratio=5.690413116 E-332 at Y, witness=5.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.0961478491 at X, ratio=3.724136513 E-249 at Y, witness=13.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.0936172779 at X, ratio=4.450152712 E-187 at Y, witness=3.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.1904916823 at X, ratio=1.875379046 E-140 at Y, witness=13.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.2909445761 at X, ratio=1.366367380 E-105 at Y, witness=3.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.4098941058 at X, ratio=2.501335540 E-79 at Y, witness=23.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.697881015 at X, ratio=1.186541664 E-59 at Y, witness=5.
Pol[18, 1] with [h, u]=[9, 3] has ratio=0.3589644951 at X, ratio=4.539902350 E-45 at Y, witness=2.
Pol[19, 1] with [h, u]=[9, 3] has ratio=0.04872042260 at X, ratio=7.071243104 E-34 at Y, witness=5.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.648449557 at X, ratio=1.261922752 E-395 at Y, witness=3.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.2719739437 at X, ratio=1.193311811 E-316 at Y, witness=2.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.05842127784 at X, ratio=1.743880509 E-253 at Y, witness=5.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.00907178960 at X, ratio=6.68075736 E-203 at Y, witness=2.
Pol[24, 1] with [h, u]=[11, 4] has ratio=0.05893025050 at X, ratio=1.891713284 E-162 at Y, witness=3.
Pol[25, 1] with [h, u]=[11, 4] has ratio=0.2886077374 at X, ratio=4.154642009 E-130 at Y, witness=3.
Pol[26, 1] with [h, u]=[10, 4] has ratio=1.582497298 E-28 at X, ratio=1.060755598 E-109 at Y, witness=3.
Pol[27, 1] with [h, u]=[10, 4] has ratio=7.41603946 E-23 at X, ratio=6.31422836 E-88 at Y, witness=17.
Pol[28, 1] with [h, u]=[12, 5] has ratio=0.527175457 at X, ratio=1.784301682 E-344 at Y, witness=5.
Pol[29, 1] with [h, u]=[12, 5] has ratio=1.252441712 E-66 at X, ratio=5.261145980 E-329 at Y, witness=7.

Validated in 108 sec.


Congratulations! n is prime!

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