Primality Certificate for (7007^2017-1)/7006

Andy Steward7,753 digits30 May 2009
Originally by A.A.D.Steward 2009

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

From Factorisation
70077 · 7 · 11 · 13
Φ22 · 2 · 2 · 2 · 2 · 3 · 73
Φ379 · 621583
Φ42 · 5 · 5 · 981961
Φ63 · 409 · 40009
Φ743 · 1583 · 1739022972336101453
Φ82 · 433 · 953 · 2920906649
Φ9127 · 379 · 919 · 47616733 · 56192023
Φ1237 · 10369 · 6283329901
Φ14118339772296781721627943
Φ162 · 17 · 89329 · 266369 · 7182933907122212353
Φ183 · 19 · 991 · 20521 · 95239 · 1072089019
Φ2137633 · p42
Φ2422153 · 262315765163215485473666617
Φ2829 · 17921 · 39089 · p36
Φ322 · 257 · 11393 · 83668129 · 53830398418582657 · p31
Φ36p47
Φ421225099 · 733454688220335019 · 15592038960591353285929
Φ48193 · 54049 · 11106804812641 · p42
Φ5698057 · 4776099219790193 · p72
Φ63757 · 180307 · 123263355601 · p120
Φ7229077849 · 32504350645491544400151313 · p60
Φ846965328587755777 · 52109940247136437 · p60
Φ9697 · 10617498172025974895430297121 · 4712703529855297438561028871369775139769904897 · p48
Φ1125643268194929 · 143493365894507526696617462113 · c143
Φ1261250551 · 7896043 · 20903488327 · p116
Φ144c185
Φ168510553 · 1963396849 · 833743345618028737041573084553670689 · p134
Φ224673 · c367
Φ2521191715561 · c268
Φ28888993 · c365
Φ336337 · 10753 · 108193 · 24373610496817 · 23456417608242287089 · 225145024444482797011057 · 21632589390626756424936458497 · c274
Φ5041009 · 44185994497 · 20226656412792990559782107929 · p512
Φ6722017 · 252001 · c730
Φ1008c1108
Φ201626209 · 7322113 · 2924565644599201 · c2189

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

63 3176840557 6931905763 3553387879 1050168103 0758686366 5656233548 7820257619 1651737504 4523698426 7954325951 6039987623 1044381324 5799280431 9909391464 8115508868 2179314602 7304969535 4690034292 5111008496 8457632305 5117357786 5343468613 0860598146 3218951426 3599689891 5304992162 6356402923 8067033732 7554773883 8804475429 3280085319 4184662859 7273185987 0485661263 5079816234 7491649319 9791702952 2181853215 4056694561 4873231172 9816326565 7215917514 9235484762 7958407848 4700775302 6559654590 2643616443 9425676503 9659989945 4884984002 2986887353
4607 4468801952 8231532573 0604245368 0607641726 3059450736 2033883038 7338721193 5697780876 1997454785 4158547020 1958617497 5881106621 3329975897
1633855996 4963952234 8488435092 6843781494 6164592717 2110207611 3354065637 8621824191 3388921224 0252979608 5817047238 1326001951
133176 1792156646 4975234540 0586627239 9656498880 6689647709 7440226206 6919042108 1375598360 5477724690 7598923721 1116397059
41 9004683486 8038606942 3179694812 3251065064 0225678299 1965218505 3529504201
5406405852 1488723449 2935343247 7932312072 5772480380 9061726749
2076189778 2443532383 6280490411 0940456644 3054242257 2694989273
23494364 9683755155 7375913966 3876656523 6044974209
1400829 9224312862 4842766013 1369228053 9112687553
471270 3529855297 4385610288 7136977513 9769904897
37 2181331223 5675792236 6045575069 0888361153
29 1460541838 3609243467 7091001927 7809998273
833743 3456180287 3704157308 4553670689
689557 6853229092 2576886230 8994042757
1 2803391102 3154043024 0845202017
1434933658 9450752669 6617462113
216325893 9062675642 4936458497
202266564 1279299055 9782107929
106174981 7202597489 5430297121
2623157 6516321548 5473666617
325043 5064549154 4400151313
2251 4502444448 2797011057
1183 3977229678 1721627943
155 9203896059 1353285929
2345641760 8242287089
718293390 7122212353
173902297 2336101453
73345468 8220335019
5383039 8418582657
5210994 0247136437
696532 8587755777
477609 9219790193
292456 5644599201
2437 3610496817
1110 6804812641
564 3268194929
12 3263355601
4 4185994497
2 0903488327
6283329901
2920906649
1963396849
1191715561
1072089019
83668129
56192023
47616733
29077849
7896043
7322113
1250551
1225099
981961
621583
510553
266369
252001
180307
108193
98057
95239
89329
88993
54049
40009
39089
37633
26209
22153
20521
17921
11393
10753
10369
2017
1583
1009
991
953
919
757
673
433
409
379
337
257
193
127
97
79
73
43
37
29
19
17
13
11
72
52
33
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) = 27.454086%

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 = 41 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 ≡ 44 (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 = 3005 significant digits (3000 digits displayed)

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

Input file is:  IO\1B5F07E1.cin
Certificate file is:  IO\1B5F07E1.chg
Found values of n, F and G.
    Number to be tested has 7753 digits.
    Modulus has 2129 digits.
Modulus is 27.45408633% 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 1368 digits.
        Done!  Time elapsed:  879328ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1347 digits.
        Done!  Time elapsed:  812438ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1320 digits.
        Done!  Time elapsed:  891375ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1287 digits.
        Done!  Time elapsed:  1524406ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1253 digits.
        Done!  Time elapsed:  1688344ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1219 digits.
        Done!  Time elapsed:  1841219ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1181 digits.
        Done!  Time elapsed:  91890ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1167 digits.
        Done!  Time elapsed:  114719ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1150 digits.
        Done!  Time elapsed:  223766ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1128 digits.
        Done!  Time elapsed:  411390ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1098 digits.
        Done!  Time elapsed:  497985ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1059 digits.
        Done!  Time elapsed:  936062ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1006 digits.
        Done!  Time elapsed:  455188ms.
    Running CHG with h = 8, u = 3. Right endpoint has 936 digits.
        Done!  Time elapsed:  376625ms.
    Running CHG with h = 7, u = 2. Right endpoint has 901 digits.
        Done!  Time elapsed:  29218ms.
    Running CHG with h = 7, u = 2. Right endpoint has 885 digits.
        Done!  Time elapsed:  29750ms.
    Running CHG with h = 7, u = 2. Right endpoint has 860 digits.
        Done!  Time elapsed:  33094ms.
    Running CHG with h = 7, u = 2. Right endpoint has 823 digits.
        Done!  Time elapsed:  36250ms.
    Running CHG with h = 7, u = 2. Right endpoint has 767 digits.
        Done!  Time elapsed:  60984ms.
    Running CHG with h = 7, u = 2. Right endpoint has 683 digits.
        Done!  Time elapsed:  78875ms.
    Running CHG with h = 5, u = 1. Right endpoint has 557 digits.
        Done!  Time elapsed:  7985ms.
    Running CHG with h = 5, u = 1. Right endpoint has 404 digits.
        Done!  Time elapsed:  7453ms.
    Running CHG with h = 5, u = 1. Right endpoint has 151 digits.
        Done!  Time elapsed:  12344ms.
A certificate has been saved to the file:  IO\1B5F07E1.chg

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

Testing a PRP called "IO\1B5F07E1.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.224157593 E-278 at X, ratio=3.416779236 E-428 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.1134023450 at X, ratio=3.771344745 E-254 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=4.484321768 E-154 at X, ratio=9.16069638 E-154 at Y, witness=13.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.0740669661 at X, ratio=3.310345020 E-252 at Y, witness=3.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.2784624156 at X, ratio=1.855222665 E-168 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.524412692 at X, ratio=1.492607414 E-112 at Y, witness=17.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.3492580862 at X, ratio=3.216829654 E-75 at Y, witness=5.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.1197278244 at X, ratio=2.300794046 E-50 at Y, witness=2.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.2366223845 at X, ratio=7.279192640 E-34 at Y, witness=7.
Pol[10, 1] with [h, u]=[8, 3] has ratio=0.001292139026 at X, ratio=1.690783447 E-103 at Y, witness=2.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.788885961 at X, ratio=9.85102639 E-212 at Y, witness=11.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.517603038 at X, ratio=5.58465586 E-159 at Y, witness=2.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.4056542591 at X, ratio=2.322051469 E-119 at Y, witness=7.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.1177666241 at X, ratio=8.79061365 E-90 at Y, witness=13.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.4217750335 at X, ratio=1.607561925 E-67 at Y, witness=2.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.0921597542 at X, ratio=7.67091923 E-51 at Y, witness=3.
Pol[17, 1] with [h, u]=[8, 3] has ratio=0.1790313905 at X, ratio=1.268980870 E-44 at Y, witness=2.
Pol[18, 1] with [h, u]=[10, 4] has ratio=0.1785625240 at X, ratio=7.133034152 E-152 at Y, witness=5.
Pol[19, 1] with [h, u]=[10, 4] has ratio=0.1484061622 at X, ratio=2.383131762 E-136 at Y, witness=7.
Pol[20, 1] with [h, u]=[10, 4] has ratio=0.4346848510 at X, ratio=2.389549692 E-136 at Y, witness=3.
Pol[21, 1] with [h, u]=[10, 4] has ratio=1.811304176 E-24 at X, ratio=8.41448754 E-134 at Y, witness=7.
Pol[22, 1] with [h, u]=[10, 4] has ratio=1.146759414 E-27 at X, ratio=3.949734059 E-107 at Y, witness=7.
Pol[23, 1] with [h, u]=[10, 4] has ratio=2.664128604 E-22 at X, ratio=8.17668201 E-86 at Y, witness=3.

Validated in 18 sec.


Congratulations! n is prime!

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