Primality Certificate for (888^3169-1)/887

Andy Steward9,341 digits07 October 2009
Originally by A.A.D.Steward 2009
A066180 #449

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

From Factorisation
8882 · 2 · 2 · 3 · 37
Φ27 · 127
Φ3199 · 3967
Φ45 · 17 · 9277
Φ613 · 60589
Φ841 · 15165893657
Φ9109 · 307 · 1801 · 88903 · 91513
Φ11463 · 82963 · 7946091554302297799437
Φ123673 · 169289641
Φ16241 · 6113 · 262441364962025009
Φ1819 · 688591 · 37476830197
Φ2223 · 23 · 89 · 3301 · 2309077 · 848616055417241
Φ2410571017 · 74919121 · 488196073
Φ32449 · 2081 · 7937 · 989249 · 757425533294977 · 26902156179261793
Φ3367 · 98143 · 1038293365596970297 · p35
Φ3673 · 181 · 3889 · 1046651149 · 4470069305765790361
Φ44353 · 28766041594049 · p43
Φ482593 · 499671457 · p36
Φ66661 · 2377 · 1625005141 · p44
Φ728713 · 18879015669049 · p54
Φ88p118
Φ9697 · 94552033 · 11684067553 · 4697933078977 · p62
Φ9920593 · 98893390861 · 157984711225111 · p148
Φ1322113 · 3037 · 3697 · 62418799363240263088993 · 152990919426641732236778230671001 · p53
Φ144139191046715225521 · 145749930227068535406935569 · 96360799408921302229367056275394135537 · p61
Φ1763452709217 · 86659873956887089 · p210
Φ198370019827 · 13807234637603551 · 148741664695525497749051976788206723126934233 · p109
Φ26494953516194528377 · 14269134257278382857 · 58804412817082895689 · p180
Φ2883169 · 3457 · 37441 · c272
Φ352127447937 · 58906621829089 · 3386917619027650753 · 29136716098516281006057857 · 34224166266195177572442209 · 421393764855307195503580513 · c354
Φ396397 · 25741 · 198397 · c342
Φ52811617 · 323137 · 2489521 · 7682807816113 · p443
Φ792c708
Φ105660715332481 · 1571788562871352698287785921 · c906
Φ1584125668496531953 · 1850947218805806795169 · c1380
Φ31686337 · 69697 · c2822

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

776 1721987576 1905823589 0213254411 6119958059 7847874944 7176705006 8769932919 4250855236 8416685218 3114198899 2500966327 9758219381 1441333299 7858308371 9979586164 6633208404 1766053292 7080836613 4263512104 0919936009 5822178456 4350603315 5082853162 7833019926 0442915524 4433449708 4189515216 3323462626 9029405776 1464878813 1573505843 9079961313 3395043818 5726977688 2848254056 9838414764 7935741754 8723793179 4156585325 8310218939 6229614755 1941369657 1773435347 7030570753
2494934825 3145255104 5959611833 2773374588 2427009927 7287060980 5379478748 6175446231 6750337213 8632407667 4185356258 5993795918 3512629346 6971806007 4366587575 6628402962 9561834421 1459798672 0744496501 8816724592 5520030577
9369548610 5307122832 4316101623 5988271544 1751579194 6999351315 0323860188 9409296604 2908755615 1837914371 6234839322 7817516573 6464424672 6153286869 0333422712 7404267975 2832689964 8776778681
24961805 6599420974 3915672454 4610716136 3379505366 6213947479 8068054182 0823714340 1049835678 8161178906 5033012789 5531901727 9315298866 9732202173 4232612403
86400972 5727663725 3221259510 2448990374 9378832053 7735595686 8146879736 8464791334 3742479665 6216436974 7648613889 9768012801
105685062 5073139775 4511377740 9933723690 7449034462 8569857937 1197339054 5390266772 2649852382 9170381527 9361482029
44 3885965639 6357099478 1629030703 5432549001 5624211443 2913360161
1 7088435631 5568695715 6619454150 2704248100 3024446928 9137750097
3513 6954619081 3477471453 1845562922 8585355121 1642042113
381 3681122331 9771034561 3384291382 2555458619 1378697901
14874 1664695525 4977490519 7678820672 3126934233
3644 7079127218 9848213039 5576530370 7237672697
915 3853452182 3555508065 4068865361 8309738913
96360799 4089213022 2936705627 5394135537
115377 3059422546 2759761092 1103405121
13599 2751036729 0756128799 7892312197
152 9909194266 4173223677 8230671001
15717885 6287135269 8287785921
4213937 6485530719 5503580513
1457499 3022706853 5406935569
342241 6626619517 7572442209
291367 1609851628 1006057857
624 1879936324 0263088993
79 4609155430 2297799437
18 5094721880 5806795169
5880441281 7082895689
1426913425 7278382857
447006930 5765790361
338691761 9027650753
103829336 5596970297
26244136 4962025009
13919104 6715225521
9495351 6194528377
8665987 3956887089
2690215 6179261793
1380723 4637603551
84861 6055417241
75742 5533294977
15798 4711225111
12566 8496531953
5890 6621829089
2876 6041594049
1887 9015669049
768 2807816113
469 7933078977
9 8893390861
6 0715332481
3 7476830197
1 5165893657
1 1684067553
3452709217
1625005141
1046651149
499671457
488196073
370019827
169289641
127447937
94552033
74919121
10571017
2489521
2309077
989249
688591
323137
198397
98143
91513
88903
82963
69697
60589
37441
25741
20593
11617
9277
8713
7937
6337
6113
3967
3889
3697
3673
3457
3301
3169
3037
2593
2377
2113
2081
1801
661
463
449
397
353
307
241
199
181
127
109
97
89
73
67
41
37
232
19
17
13
7
5
3
23

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

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 = 2491 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 ≡ 35 (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:

realprecision = 3756 significant digits (3750 digits displayed)

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

Input file is:  IO\03780C61.cin
Certificate file is:  IO\03780C61.chg
Found values of n, F and G.
    Number to be tested has 9341 digits.
    Modulus has 2560 digits.
Modulus is 27.39750245% 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 1664 digits.
        Done!  Time elapsed:  568609ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1646 digits.
        Done!  Time elapsed:  615922ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1624 digits.
        Done!  Time elapsed:  686469ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1597 digits.
        Done!  Time elapsed:  2745328ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1562 digits.
        Done!  Time elapsed:  390750ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1527 digits.
        Done!  Time elapsed:  1770188ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1492 digits.
        Done!  Time elapsed:  1619406ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1454 digits.
        Done!  Time elapsed:  1460203ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1412 digits.
        Done!  Time elapsed:  463109ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1399 digits.
        Done!  Time elapsed:  510454ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1382 digits.
        Done!  Time elapsed:  536953ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1359 digits.
        Done!  Time elapsed:  511672ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1329 digits.
        Done!  Time elapsed:  580140ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1289 digits.
        Done!  Time elapsed:  689688ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1235 digits.
        Done!  Time elapsed:  773156ms.
    Running CHG with h = 8, u = 3. Right endpoint has 1163 digits.
        Done!  Time elapsed:  1016859ms.
    Running CHG with h = 8, u = 3. Right endpoint has 1133 digits.
        Done!  Time elapsed:  256500ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1098 digits.
        Done!  Time elapsed:  47063ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1086 digits.
        Done!  Time elapsed:  47297ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1071 digits.
        Done!  Time elapsed:  47109ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1049 digits.
        Done!  Time elapsed:  49859ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1015 digits.
        Done!  Time elapsed:  52563ms.
    Running CHG with h = 7, u = 2. Right endpoint has 965 digits.
        Done!  Time elapsed:  71422ms.
    Running CHG with h = 7, u = 2. Right endpoint has 890 digits.
        Done!  Time elapsed:  88812ms.
    Running CHG with h = 7, u = 2. Right endpoint has 778 digits.
        Done!  Time elapsed:  180688ms.
    Running CHG with h = 5, u = 1. Right endpoint has 609 digits.
        Done!  Time elapsed:  13547ms.
    Running CHG with h = 5, u = 1. Right endpoint has 364 digits.
        Done!  Time elapsed:  14593ms.
    Running CHG with h = 5, u = 1. Right endpoint has 38 digits.
        Done!  Time elapsed:  28657ms.
A certificate has been saved to the file:  IO\03780C61.chg

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

Testing a PRP called "IO\03780C61.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.099445990 E-617 at X, ratio=2.764000310 E-654 at Y, witness=2.
Pol[2, 1] with [h, u]=[5, 1] has ratio=0.3423552316 at X, ratio=1.559774878 E-327 at Y, witness=11.
Pol[3, 1] with [h, u]=[4, 1] has ratio=7.23201853 E-163 at X, ratio=3.499982232 E-245 at Y, witness=23.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.720013946 at X, ratio=2.087804490 E-338 at Y, witness=2.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.1303029493 at X, ratio=1.043365861 E-225 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.4043280429 at X, ratio=8.76441840 E-151 at Y, witness=5.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.532851911 at X, ratio=9.86095518 E-101 at Y, witness=2.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.03477996726 at X, ratio=2.007112121 E-67 at Y, witness=7.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.01343270402 at X, ratio=3.458004739 E-45 at Y, witness=2.
Pol[10, 1] with [h, u]=[7, 2] has ratio=0.02638871031 at X, ratio=2.469239659 E-30 at Y, witness=2.
Pol[11, 1] with [h, u]=[6, 2] has ratio=0.852600020 at X, ratio=5.088519794 E-26 at Y, witness=7.
Pol[12, 1] with [h, u]=[8, 3] has ratio=0.1994032589 at X, ratio=1.042609690 E-105 at Y, witness=11.
Pol[13, 1] with [h, u]=[8, 3] has ratio=0.2177541380 at X, ratio=1.092217582 E-90 at Y, witness=2.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.2690439512 at X, ratio=5.492670228 E-216 at Y, witness=7.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.3255744941 at X, ratio=3.703181516 E-162 at Y, witness=31.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.2098405306 at X, ratio=8.51880969 E-122 at Y, witness=7.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.2636903566 at X, ratio=1.558730614 E-91 at Y, witness=5.
Pol[18, 1] with [h, u]=[9, 3] has ratio=0.4102780952 at X, ratio=7.86764496 E-69 at Y, witness=5.
Pol[19, 1] with [h, u]=[9, 3] has ratio=0.01863943379 at X, ratio=8.72745822 E-52 at Y, witness=7.
Pol[20, 1] with [h, u]=[9, 3] has ratio=0.4050276113 at X, ratio=4.851850016 E-39 at Y, witness=11.
Pol[21, 1] with [h, u]=[10, 4] has ratio=0.1288986554 at X, ratio=2.940292488 E-169 at Y, witness=11.
Pol[22, 1] with [h, u]=[10, 4] has ratio=0.1689436879 at X, ratio=1.694519432 E-150 at Y, witness=3.
Pol[23, 1] with [h, u]=[10, 4] has ratio=0.531096073 at X, ratio=1.117965838 E-142 at Y, witness=2.
Pol[24, 1] with [h, u]=[10, 4] has ratio=0.4384118710 at X, ratio=1.403662457 E-142 at Y, witness=7.
Pol[25, 1] with [h, u]=[10, 4] has ratio=7.88583626 E-37 at X, ratio=1.824509074 E-138 at Y, witness=3.
Pol[26, 1] with [h, u]=[10, 4] has ratio=1.336066572 E-28 at X, ratio=6.210408088 E-111 at Y, witness=3.
Pol[27, 1] with [h, u]=[10, 4] has ratio=2.973710369 E-24 at X, ratio=7.30773740 E-89 at Y, witness=2.
Pol[28, 1] with [h, u]=[10, 4] has ratio=1.805751901 E-20 at X, ratio=2.949870992 E-71 at Y, witness=2.

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.