Primality Certificate for (15^8741-1)/14

Andy Steward10,280 digits31 December 2006
Originally by A.A.D.Steward 2006

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

From Factorisation
153 · 5
Φ22 · 2 · 2 · 2
Φ42 · 113
Φ511 · 4931
Φ1031 · 1531
Φ194272113 · 370649274902657
Φ2019421 · 131381
Φ23829 · 31741 · 3046462151831565769
Φ38229 · 13757 · 439799488353587
Φ4647 · 6257 · 81421 · 825287 · 3549551867
Φ7626297 · 18434831466377 · 4485532699379697977461729
Φ92277 · 2393 · 488153 · 132653513 · 40193672100977 · 3230238627505403797
Φ95191 · 65959677431 · p72
Φ1151151 · 53591 · 100511 · 2083752851 · 740265963181 · 4088280880261 · 42460920908092999453501 · p35
Φ190571 · 2851 · 1045074297886141 · 45186569761128841661272737901 · p35
Φ2309935311 · 12203077111 · 47259785976796262161 · 8264999210340600150541 · p45
Φ3806837459701 · c160
Φ43763057282689597576150473960079 · p437
Φ460461 · 11426885761 · 1698065217789065381 · p177
Φ8748715303383 · p456
Φ1748p932
Φ218521851 · 4416885731 · 17135664726911 · 8082126682134151981 · c1817
Φ43701311001 · 7092511 · 61877723905771 · 27739197968560223851 · c1817
Φ87408741 · 12594341 · 51391201 · 8388520901 · 18645680021 · c3687

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

29 2552014598 5514428232 1227250378 6249461233 0112526968 9204399517 5171367429 3359145739 1171158619 3121047319 4210585440 7434755577 8033670854 7965666292 0216753324 8735713834 4582896436 7209710180 3388142646 8120470185 9074626233 9222304359 3140883048 8936505447 8892828394 1066512732 5852887763 8760144837 2028621762 5817854728 4606577382 4381103299 7588240064 0575250713 8276817360 5066647014 4012301646 6891381587 7324751657 9924294758 3416867571 3712840321 9160607642 6146381086 8634869341 9833469668 2526934509 2012636263 5086254244 1365142009 3449134967 4398222527 3401158970 5625769735 3037499023 3115942904 2948637287 1620735656 7783571197 4052902640 3115755160 5234226661 0333828465 4242330478 9369879269 6543066145 7933238814 8122448920 8436425588 1164948020 6127520077 6263656497 9441196840 9510910533 3726638193 5845465200 1130478540 7777754585 9237184872 1471429379 7164232763 6623799234 9250960899 8359419418 3094414820 7146268893 4867890751 8499378909 3135712514 5501645803 4191600745 5438375473 0224609601
660518 2171357885 5155327948 9100604142 4739615436 1406159925 7979219554 2393401890 8203808390 3674517370 6011953380 5319101804 6333150924 2665285121 3451214050 1689932231 7702111103 8493955636 5279379152 7233872667 4605171284 5307393960 0821660836 9676815590 8162663229 5286872795 3055536640 1704361545 0401039352 2323446379 7139665905 8052498617 7682356693 1646702917 5520892738 8204334564 5141458907 7799345451 8436484941 5789444173 3271856286 5224541414 1208075778 3165435209 6860857596 5500717127
7988037 7903209786 8248182952 2306463998 0040320319 7519361244 4794725818 9842109235 1936403325 8224337147 0966288912 7963253711 4013658718 5260218801 9835394605 1511584851 7149649986 8304359564 5476655943 1697572183 6650762995 3303481281 4340189013 2109860660 3056789672 2107615691 8385584129 9519837328 1663756053 1697132094 4833282179 9389354522 6245650767 1311957309 8432754778 2251083089 9995734137 6004633321 4411514335 6149995851 5840582260 3883484063 5682737289 4826129359
1102565 3441978642 4664553419 8379554832 2267019042 9081286806 1900194191 7407449706 6539748023 6699739164 9750766456 1631338033 7427210552 1524721896 4114810696 5954227446 8537163656 9183256801
35 3424058867 1253965135 4272508135 7813010609 7292784712 6211140389 5782573241
70578 6845852111 5411084440 7456019509 6202278621
66192 5233114490 7459799154 5296985081
17616 6466586103 0448031363 5124812321
630572826 8959757615 0473960079
451865697 6112884166 1272737901
44855 3269937969 7977461729
424 6092090809 2999453501
82 6499921034 0600150541
4725978597 6796262161
2773919796 8560223851
808212668 2134151981
323023862 7505403797
304646215 1831565769
169806521 7789065381
104507 4297886141
43979 9488353587
37064 9274902657
6187 7723905771
4019 3672100977
1843 4831466377
1713 5664726911
408 8280880261
74 0265963181
6 5959677431
1 8645680021
1 2203077111
1 1426885761
8715303383
8388520901
6837459701
4416885731
3549551867
2083752851
132653513
51391201
12594341
9935311
7092511
4272113
1311001
825287
488153
131381
100511
81421
53591
31741
26297
21851
19421
13757
8741
6257
4931
2851
2393
1531
1151
829
571
461
277
229
191
113
47
31
11
5
3
25

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

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 = 1547 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 ≡ 61 (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 = 4007 significant digits (4000 digits displayed)

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

Input file is:  IO\000F2225.cin
Certificate file is:  IO\000F2225.chg
Found values of n, F and G.
    Number to be tested has 10280 digits.
    Modulus has 2800 digits.
Modulus is 27.23111882% 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 1883 digits.
        Done!  Time elapsed:  8516234ms.
    Running CHG with h = 12, u = 5. Right endpoint has 1838 digits.
        Done!  Time elapsed:  4092219ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1791 digits.
        Done!  Time elapsed:  10550797ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1775 digits.
        Done!  Time elapsed:  11447390ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1755 digits.
        Done!  Time elapsed:  859016ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1731 digits.
        Done!  Time elapsed:  1047891ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1701 digits.
        Done!  Time elapsed:  2832671ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1663 digits.
        Done!  Time elapsed:  3690047ms.
    Running CHG with h = 10, u = 4. Right endpoint has 1616 digits.
        Done!  Time elapsed:  1726360ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1588 digits.
        Done!  Time elapsed:  3906125ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1523 digits.
        Done!  Time elapsed:  282859ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1515 digits.
        Done!  Time elapsed:  296797ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1505 digits.
        Done!  Time elapsed:  310953ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1492 digits.
        Done!  Time elapsed:  803922ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1475 digits.
        Done!  Time elapsed:  853328ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1452 digits.
        Done!  Time elapsed:  937703ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1421 digits.
        Done!  Time elapsed:  962797ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1379 digits.
        Done!  Time elapsed:  704688ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1324 digits.
        Done!  Time elapsed:  1026453ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1251 digits.
        Done!  Time elapsed:  1540312ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1153 digits.
        Done!  Time elapsed:  64391ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1133 digits.
        Done!  Time elapsed:  74344ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1102 digits.
        Done!  Time elapsed:  85859ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1057 digits.
        Done!  Time elapsed:  167641ms.
    Running CHG with h = 7, u = 2. Right endpoint has 989 digits.
        Done!  Time elapsed:  73828ms.
    Running CHG with h = 7, u = 2. Right endpoint has 887 digits.
        Done!  Time elapsed:  102250ms.
    Running CHG with h = 5, u = 1. Right endpoint has 733 digits.
        Done!  Time elapsed:  23468ms.
    Running CHG with h = 5, u = 1. Right endpoint has 534 digits.
        Done!  Time elapsed:  14250ms.
    Running CHG with h = 5, u = 1. Right endpoint has 228 digits.
        Done!  Time elapsed:  34219ms.
A certificate has been saved to the file:  IO\000F2225.chg

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

Testing a PRP called "IO\000F2225.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.809742625 E-289 at X, ratio=1.088839380 E-516 at Y, witness=13.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.702438733 at X, ratio=1.855623679 E-306 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=5.091719456 E-202 at X, ratio=1.506680020 E-200 at Y, witness=7.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.1864548083 at X, ratio=3.190002573 E-307 at Y, witness=13.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.05112014328 at X, ratio=6.399963016 E-205 at Y, witness=7.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.3378396602 at X, ratio=7.02190263 E-137 at Y, witness=3.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.2655382116 at X, ratio=1.816611082 E-91 at Y, witness=2.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.4463846594 at X, ratio=2.688572011 E-61 at Y, witness=17.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.681983999 at X, ratio=4.412205002 E-41 at Y, witness=2.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.03577279735 at X, ratio=1.171093567 E-294 at Y, witness=5.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.1431589244 at X, ratio=2.835117439 E-221 at Y, witness=5.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.0940859492 at X, ratio=4.480924420 E-166 at Y, witness=3.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.0783428205 at X, ratio=8.49627438 E-125 at Y, witness=5.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.3162639878 at X, ratio=9.38653345 E-94 at Y, witness=3.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.569700057 at X, ratio=1.399799410 E-70 at Y, witness=5.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.1646616046 at X, ratio=4.880520564 E-53 at Y, witness=5.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.4252164283 at X, ratio=6.444844690 E-40 at Y, witness=2.
Pol[18, 1] with [h, u]=[9, 3] has ratio=0.1294306442 at X, ratio=3.885945940 E-30 at Y, witness=3.
Pol[19, 1] with [h, u]=[9, 3] has ratio=0.0841562469 at X, ratio=8.56062877 E-23 at Y, witness=17.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.02804163077 at X, ratio=4.519004408 E-264 at Y, witness=2.
Pol[21, 1] with [h, u]=[10, 4] has ratio=0.1395380104 at X, ratio=4.938078076 E-110 at Y, witness=5.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.1498554816 at X, ratio=1.775289584 E-189 at Y, witness=5.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.737126932 at X, ratio=9.42349481 E-152 at Y, witness=31.
Pol[24, 1] with [h, u]=[11, 4] has ratio=0.2961958906 at X, ratio=1.382962947 E-121 at Y, witness=37.
Pol[25, 1] with [h, u]=[11, 4] has ratio=0.2599765471 at X, ratio=2.271624537 E-97 at Y, witness=3.
Pol[26, 1] with [h, u]=[10, 4] has ratio=4.650355158 E-22 at X, ratio=3.758331052 E-81 at Y, witness=3.
Pol[27, 1] with [h, u]=[10, 4] has ratio=3.979150838 E-17 at X, ratio=3.978278317 E-65 at Y, witness=13.
Pol[28, 1] with [h, u]=[12, 5] has ratio=0.02890959298 at X, ratio=3.140093925 E-233 at Y, witness=19.
Pol[29, 1] with [h, u]=[12, 5] has ratio=4.117039658 E-47 at X, ratio=2.159802765 E-224 at Y, witness=7.

Validated in 49 sec.


Congratulations! n is prime!

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