Primality Proof of (452916381-1)/4528

OpenPFGW

Primality testing (4529^16381-1)/4528 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N-1 test using base 23
Calling Brillhart-Lehmer-Selfridge with factored part 28.69%
(4529^16381-1)/4528 is PRP! (623.4033s+0.0005s)

CHG

   realprecision = 21019 significant digits (21000 digits displayed)

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

Input file is:  4529_16381.in
Certificate file is:  4529_16381.out
Found values of n, F and G.
    Number to be tested has 59886 digits.
    Modulus has 17179 digits.
Modulus is 28.685595588619700532% 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 = 6, u = 2. Right endpoint has 8351 digits.
        Done!  Time elapsed:  210890ms.
    Running CHG with h = 6, u = 2. Right endpoint has 8207 digits.
        Done!  Time elapsed:  123230ms.
    Running CHG with h = 6, u = 2. Right endpoint has 7992 digits.
        Done!  Time elapsed:  128740ms.
    Running CHG with h = 6, u = 2. Right endpoint has 7670 digits.
        Done!  Time elapsed:  133820ms.
    Running CHG with h = 6, u = 2. Right endpoint has 7186 digits.
        Done!  Time elapsed:  136130ms.
    Running CHG with h = 6, u = 2. Right endpoint has 6460 digits.
        Done!  Time elapsed:  157590ms.
    Running CHG with h = 6, u = 2. Right endpoint has 5530 digits.
        Done!  Time elapsed:  159940ms.
    Running CHG with h = 5, u = 1. Right endpoint has 4599 digits.
        Done!  Time elapsed:  10370ms.
    Running CHG with h = 5, u = 1. Right endpoint has 3472 digits.
        Done!  Time elapsed:  104630ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1218 digits.
        Done!  Time elapsed:  101610ms.
A certificate has been saved to the file:  4529_16381.out

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

Testing a PRP called "4529_16381.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=5.835561420380681906 E-2768 at X, ratio=7.241302067588751576 E-3985 at Y, witness=23.
Pol[2, 1] with [h, u]=[4, 1] has ratio=4.821602307928439311 E-2066 at X, ratio=3.855075330651802960 E-2255 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=2.501770264115215259 E-1128 at X, ratio=4.517070961623805674 E-1128 at Y, witness=2.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.4680526216804052198 at X, ratio=7.903788472550114062 E-1862 at Y, witness=7.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.5978687966999096481 at X, ratio=8.297044818334960063 E-1862 at Y, witness=2.
Pol[6, 1] with [h, u]=[6, 2] has ratio=6.266427608611931538 E-727 at X, ratio=2.4854163998922874054 E-1452 at Y, witness=2.
Pol[7, 1] with [h, u]=[6, 2] has ratio=5.971454124140086931 E-485 at X, ratio=4.649925520843198637 E-968 at Y, witness=5.
Pol[8, 1] with [h, u]=[6, 2] has ratio=2.193089460702948020 E-323 at X, ratio=7.474844578358508682 E-646 at Y, witness=23.
Pol[9, 1] with [h, u]=[6, 2] has ratio=8.595018609452281570 E-217 at X, ratio=1.2721507824509890089 E-430 at Y, witness=11.
Pol[10, 1] with [h, u]=[6, 2] has ratio=3.105317986787952453 E-144 at X, ratio=2.5795301518409557634 E-287 at Y, witness=2.

Validated in 1 sec.


Congratulations! n is prime!
Goodbye!
A copy of the CHG certificate 4529_16381.out (1476KB) is included in: 4529_16381.zip.

Helper File

Based on factorization of N-1 and N+1: 
Phi(4095,4529)/(64275824341*10944444434398412506644888541)
Phi(819,4529)/(6553*608486868991*5441286769395751*9808142052154447*1437449670642861849788041501)
Phi(1092,4529)/1093
Phi(585,4529)/182496571683661
Phi(1170,4529)/(3511*8191*55721774127241)
Phi(315,4529)/(26002929331*5762857372083333806131*1457160406191430676298991)
Phi(630,4529)/(631*524279071*366331037311*982257493771*150122172578491*49132999015254001*750645023170321790411858087273626456891)
9756042338916964996740839619821506649309678170285685724886909346533218933889448017014416923544757269132125148322360149081164114521934155206008389275143454520844671357285637957737245147383399210635547715799483335285710043352328928497015430519695341375748027011567760349580926507397556540329421
2088398033911541051860996269088842675499950460431661245366214173270018616120950523020380918976319509387103726402142561796952203525265307407411478158615892536390755353594132638590738276569733366693700773384912614878414930290773511878952484458274549327
12803131034785975779975666744036930301307267799266791678544258300287262091351903204101957834207626226202806803214747739299049458192591428233814369083788985687975053489360778079823490083847525877825791871393639076605323098376800377600246051
28254388915781963980845379957197219139240834983406126011256649415736766062027600632949545140215421881964186699372257793408435347870823313888814836630568875813252846050373227246918794057398287756215727413
4719994413667171922140679404773525370329231963976779312765266248385885636706243978493904670359515074757051542349561229115478065465280813132814616199393300312026472741501886669515467883
3252968243820015284052414722846483620294518255149830911373444320442337812321432929133356152212564762557603251618789675955967168543
7602148577059174205422801770590258426088742400921328949752633501660911035806980696767099495587635875288970957336675158561
2784360489158985090410662735966558393573530287100206680107842400316425148931580897653167044488928696014009321699513665861
1837759490394997430671688873765374279491638633181196400666809170376950950023133676895674161779542258771801157846925998031
24375430866522021312076926643464387296375227025565254961778373855472585480357917487547237
5545743691988902284409468210462000493156863258151146436781773086506819374239970750936641
1533500067344173011289863429895278276362057372666474090726479825511756854213567539671711
30646234578812382069943914801453133894071300773099158500090577705580710492497446320861
7562133711205591991604898304683477184190115683130379858675150196967555942281523813
1981761488757769187056956943052978417477467769913056241217233918738663571
1639065247986723412500751086137066279386346203525332775185631
135447936383446437957584392475557527562786352307396691209341
54680267535446412836621019034473063478227504057169
61654843499604710968546960635047704548589733701
1471917771732616695244496742504102595339152409
1452081825227958268212879453211226658932808077
507838641576597291303491936074751722404771451
129153086480578996464517423774820318430155131
42948787441326299624087036396686849633361011
8388904925331396132774295885798622322878051
6145860615990351398523943671828385596143971
1975068384199578420559737362354812653491281
1166231010379914551563104846565357410214141
4890132587312991988071027003886406348341
2604038654726867517332869660338823698523
1001439361544421234584815590171379132981
750645023170321790411858087273626456891
425162110070761387748380395403735800901
363846083010149498451288962422522908961
126826444141744827139390098430305485971
58976188260247563588891516042243721
17014195168885018982098692022019729
9892529450835975197663521515837241
7449647003318685448378264104821341
346625559075382315822190551394221
10537498219886108354350612398371
882900810025372828064049167221
322046251928231158810916706637
182799796708565250299524747309
157656546060885461896911881641
98137730059260614821210228057
88992193271347020061130724001
50818741210094353190880859571
27269553146735322227374093681
21271536946001583643874039881
10944444434398412506644888541
8039266302059995989917229781
1986961432255850024317355741
1711603742775929604858045301
1437449670642861849788041501
29353876491328557788210501
21134842524905326893517843
13330636886550288708820171
11201135868609273970224661
9418195256841844821870341
5302134321281060128698421
1457160406191430676298991
110191301910214776257833
87911340493240766782141
32445721025550564573661
12229087537207645217023
10301670856422218005321
9383370479814623705869
8715340532441925516331
7017482709408448808441
5762857372083333806131
7229698015367040120601
773098761952623160801
509952994947189326737
297522657734320219013
141602015965609122589
133521641543867537941
35605578584137236949
32255213044404636751
2173155163293376081
1675134503733358487
837237376380975571
479598189308309527
378720903945540781
377049321529459801
293794915548828961
142040277103677041
76963727311195999
49132999015254001
47075430364091351
41130782119878361
23439669314160997
9808142052154447
9367693448529391
5441286769395751
5091097313073253
2739668354959447
685500331341281
182496571683661
174836243247797
150122172578491
120346855361461
119437413499301
95748311240401
94425524085439
55721774127241
39811285217761
38465016220723
24775072098661
17675104766281
8902833388541
5763501379417
1529879199841
1359469050661
1246255343441
982257493771
608486868991
412217476441
366331037311
323654107141
143900707861
69790597813
64275824341
59268216589
57715263061
31999736891
26002929331
20476622671
15576476341
6342694261
5935455553
5000790133
2869135361
1573777141
1093520017
985216051
770921971
755525233
729254179
524279071
492690901
418922323
185507713
119975311
52433401
52211251
30921661
29392273
22870121
13648181
6366751
5926381
5431861
5378101
3716831
2796223
2702701
1976983
1930261
1901719
1178269
1079809
1050013
999181
718901
672127
668851
637841
446041
443041
378691
343141
128221
90847
68041
63793
52937
28211
24571
18757
16381
15787
13151
9283
8191
6553
5981
5431
5281
5153
4421
3511
2731
2341
2269
2029
1471
1381
1171
1093
937
911
701
691
647
631
547
541
521
491
433
421
337
313
281
211
181
157
151
131
127
79
73
71
61
53
43
37
31
29
19
13
13
11
7
5
5
3
3
3
2
2

Prime Factor Certification

Signed Primo certificates for the seven largest prime factors of N-1, ranging from 422 to 6279 digits, are included in: 4529_16381.zip.

Tom Wu
Last modified: Fri Oct 26 19:00:00 PDT 2012