Primality Certificate for (4735^4621-1)/4734

Andy Steward16,980 digits15 February 2010
Originally by David Broadhurst & Bouk de Water 2005

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

From Factorisation
47355 · 947
Φ22 · 2 · 2 · 2 · 2 · 2 · 2 · 37
Φ33 · 13 · 709 · 811
Φ42 · 1549 · 7237
Φ511 · 491 · 571 · 163027691
Φ67 · 7 · 457459
Φ711272276413073374840961
Φ1031 · 1861 · 8711243551
Φ112663 · 2971 · 3499 · 115385792237 · 1773868681663739
Φ12162901 · 3085717501
Φ1411267516161209745881991
Φ15181 · 29311 · 47616659719574710778851
Φ2041 · 61 · 14401 · 259321 · 27053023984638581
Φ21193822483 · p36
Φ2223 · 67 · 2399 · 292667 · 5234816715483123445446947
Φ2829 · 1289 · 1877 · 817074359802737 · 2215455394630424674729
Φ308581 · 47431 · 590647531 · 1051291132321
Φ33390721 · p68
Φ3571 · 8191 · 91771 · 118996291 · p70
Φ427 · 43 · 5680921 · p35
Φ4489 · 353 · 70665629 · 38567022672741419389097069033 · p33
Φ5511 · 277531 · 1230571 · 215339300518724740447919418366324340421 · p97
Φ60185161 · 1702321 · 1096022332596084241 · p30
Φ6610429 · 355609 · 1973467 · 1455560875891 · p46
Φ70421 · 701 · 754181 · 57953872382118954151 · p58
Φ77p221
Φ84247717 · 758101 · 415074577 · p69
Φ105211 · 4831 · 2546096111030697488681948901231841 · p138
Φ11029874791 · c140
Φ132668601127207540603429 · c127
Φ140p177
Φ154463 · 20119793 · 53587843 · 83435495411294619517 · c183
Φ165661 · p292
Φ21051715682728128721 · 3136941368527054831 · 29703923203228360775011 · p119
Φ2201533849901 · p285
Φ2312013859 · 1880686728488569 · c420
Φ308c442
Φ330331 · 521401 · 22434619084351 · 14682720318987601 · 74262065683141155528135521491 · c228
Φ38536191 · 2700391 · 107803412457870361 · c855
Φ420115253538541 · c342
Φ462c442
Φ6602082961 · 27593281 · 579966009422092947694591981 · c548
Φ770574410063151 · 707561826058781 · 43540508036678023689438183102271 · c824
Φ92450821 · 2534188637469510968752596253 · c850
Φ11552311 · 109126711 · 1095482851 · 2674423291 · c1735
Φ15409241 · p1761
Φ2310242551 · 24635588671 · 11190954754981 · c1736
Φ46204621 · c3525

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

1 5412497290 1481516317 5331939467 4268997984 8363917040 0251510078 2321043698 6307277057 0357627706 9636152346 7114303043 1038212583 0216390164 2411626293 4490432120 5702378889 6292433549 5611633465 4969367590 8505237900 4164309532 1430798376 9218205752 9874717295 1234932129 8472748870 9986608300 0645342629 9468533114 0305771398 7772813390 8303480994 4381331894 7760180693 0846126472 3212362865 5224557227 4548595592 7865272955 8133926186 4114188272 1718002878 9820043733 8506718707 9170467160 9018195398 7597423224 8112673439 6558412887 5222566357 3082547915 5223407203 6294179170 2163883231 9894644964 5449712699 9140821669 4741238253 1457588965 3595400123 7370520958 4988923353 2511676093 3359020545 4176028183 7404737166 3788720777 1427344014 9267233278 4321679028 4788300686 8235180251 5926652265 6034446407 5361511392 8162685316 4770732110 1150556375 8911184840 6517399449 5144352668 7943090153 4708446095 9805498620 3153161152 7656282139 2562414850 9100600798 8299054131 8329639051 9564247799 8454513888 7462170389 1788401941 1118357952 0761890857 4838451943 5497928566 9841350125 9471079337 2369541033 7455976018 9460400682 5418003445 1892672503 5455607415 2191798092 9321809919 1476610342 5319332030 1045694448 3821822669 4927521986 0905577556 9684910653 9652338356 5789991882 5566253695 0522131889 8271503894 4056342859 7319753157 1105455389 8166519049 0087835330 0702702906 1974985819 0836111944 1547169237 3690927414 1568339522 5200727421 4272565214 7727948543 1160550477 3826810537 7593908479 1386684345 5499779670 8214614667 4483783373 0814918102 9507523041 8735714596 3205538804 8170757213 1241605079 5952315175 1154645075 7375881553 4364752585 4651037219 1460009061 1527634995 7577564183 0101539274 8225984457 2011311098 0450390875 6347620377 1498404523 9297367200 8785077935 8739865676 0040956634 6466165229 4941266478 4221210840 9574690592 4464819585 7856745198 5980866929 5866617963 3223832545 9298500572 1710878761
16 0505137277 9657571876 3090240344 0536048411 3978248772 0841064096 9289170680 5086978753 7465159726 3904087373 6614824492 4664090992 4697526941 4836465084 7248128692 2441905804 4824229990 1799438369 8612510986 8523561392 3661053526 1778604638 4934325061 1024476835 0674617876 5607716674 9827634789 2934690525 4415066301
69153 7640611803 2284622129 3498704141 9107881711 6774363784 3832482205 1887628046 8004914266 5736722407 2613922062 9762181497 3853458723 6658877661 1684978092 1921090424 2166081573 9794255882 7157653788 0797495939 1754875279 0645040960 9180539608 8709731728 8317968135 6934143550 0647913788 7305523508 9995649701
3 3045115229 6375219655 3497772091 1514205207 3478411385 3324565152 2616789985 5532880037 6223558337 8827975073 7314369692 4466013433 2168319537 5164917479 1306974631 0635484941 2571642321 0824827452 2605288095 4560724304 8829546698 5897104641
2602311 1327898360 6080494474 2486665422 2238347814 3651128441 7805519081 1992523236 8684106103 8394014142 9165672412 0148703501 3995415290 7316536966 7220876085 7519059343 3729151588 4309529601
10028977 1934456899 7495049416 1687424689 0778054505 4595061501 0575220327 7364366725 1093865027 4898828509 5261150772 0471541069 2921176596 1826479781
539914526 7091187757 9736568636 7268243222 2410855676 6574196366 5991311065 3066482341 8985889204 5683031868 5176225450 3269661781
1272838 9128625207 0714502936 2468124648 9155061236 2458748711 2439360318 9734794937 3713149678 6986010511
2539532099 0994962963 2139498549 9510090028 6235231223 8764325055 0480725721
206952465 2772424569 8591712717 7884781813 4871674638 5585988066 8807347689
82118533 1717191988 2776266941 2759152640 4088035989 8155657370 3524835521
12508728 0162497310 9041986036 5211392692 3359533269 4103314811
301311 5111841670 8497064336 8750546820 3190452733
215339300 5187247404 4791941836 6324340421
655154 7852377660 8645477597 1023859227
74292 7210117269 2534511795 6205727341
2546 0961110306 9748868194 8901231841
374 8095027235 4931136621 5457955029
43 5405080366 7802368943 8183102271
1848031523 3949205635 7913357881
742620656 8314115552 8135521491
385670226 7274141938 9097069033
25341886 3746951096 8752596253
5799660 0942209294 7694591981
52348 1671548312 3445446947
476 1665971957 4710778851
297 0392320322 8360775011
112 7227641307 3374840961
112 6751616120 9745881991
22 1545539463 0424674729
6 6860112720 7540603429
8343549541 1294619517
5795387238 2118954151
313694136 8527054831
109602233 2596084241
10780341 2457870361
5171568 2728128721
2705302 3984638581
1468272 0318987601
188068 6728488569
177386 8681663739
81707 4359802737
70756 1826058781
2243 4619084351
1119 0954754981
145 5560875891
105 1291132321
57 4410063151
11 5385792237
11 5253538541
2 4635588671
8711243551
3085717501
2674423291
1533849901
1095482851
590647531
415074577
193822483
163027691
118996291
109126711
70665629
53587843
29874791
27593281
20119793
5680921
2700391
2082961
2013859
1973467
1702321
1230571
758101
754181
521401
457459
390721
355609
292667
277531
259321
247717
242551
185161
162901
91771
50821
47431
36191
29311
14401
10429
9241
8581
8191
7237
4831
4621
3499
2971
2663
2399
2311
1877
1861
1549
1289
947
811
709
701
661
571
491
463
421
353
331
211
181
89
71
67
61
43
41
37
31
29
23
13
112
73
5
3
28

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

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 = 799 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 ≡ 47 (mod 65) 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 = 6752 significant digits (6750 digits displayed)

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

Input file is:  IO\127F120D.cin
Certificate file is:  IO\127F120D.chg
Found values of n, F and G.
    Number to be tested has 16980 digits.
    Modulus has 4592 digits.
Modulus is 27.03780522% 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 3208 digits.
        Done!  Time elapsed:  11831297ms.
    Running CHG with h = 12, u = 5. Right endpoint has 3180 digits.
        Done!  Time elapsed:  4779281ms.
    Running CHG with h = 12, u = 5. Right endpoint has 3147 digits.
        Done!  Time elapsed:  11277406ms.
    Running CHG with h = 12, u = 5. Right endpoint has 3108 digits.
        Done!  Time elapsed:  5128063ms.
    Running CHG with h = 12, u = 5. Right endpoint has 3064 digits.
        Done!  Time elapsed:  10675890ms.
    Running CHG with h = 12, u = 5. Right endpoint has 3021 digits.
        Done!  Time elapsed:  43110469ms.
    Running CHG with h = 12, u = 5. Right endpoint has 2977 digits.
        Done!  Time elapsed:  50760469ms.
    Running CHG with h = 12, u = 5. Right endpoint has 2929 digits.
        Done!  Time elapsed:  22893250ms.
    Running CHG with h = 12, u = 5. Right endpoint has 2876 digits.
        Done!  Time elapsed:  20936203ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2817 digits.
        Done!  Time elapsed:  3854875ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2790 digits.
        Done!  Time elapsed:  3677734ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2755 digits.
        Done!  Time elapsed:  3344844ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2712 digits.
        Done!  Time elapsed:  3206609ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2658 digits.
        Done!  Time elapsed:  3345000ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2590 digits.
        Done!  Time elapsed:  31243157ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2506 digits.
        Done!  Time elapsed:  36046515ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2401 digits.
        Done!  Time elapsed:  1709703ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2383 digits.
        Done!  Time elapsed:  1921344ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2360 digits.
        Done!  Time elapsed:  1974438ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2329 digits.
        Done!  Time elapsed:  2145875ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2287 digits.
        Done!  Time elapsed:  2145984ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2232 digits.
        Done!  Time elapsed:  2089688ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2158 digits.
        Done!  Time elapsed:  1556468ms.
    Running CHG with h = 9, u = 3. Right endpoint has 2060 digits.
        Done!  Time elapsed:  3269047ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1929 digits.
        Done!  Time elapsed:  4504281ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1754 digits.
        Done!  Time elapsed:  252188ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1678 digits.
        Done!  Time elapsed:  211172ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1565 digits.
        Done!  Time elapsed:  330765ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1395 digits.
        Done!  Time elapsed:  373735ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1139 digits.
        Done!  Time elapsed:  39297ms.
    Running CHG with h = 5, u = 1. Right endpoint has 748 digits.
        Done!  Time elapsed:  45093ms.
    Running CHG with h = 5, u = 1. Right endpoint has 287 digits.
        Done!  Time elapsed:  75891ms.
A certificate has been saved to the file:  IO\127F120D.chg

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

Testing a PRP called "IO\127F120D.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.367905562 E-623 at X, ratio=4.056554250 E-909 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.4305350974 at X, ratio=7.00609322 E-462 at Y, witness=5.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.764559466 E-211 at X, ratio=4.484432620 E-392 at Y, witness=2.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.646066583 at X, ratio=4.193865116 E-511 at Y, witness=5.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.1904607790 at X, ratio=5.110106414 E-341 at Y, witness=13.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.2479577533 at X, ratio=1.404826544 E-227 at Y, witness=5.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.0791710590 at X, ratio=5.670537232 E-152 at Y, witness=2.
Pol[8, 1] with [h, u]=[9, 3] has ratio=0.01283375459 at X, ratio=3.614125809 E-525 at Y, witness=17.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.3523190722 at X, ratio=4.417854856 E-394 at Y, witness=5.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.02721108720 at X, ratio=1.175213092 E-295 at Y, witness=3.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.2774243844 at X, ratio=5.99343197 E-222 at Y, witness=3.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.2079683201 at X, ratio=1.128564522 E-166 at Y, witness=17.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.1645522227 at X, ratio=3.819367379 E-125 at Y, witness=2.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.3162319605 at X, ratio=4.383176556 E-94 at Y, witness=7.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.711000132 at X, ratio=9.98337125 E-71 at Y, witness=17.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.2346819851 at X, ratio=2.876743667 E-53 at Y, witness=5.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.526643300 at X, ratio=1.959167806 E-422 at Y, witness=3.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.515740825 at X, ratio=4.449250234 E-338 at Y, witness=7.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.4813454472 at X, ratio=1.459856107 E-270 at Y, witness=2.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.1203475884 at X, ratio=1.284467601 E-216 at Y, witness=2.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.1357481581 at X, ratio=2.261745711 E-173 at Y, witness=7.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.3658195945 at X, ratio=6.548053156 E-139 at Y, witness=7.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.3694456041 at X, ratio=3.060286114 E-111 at Y, witness=5.
Pol[24, 1] with [h, u]=[12, 5] has ratio=0.2089960373 at X, ratio=8.77518127 E-293 at Y, witness=2.
Pol[25, 1] with [h, u]=[12, 5] has ratio=0.3872241272 at X, ratio=3.166829669 E-266 at Y, witness=3.
Pol[26, 1] with [h, u]=[12, 5] has ratio=0.1828297763 at X, ratio=3.891631799 E-242 at Y, witness=7.
Pol[27, 1] with [h, u]=[12, 5] has ratio=0.4490669760 at X, ratio=3.645852766 E-220 at Y, witness=5.
Pol[28, 1] with [h, u]=[12, 5] has ratio=0.01216679735 at X, ratio=4.260223118 E-218 at Y, witness=3.
Pol[29, 1] with [h, u]=[12, 5] has ratio=0.4839578300 at X, ratio=3.567875134 E-218 at Y, witness=3.
Pol[30, 1] with [h, u]=[12, 5] has ratio=5.11915358 E-41 at X, ratio=2.057602736 E-198 at Y, witness=5.
Pol[31, 1] with [h, u]=[12, 5] has ratio=1.416772167 E-34 at X, ratio=1.621565888 E-165 at Y, witness=5.
Pol[32, 1] with [h, u]=[12, 5] has ratio=1.367393791 E-28 at X, ratio=5.75363951 E-138 at Y, witness=11.

Validated in 173 sec.


Congratulations! n is prime!

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