Primality Certificate for (3949^2341-1)/3948

Andy Steward8,416 digits13 February 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.424704% factorization of N-1:

From Factorisation
394911 · 359
Φ22 · 5 · 5 · 79
Φ33 · 43 · 120919
Φ42 · 101 · 77201
Φ5971 · 250518207031
Φ613 · 37 · 32413
Φ93 · 19 · 1009 · 7723 · 8538286938949
Φ105 · 941 · 51674816761
Φ1245061 · 5396941141
Φ13521 · 178347308014877 · 154828644925620758585203153
Φ15382013533351 · 154777679598553351
Φ1859167 · 64097819089080859
Φ2059142140960266467063435829201
Φ26131 · 443 · 686011 · 9430721 · 45453197843 · 842597568319417
Φ3031 · 61 · 151 · 691 · 299819936788186296271
Φ3695401 · p39
Φ39418939 · 12634284627888187221439 · 351918857208444493393018009 · p33
Φ45181 · 991 · 223352281 · 453908020458110810862724828129445941 · p38
Φ5253 · 53398021 · 582235233529 · 95447911495390793 · 2576430528758099783173 · 510512994418098428435797717
Φ603061 · 29221 · 665761 · 727201 · 1142161 · 177379021 · 398688184596620435227981
Φ652126581768481 · 4769668224192301 · p145
Φ7813 · 821497 · 1297879223574003186681712038139 · p50
Φ90p87
Φ1172341 · 21061 · 730691758914062206483 · c231
Φ1302731 · 98801 · 17015074051 · 190306080316171 · 4046062517781860224741 · c119
Φ156157 · p171
Φ180541 · 1056061 · 1296181 · 4990763940138987088681 · 10743655586812348172404681 · p112
Φ19523011 · c341
Φ23415913 · 240674383 · 567956139216046191080497 · c223
Φ26024226645301 · 3120934053641 · 9361872079715234599339194961 · c295
Φ39025147329326530959211 · c326
Φ46851949 · 2981703543157 · c501
Φ5851171 · 10531 · 423541 · 15099174351299611 · c1007
Φ780468001 · 4787169847981 · 29007897243782341 · 7255435059493436401 · p637
Φ117016381 · 41211932581 · c1021
Φ23402129401 · 1925588106845402221 · c2047

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

7112533 4924133058 3773949342 4157714587 6232639884 0454353068 6751398344 8003685708 1220072767 9614682773 1005944739 8973473077 1831836678 8932863808 9992421465 7728438654 4209975799 9942216072 6449562069 5997567503 4128381185 8941780797 5828349966 1339186572 1071782461 9153363526 4985440482 7476861080 8919893975 0626598199 7714702495 2361083555 8682971597 2199931388 1337865318 4297406351 9376013905 1972200760 0053714765 4607608808 1754402284 6546678553 1647068036 8339745548 4946348714 8917744394 8801765177 8849648591 7376342106 2775719158 4471844774 2879078786 5182371244 8738048790 5549216603 1652510784 6302787154 6079669957 5779422426 1834036240 6570534846 6940909638 5154351733 8224147281
2 7257297530 5018905117 0179252503 6555047095 0409728599 6274615851 2818070091 8328955930 3656095304 6341572435 1778031059 0401318805 8786747557 8581242550 4387243163 3254052862 3031455893
42179 5723842034 5403071763 1607959449 7808281876 2226058827 6765178571 5027164057 0122076560 3065426105 0820906907 1287808738 1371616087 5489673643 4565470821
10 7773352476 3522838473 3070224497 9801046930 6360419455 2541186841 1381560344 3872041605 2482231909 2808727631 3288973061
2068669 9683643555 3650406183 6545683604 3226267493 7118564495 8607493529 8464216018 7075847601
1492854759 7665729982 1800360566 3986604964 3706622919
150762273 4317303243 4407967584 4923248401
11375768 1348067982 4647809198 0068864511
453908 0204581108 1086272482 8129445941
111 0292057260 3786225258 3092482309
1 2978792235 7400318668 1712038139
591421409 6026646706 3435829201
93618720 7971523459 9339194961
5105129 9441809842 8435797717
3519188 5720844449 3393018009
1548286 4492562075 8585203153
107436 5558681234 8172404681
5679 5613921604 6191080497
3986 8818459662 0435227981
126 3428462788 8187221439
49 9076394013 8987088681
40 4606251778 1860224741
25 7643052875 8099783173
7 3069175891 4062206483
2 9981993678 8186296271
2514732932 6530959211
725543505 9493436401
192558810 6845402221
15477767 9598553351
9544791 1495390793
6409781 9089080859
2900789 7243782341
1509917 4351299611
476966 8224192301
84259 7568319417
19030 6080316171
17834 7308014877
853 8286938949
478 7169847981
312 0934053641
298 1703543157
212 6581768481
58 2235233529
38 2013533351
25 0518207031
5 1674816761
4 5453197843
4 1211932581
2 4226645301
1 7015074051
5396941141
240674383
223352281
177379021
53398021
9430721
2129401
1296181
1142161
1056061
821497
727201
686011
665761
468001
423541
418939
120919
98801
95401
77201
59167
51949
45061
32413
29221
23011
21061
16381
15913
10531
7723
3061
2731
2341
1171
1009
991
971
941
691
541
521
443
359
181
157
151
131
101
79
61
53
43
37
31
19
132
11
53
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) = 27.424704%

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 = 14 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 ≡ 53 (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 = 3506 significant digits (3500 digits displayed)

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

Input file is:  IO\0F6D0925.cin
Certificate file is:  IO\0F6D0925.chg
Found values of n, F and G.
    Number to be tested has 8416 digits.
    Modulus has 2309 digits.
Modulus is 27.42470365% 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 = 10, u = 4. Right endpoint has 1493 digits.
        Done!  Time elapsed:  383516ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1473 digits.
        Done!  Time elapsed:  370844ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1449 digits.
        Done!  Time elapsed:  405640ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1419 digits.
        Done!  Time elapsed:  426329ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1385 digits.
        Done!  Time elapsed:  632875ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1350 digits.
        Done!  Time elapsed:  1863234ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1315 digits.
        Done!  Time elapsed:  2312578ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1275 digits.
        Done!  Time elapsed:  83109ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1262 digits.
        Done!  Time elapsed:  84719ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1245 digits.
        Done!  Time elapsed:  82375ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1222 digits.
        Done!  Time elapsed:  284906ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1192 digits.
        Done!  Time elapsed:  270891ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1151 digits.
        Done!  Time elapsed:  382000ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1097 digits.
        Done!  Time elapsed:  342125ms.
    Running CHG with h = 8, u = 3. Right endpoint has 1024 digits.
        Done!  Time elapsed:  178859ms.
    Running CHG with h = 7, u = 2. Right endpoint has 991 digits.
        Done!  Time elapsed:  248610ms.
    Running CHG with h = 7, u = 2. Right endpoint has 977 digits.
        Done!  Time elapsed:  243437ms.
    Running CHG with h = 7, u = 2. Right endpoint has 961 digits.
        Done!  Time elapsed:  262250ms.
    Running CHG with h = 7, u = 2. Right endpoint has 936 digits.
        Done!  Time elapsed:  266750ms.
    Running CHG with h = 7, u = 2. Right endpoint has 900 digits.
        Done!  Time elapsed:  258047ms.
    Running CHG with h = 7, u = 2. Right endpoint has 845 digits.
        Done!  Time elapsed:  156235ms.
    Running CHG with h = 7, u = 2. Right endpoint has 763 digits.
        Done!  Time elapsed:  88703ms.
    Running CHG with h = 7, u = 2. Right endpoint has 639 digits.
        Done!  Time elapsed:  146578ms.
    Running CHG with h = 5, u = 1. Right endpoint has 454 digits.
        Done!  Time elapsed:  11062ms.
    Running CHG with h = 5, u = 1. Right endpoint has 182 digits.
        Done!  Time elapsed:  14578ms.
A certificate has been saved to the file:  IO\0F6D0925.chg

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

Testing a PRP called "IO\0F6D0925.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.452535970 E-264 at X, ratio=4.061698344 E-444 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.2580048412 at X, ratio=2.159904938 E-273 at Y, witness=2.
Pol[3, 1] with [h, u]=[7, 2] has ratio=0.01370365490 at X, ratio=1.058954482 E-370 at Y, witness=7.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.2348601236 at X, ratio=2.160781909 E-247 at Y, witness=7.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.531513979 at X, ratio=3.593071194 E-165 at Y, witness=2.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.1608451986 at X, ratio=2.420714523 E-110 at Y, witness=3.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.2370946676 at X, ratio=7.89995595 E-74 at Y, witness=31.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.649684761 at X, ratio=1.883307356 E-49 at Y, witness=7.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.3570017360 at X, ratio=3.172924381 E-33 at Y, witness=2.
Pol[10, 1] with [h, u]=[6, 2] has ratio=0.1398493776 at X, ratio=9.01749590 E-29 at Y, witness=7.
Pol[11, 1] with [h, u]=[8, 3] has ratio=0.552818402 at X, ratio=1.073632884 E-100 at Y, witness=5.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.3293764703 at X, ratio=7.96670301 E-218 at Y, witness=7.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.1652765824 at X, ratio=2.218742262 E-163 at Y, witness=3.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.741311483 at X, ratio=8.06327982 E-123 at Y, witness=3.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.2796713318 at X, ratio=3.207327614 E-92 at Y, witness=13.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.1062933384 at X, ratio=2.266113732 E-69 at Y, witness=2.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.4221535564 at X, ratio=3.433896220 E-52 at Y, witness=5.
Pol[18, 1] with [h, u]=[8, 3] has ratio=0.02149506179 at X, ratio=1.850321622 E-40 at Y, witness=2.
Pol[19, 1] with [h, u]=[10, 4] has ratio=0.3660780927 at X, ratio=2.693737526 E-159 at Y, witness=2.
Pol[20, 1] with [h, u]=[10, 4] has ratio=0.05372991520 at X, ratio=9.27309457 E-142 at Y, witness=13.
Pol[21, 1] with [h, u]=[10, 4] has ratio=0.2585931229 at X, ratio=6.17200806 E-138 at Y, witness=5.
Pol[22, 1] with [h, u]=[10, 4] has ratio=0.3298279335 at X, ratio=6.00366433 E-138 at Y, witness=3.
Pol[23, 1] with [h, u]=[10, 4] has ratio=8.81685006 E-32 at X, ratio=1.190956864 E-121 at Y, witness=3.
Pol[24, 1] with [h, u]=[10, 4] has ratio=6.15816389 E-26 at X, ratio=1.886543353 E-97 at Y, witness=23.
Pol[25, 1] with [h, u]=[10, 4] has ratio=2.296582634 E-20 at X, ratio=4.294598556 E-78 at Y, witness=2.

Validated in 24 sec.


Congratulations! n is prime!

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