Primality Certificate for (5207^4129-1)/5206

Andy Steward	15,343 digits	15 March 2010
Primality Certificate for (5207^4129-1)/5206
Originally by A.A.D.Steward 2010

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

From	Factorisation
5207	41 · 127
Φ₂	2 · 2 · 2 · 3 · 7 · 31
Φ₃	1933 · 14029
Φ₄	2 · 5 · 5 · 569 · 953
Φ₆	3 · 37 · 103 · 2371
Φ₈	2 · 367553290448401
Φ₁₂	13 · 73 · 7057 · 109765021
Φ₁₆	2 · 17 · 10513 · 1256929057 · 1202774671044833
Φ₂₄	10177 · 53098328120053483128508513
Φ₃₂	2 · 3361 · 248609 · 34393537 · 8292599521 · p33
Φ₄₃	947 · 13417 · 1158504023 · 5469068789722842426132343 · p116
Φ₄₈	97 · 193 · 104725451126292571626104401 · p30
Φ₈₆	1033 · 1291 · 652913 · 4443707 · 102822308297 · p127
Φ₉₆	140929 · 4680961 · 4703703649 · p98
Φ₁₂₉	486589 · 1471643082706285813 · 2302020898185053556607 · 33659819687733741704239 · 125403565757821477292416392253 · p216
Φ₁₇₂	173 · 169937 · 9099661 · 227120052614281117 · 383170373830942657 · p263
Φ₂₅₈	c313
Φ₃₄₄	117190089217 · c614
Φ₅₁₆	4129 · 227427001 · 374625289 · 3769535322193 · c592
Φ₆₈₈	12586517619891984312097 · 360791785608877337092817 · 1975696223805806657622400673 · c1176
Φ₁₀₃₂	157897 · 620649961 · 3008861017 · 4553751390985418467298353 · c1201
Φ₁₃₇₆	2753 · p2495
Φ₂₀₆₄	338497 · c2493
Φ₄₁₂₈	144481 · 115084513 · 620314561 · 503825409313 · 2540869382542794817 · 64555717971710233049349889 · c4918

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

12795 1678274593 7103038218 5861179455 1125170944 0537595337 5067432611 7720012916 6694978975 1277122343 1193940283 1599101403 6059830445 7741471840 7761422755 6483549258 7576808920 2191773898 9569858134 8679717642 7989919654 8267051709 8717406831 8140993691 0141563644 7819794028 3494496308 0526193073 9300922091 6908532680 5985536322 6012689368 9817961179 0741749558 8620896270 7364130135 4545730400 7298186866 5183347269 8631011392 6375412002 0724187030 4362912982 2892276837 2258161360 4698167060 7205367919 6433394542 0802144948 1927705927 9457445997 5735156320 0526354781 9406547820 8565783624 2911748595 3529601702 6729004854 8141720270 2784053843 2123030901 9816004061 7485756902 1447511488 1516207719 9415123942 5765084676 3469749921 2716273250 2133988426 7309721323 9410703238 1251478737 3362708059 2008825364 9433548699 7631281408 8894916675 6332783660 1733036733 0650694435 5101287648 6164454920 0603341791 8757671272 8284416949 1168209882 9065068742 1151992056 4816969654 0688234572 8199599503 8408410946 9125794707 6578448655 8608346305 3295332284 0241559458 5237692885 6405976972 5709795897 8245815386 4017966698 4729982947 1169976668 5484592139 4295566011 8930286262 0334393200 2797525669 0208001325 5816130548 4836061601 3680110214 6852579188 7271270148 6716688619 8910612352 8582801728 7255553964 7207297049 0804055453 8632282457 9956744107 3347703241 0636476722 8953530373 2913898038 2264063296 7448151920 6395466272 7682032964 6670381893 8251578429 1490768827 0581213830 2462287806 2651671653 8407038443 4718269648 5115057296 8386822028 9875491375 6161904255 8382171203 3673040657 2706191252 4057397392 7765412508 8467915738 4923678261 9492727160 0913674518 1359798806 8095195752 3645812026 1519160961 4775624687 0131471198 9302217290 4230937562 2568680769 9370964486 1874830932 5659434698 1734748385 9711169850 3581191405 7536272498 4246349778 3513039693 3127335742 9833245524 1942021017 6517350986 1323843544 3472624384 7455325469 9292960802 8339742442 0130185616 8105288586 3867308886 7520251209 9437253794 0852950131 9180432194 7891953249 8319567007 9136254498 4179164316 5493171641 1781247005 4845773430 1618356502 8013093170 6985604868 3429535554 8113392842 4861857284 2101138054 2519531140 7564796140 4657031263 8253780309 2875554437 7884348640 6327805672 3850017822 4214350942 0346697747 2600053439 3684851697 3873819046 9560712749 9247475957 0628703655 7855917146 4127061038 5176151166 1244989709 2050382214 1221520763 8077453359 4743163967 4956736109 1216356298 3992434297 6278823677 4733701915 6685645606 7968256685 7849892108 9061766932 3667237988 9655897214 4149526801 3986542309 9472173360 3010819406 8558481641 4952667577 8475260487 0901790190 8876222234 1805877919 0029936864 2581344107 9035120724 6885754817
670 4244467976 6103357862 0508875106 2503789571 0195890300 3620455668 5536411518 6216178866 5511053692 5606675152 7865462576 9888945489 9559506095 5624470050 0412948079 1026278727 4787336592 6285833765 5764564536 5296020962 3962763861 7000319031 0123482970 6800576897 9771329567 3477580877
224273 2093935231 0827478320 1851195016 9663561891 0204120373 1358427661 7758499286 8109269879 5250636204 5964408898 0282415442 8206322010 8917450010 1688255016 1926096699 3257959805 0503342238 8469845283 1989139558 1904132836 4540947253
3139642 6495819663 0266507458 8304805062 1486764614 6191350526 9541655983 5385404345 6723181173 4766178436 6147884863 0170718561 4906002603
155219 1658866073 9741652511 0105940731 2366965055 9258695072 8966356033 9099060915 9954213927 2222832747 7844795325 9460603787
27480658 8553518026 8837712776 4349164239 1910378231 8918302912 7875479693 7928991101 0246018462 7308111521
612 6583474991 3052771734 8080643937
1489429528 6492643866 2556796881
1254035657 5782147729 2416392253
19756962 2380580665 7622400673
1047254 5112629257 1626104401
645557 1797171023 3049349889
530983 2812005348 3128508513
54690 6878972284 2426132343
45537 5139098541 8467298353
3607 9178560887 7337092817
336 5981968773 3741704239
125 8651761989 1984312097
23 0202089818 5053556607
254086938 2542794817
147164308 2706285813
38317037 3830942657
22712005 2614281117
120277 4671044833
36755 3290448401
376 9535322193
50 3825409313
11 7190089217
10 2822308297
8292599521
4703703649
3008861017
1256929057
1158504023
620649961
620314561
374625289
227427001
115084513
109765021
34393537
9099661
4680961
4443707
652913
486589
338497
248609
169937
157897
144481
140929
14029
13417
10513
10177
7057
4129
3361
2753
2371
1933
1291
1033
953
947
569
193
173
127
103
97
73
41
37
31
17
13
7
5²
3²
2⁷

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) = 26.330547%

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 = 11 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F⁴>N, N can have no more than three prime factors.

Express N in base F

As F² < N < F³ and N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

c₁= 3617859027 0870349160 9925331304 2537776033 7910631935 2302150658 2157126953 4336215823 0295973203 2384309848 4863774942 7135656484 0974163362 9005767950 2128010961 5413757861 7626422567 8844000266 0673081604 9489235719 3607808702 8905546012 8376245716 0159535502 6850666824 7729281565 2155318661 8178912565 8268571869 7608700331 9333171060 7821487039 5863722132 7289576326 6306173479 6210730760 5833850947 3515741941 0086094288 7940278295 5287658772 3286939143 0884237156 8119671690 0705779289 4117298781 0549271094 2564162463 6228600967 7476030450 3698518296 9498431685 8101668730 1060959771 3178910910 3005609858 5348362331 4272657337 6792669749 0678165986 5862616021 9541796388 4649841516 9605605339 7316861489 5377169773 0196117736 3758762488 9429613440 8398079230 1752598278 7408795444 4103276824 0925066123 9262269336 0195271669 3542077934 1124995743 0701762503 0997669055 1155207410 7054070086 1071029500 6199099128 8566666698 5680600573 6515290856 0467104487 5134678506 1970101655 9905278554 7765355593 8717243264 0518994923 5201884670 5262452213 7661971411 8176566371 6480402191 3207057325 8085268745 3563942642 8527778642 9262694564 7302441252 2408004794 0464361607 1439445432 1794314645 8591152217 6538781861 0591514777 7470304313 3111211716 1582567479 5947951883 7191301588 9256882552 7520388453 4517674094 5454789319 6254691236 1513018867 1243675435 7328498733 0372338162 3462351905 6495068879 6149157565 0077416098 6394983753 5526425218 5055386870 8830967993 1573890612 9073416816 6318719971 4341672907 9862425149 9866919977 4620495855 0371953135 1554650520 8460824673 2349330332 6718496932 5014389531 4957841436 8805339950 4310924219 5897324645 9398492278 8936988072 9743019929 1832577731 7534061152 4983444077 9163876493 8499027679 0991099278 2041288871 8867571657 2969582751 3560404580 3807245753 3902310400 7226158450 8423857821 8153994159 4864065734 3716318969 1974176335 5423835202 9894931365 9384114674 6758346287 3280658567 3995935628 3099495760 0442704708 9937653829 1685887653 5145057136 7721714603 1332735255 9865091482 4241855755 0499634189 4211888104 1885806397 9039761649 8679107832 3020292273 6567783784 2373706197 6033258789 2433902012 2388602598 2497410872 9571738659 6123006221 9563825698 2802522624 0093538286 6044797528 2721750792 2555274043 2052070578 8369854916 2404669953 7319874934 1490969987 3661479907 8769822975 1300674004 9788440614 1067488121 1891937351 6728383858 2516387692 9722551460 8044265916 7081863593 4338368844 8844086301 9122544596 0234381847 7409670756 0364949517 0205566347 2447968728 0264385253 2442665372 3544109424 8196829598 7131402003 2754471222 8243947805 8141971024 8410492273 5441680596 9189393528 2941793346 3857180875 3163551429 9988081982 3394793411 7723761919 5477620190 2235243556 9965776400 9950513041 2031000112 3323304465 1877559031 1605960959 8641374056 0125156645 7115444863 3383751065 2152622493 1362385512 5969604188 5496299912 6001718852 6845538528 1017068110 8126147641 5664384722 9848099743 4450729611 7311947985 9916709212 9322990695 3426611258 4044880137 9149707424 6307239086 6846329145 0094119634 9153782655 0060695492 0206568428 8614767516 2346124225 8654865291 4446117865 8638023106 5968035387 9111971375 8622048513 0037051057 0777894183 0388017303 3139531634 2697939307 6590678134 4803614533 5193964811 4698364860 1620216028 1056003029 8792436317 3071120426 4778032452 2245931464 2133611353 5781887392 2316743286 0651078365 5810132091 4679704755 4969901942 4733329906 0088636393 1868143497 4570737780 0787080075 9419808913 9925849244 0096756751 0143130466 7800947691 3995898880 5349483081 0542453427 4143719669 4044531362 8909598490 8743943290 9541909003 3881154633 3180424029 7358958389 9112562780 8976900979 5703601919 1712094883 9940734290 5870199392 4098947890 5078758573 0425909775 3637489312 4178205759 4123696952 3070557530 0886008448 3571760035 6278723150 9940641925 8022579249 5265943979 3832342846 7709263908 6632610301 1541481155 1872343923 3762259157 9596679042 9912054456 4623062354 4248635015 3176999475 8557379975 0143715235 8460615130 2438450781 8874290768 2952257652 5005584132 1523195941 7040399149 1990998902 0895059501 0260092478 5185666545 0343145427 5013366940 8543973396 2411028481 7202986563 8668621575 5539953958 3859450678 0890119400 3487266703 6788555538 1771739317 4514349248 6444083750 9215113534 2908877570 2044786839 5305856369 4463099642 2795632190 2188256577 6407150061 8281007033 3800823629 5506397047 9607681402 0251142329
c₂= 588 6920907208 8039948932 1109894884 8638687508 4917472481 1001451890 3242622494 8886820736 4584069230 7586793213 7984761270 9325767476 9454838633 2746244546 0735824115 0661618111 4236822515 0042103223 6244473731 1846509798 7163839874 4861124383 6811303314 2662788045 6824398462 3823740294 5295680460 4118518575 3719624379 1447602098 4991434497 3877366976 3517504816 5951231170 8092719408 8460970582 1191560199 1182914515 1983654391 4488673779 3384775452 5909139040 7718191957 1219818584 6700573150 7437255269 9838646857 6453049115 2639231430 0031296956 1282656498 1649799897 5420422235 6195073602 1534202571 8663181080 6548437792 3280061936 3454021459 7170151122 8912438831 2652421747 4915615133 4864353922 6048180224 6865230293 8353120756 4158414714 4257911776 0692217860 0349188241 2128578713 8446975730 0511050645 7430062119 2309269639 0056886474 0569570390 3438493120 2323411594 1158079038 8315477699 4327483327 3369712037 8948281387 8690765658 8341481827 3439143340 9572542781 6513857509 1208979639 4284575623 7055199722 3920607275 8474155480 3319000049 7971406776 3107754695 3375306768 6623936724 7129782943 0106062952 0681835189 5043453411 7541463311 3878540431 7629593610 2108771521 5744166170 1391367931 5741951645 7130084890 9923544859 5295861453 4812105248 0155378111 6525270542 5863567913 6352901871 4818295549 2140375408 1015784478 1010365130 6297318910 7103915551 7901276980 6808380983 4817144994 7022333459 8793099779 8704029080 5924007062 0558611906 3800656216 7634587912 9976281812 2661027984 2521734936 7042710769 4797123787 8906936948 4025267788 9977896675 6005972426 7981108385 6145664647 6678675346 3573964685 7765601261 6793333547 8469017058 0997030584 6299020120 2923389017 6859981777 2191171731 8843010031 6991353925 4200226349 0241638468 9437453599 2564588404 5256570921 5976914521 2106473862 3421928544 1786214397 6335257967 3086471023 7084139543 7698109394 2840892768 1367354123 2616857112 2372957547 3242782198 6746368518 7601343979 6831088052 7487325019 5189545095 9476334962 3308047439 3813555217 2213077259 2535715481 8638759223 4689444220 3727389340 1644660273 0737886074 6229014609 7725723658 4307932301 0032248063 7971453930 3294197523 6380804984 8843474352 4633695620 1104246242 8351011618 2941389909 6525877861 1824162369 0143657336 5358617751 5806297402 2795201956 6623952001 2281693335 6258075672 0223165233 3276205874 2691826793 1369857244 3544552169 8188852041 2160315779 9493700455 3875797532 0149215462 0195258813 8520523953 6996578697 9072805398 3974708226 3303119555 6879805652 8248135232 2743611076 5872371571 1013976595 3883234682 2969817625 7010003641 8855845940 3345826705 9196169699 4061716757 6037590487 2429603047 1818480577 8583833783 2787368885 4480325158 8908907574 5260330974 1643846576 3003266235 4862730100 6269593811 8455082076 4025282245 8984724409 8880853466 8478478511 5130320907 6476817585 1746495981 1861444764 6901079111 6745324472 7339280651 0165813277 3312608292 7298769723 5770993596 8172665968 0861842699 1409488120 1443954330 7979544731 0280951965 3578860744 7765803954 3640869651 3289253111 5698887399 7231914108 7762179535 7333973494 0148842380 5161490187 7805432424 2209435466 1546693198 7792765112 3896227010 4469562132 3740718693 8997901429 4601391994 7668517843 1619790282 9808366739 9986176382 3556236822 3115345358 0256696546 4647961353 0505086965 2102158199 8275937485 3963637599 3374320018 1698646481 2609470104 1792779993 6960966317 2490439801 3709764844 9925027701 6523724610 9348462912 9390576810 6001641845 2172794263 5434586994 3626597085 8379738749 8328847038 5652406555 3966697333 6383635213 5425606174 7320474802 2259347652 3288892908 4928000803 0433020093 8249757175 0881738809 6890624023 4676064495 6679091616 0441061923 9674529625 7250297046 0135017288 3705554917 8415743729 0521168479 6247431493 0918226247 9054386642 9018668364 2961243718 9164765694 4294551430 6375318721 7350422682 4318533434 2963009993 2698332555 9198758467 4359917584 9813328079 1692145796 0009853567 8176776382 3780022106 0104275658 2582475259 2596110607 8800068835 4772859884 2730958058 6283540995 6457968812 1648867070 8866848554 9828683116 2267141362 0439075054 4085145764 6280858827 0425681824 5437465217 6271248285 7778411892 8383335084 4455887926 1992915745 7861679935 5082918850 3964602675 1812522658 8224238924 0975616341 7096926897 2648489953 3380697272 7972453678 1907933862 1366459060 3207898886 9415450354 0996388611 3853739265 5145323399 8151481468 5673201917 1878600570 9469687175 5678118334 0054754552 5040223619 6684861863 7487862049 8444021208 1147684985 9880579065 5078665830 0219807277 2433182827 1834356807 4557047330 2623256712 4977755713 5317023152 4926156509 9814531585 9011032612 8773920973 1435478906 3927912563 4581925877 8284395757 0555380179 1891932354 4798449278 6826305200 8639349893 4351375359 1048877758 4782082622 5729779965 0463336140 7735901967 2626461118 8634205615 5313321042 9448561635 7242733034 5701400423 7245681335 3122631637 9570101137 1943227876 8918924848 8108564630 6543676308 5257304453 8680066333 3819295311 7825391784 4104547882 1001541000 5618841074 2798060972 8874788278 8685295635 4098499254 9615124108 0086618425 2924735162 4545659282 5918061810 2412287848 3391532586 6786429979 5768865983 3857570619 5990463999 0320194585 1282813669 1121733344 9376824511 1110868781 5689362432 2616036944 6299263586 0271140246 7305876416 4772050543 1909061940 9402690653 0561768700 5342145024 0567265636 2326775248 0950176037 3899548925 9634080193 7234627235 6045174170 4131931597 4645999565 0793769633 4321663795 2373670730 9113858698 4842586578 9395879787 7729334557 4102250934 8271416529 6817317761 2855846914 2722011230 4087534739 5866867872 2298996662 5904843768 0583450491 0892322456 7816967868 0433946837 9297126950 3696503672 3291188010 1094982984 1298114332 0455078041 1352451798 8965020991 0232874511 2780767055 4540978051 7994781947 1672905741 4667029590 3060211550 4258345173 7206761442 1951164494 4348282931 9923718475 1863212622 2481334457 8190548769 7207323612 0804670090 3667824142 0869418424 4417422030 8074197778 2207648672 4913667899 0882155939 6909667989 8634695787 5049385502 7854984249 7581658560 9602825004 4117505066 1138196928 1636102345 4545295948 7809895075 9868283990 5999679982 6512713082 0228575727 1951168898 7121103902 6038647267 6278870541 4067970083 9200929606 2041023766 8155919516 8497173293 8599646250 2719339617 7602935925 6804420241 4117713805 1441360089 3314298975 8404354510 9605768367 2296036058 8254084279 0553456066 0244501284 9013150731 8761467019 4472242430 8842239363 9799253731 8577373490 5874054445 5113675238 3173774083 8926992754 2988629078 8547609739 8112018911 3398918659 7263757516 3383510685 1385610990 2125192533 4395530450 6097705718 8696447121 4056111994 3162329359 2906525337 7573753165 2122357443 7030051125 1144472485 6742301131 4561741120 4896716895 6860100305 6175263246 4978745124 5756405626 7667207985 5985972321 2994317053 3713134522 2754555279 6862671546 1570268923 8133843306 9319264427 3665532962 7655205160 3825381650 8230865502 6167284727 0400820166 5943005069 4530836262 1486081234 9326084901 0060296124 7685416568 0517129545 7508754105 3974156091 7698669500 0520161650 0075559307 5129927274 9794731892 4792242997 4758185329 2972781700 4727070117 9570071911 4285571655 7989932900 8166868717 7635295255 6691183645 4475374128 6470776448 7592505551 6356605354 2379090982 2380169378 2882892338 7061937714 6451046012 1634324619 0904757827 0601751951 0087616454 5345633734 4195809703 4874833633 4681735209 1314596140 0707669895 9421294457 3333684679 2885564624 4267404799 0552325956 5377711960 3915578047 2846874529 1522260179 8890246598 5043447806 7791273038 0932044595 7337099312 9954885826 9928407586 0750881938 0777798677 6849939527 5456355452 2541961388 3672440442 0500343360 3602968997 5468375524 2061896343 6638076954 5265411437 0937686779 1283686786 9159874227 5108667654 5738648707 4991435249 9806979757 6160070245 5191825446 8669969036 2991202436 0412330803 3037078017 9316461183 8094179455 9585860800 6398933203

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c₁²-4·c₂ is a perfect square.

Here, c₁²-4·c₂ is ≡ 37 (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:

Welcome to the CHG primality prover!
------------------------------------
realprecision = 6502 significant digits (6500 digits displayed)
Input file is:  IO\14571021.cin
Certificate file is:  IO\14571021.chg
Found values of n, F and G.
    Number to be tested has 15343 digits.
    Modulus has 4040 digits.
Modulus is 26.33054672% 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 = 20, u = 9. Right endpoint has 3224 digits.
        Done!  Time elapsed:  71535469ms.
    Running CHG with h = 20, u = 9. Right endpoint has 3198 digits.
        Done!  Time elapsed:  57072375ms.
    Running CHG with h = 21, u = 9. Right endpoint has 3172 digits.
        Done!  Time elapsed:  100585281ms.
    Running CHG with h = 20, u = 9. Right endpoint has 3137 digits.
        Done!  Time elapsed:  608368563ms.
    Running CHG with h = 19, u = 8. Right endpoint has 3108 digits.
        Done!  Time elapsed:  61150422ms.
    Running CHG with h = 19, u = 8. Right endpoint has 3090 digits.
        Done!  Time elapsed:  63102500ms.
    Running CHG with h = 19, u = 8. Right endpoint has 3070 digits.
        Done!  Time elapsed:  63965546ms.
    Running CHG with h = 19, u = 8. Right endpoint has 3048 digits.
        Done!  Time elapsed:  62310875ms.
    Running CHG with h = 19, u = 8. Right endpoint has 3023 digits.
        Done!  Time elapsed:  63842735ms.
    Running CHG with h = 19, u = 8. Right endpoint has 2995 digits.
        Done!  Time elapsed:  69243390ms.
    Running CHG with h = 19, u = 8. Right endpoint has 2964 digits.
        Done!  Time elapsed:  73551704ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2928 digits.
        Done!  Time elapsed:  144117359ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2917 digits.
        Done!  Time elapsed:  37760234ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2903 digits.
        Done!  Time elapsed:  48199203ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2889 digits.
        Done!  Time elapsed:  43229688ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2871 digits.
        Done!  Time elapsed:  42944344ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2852 digits.
        Done!  Time elapsed:  46662922ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2830 digits.
        Done!  Time elapsed:  45494406ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2804 digits.
        Done!  Time elapsed:  44136578ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2775 digits.
        Done!  Time elapsed:  44564828ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2742 digits.
        Done!  Time elapsed:  62334875ms.
    Running CHG with h = 17, u = 7. Right endpoint has 2704 digits.
        Done!  Time elapsed:  69000344ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2660 digits.
        Done!  Time elapsed:  19432844ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2644 digits.
        Done!  Time elapsed:  21178296ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2625 digits.
        Done!  Time elapsed:  26846375ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2602 digits.
        Done!  Time elapsed:  16388704ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2576 digits.
        Done!  Time elapsed:  16694406ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2545 digits.
        Done!  Time elapsed:  37544234ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2507 digits.
        Done!  Time elapsed:  39276563ms.
    Running CHG with h = 15, u = 6. Right endpoint has 2464 digits.
        Done!  Time elapsed:  11509109ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2414 digits.
        Done!  Time elapsed:  11459656ms.
    Running CHG with h = 14, u = 5. Right endpoint has 2397 digits.
        Done!  Time elapsed:  18905266ms.
    Running CHG with h = 14, u = 5. Right endpoint has 2363 digits.
        Done!  Time elapsed:  20142000ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2320 digits.
        Done!  Time elapsed:  18480891ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2281 digits.
        Done!  Time elapsed:  13669328ms.
    Running CHG with h = 13, u = 5. Right endpoint has 2238 digits.
        Done!  Time elapsed:  21988281ms.
    Running CHG with h = 12, u = 4. Right endpoint has 2186 digits.
        Done!  Time elapsed:  2452297ms.
    Running CHG with h = 12, u = 4. Right endpoint has 2162 digits.
        Done!  Time elapsed:  2149797ms.
    Running CHG with h = 12, u = 4. Right endpoint has 2130 digits.
        Done!  Time elapsed:  4385000ms.
    Running CHG with h = 11, u = 4. Right endpoint has 2085 digits.
        Done!  Time elapsed:  3671859ms.
    Running CHG with h = 12, u = 4. Right endpoint has 2041 digits.
        Done!  Time elapsed:  4124313ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1962 digits.
        Done!  Time elapsed:  5040812ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1900 digits.
        Done!  Time elapsed:  805781ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1879 digits.
        Done!  Time elapsed:  767750ms.
    Running CHG with h = 10, u = 3. Right endpoint has 1847 digits.
        Done!  Time elapsed:  815907ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1799 digits.
        Done!  Time elapsed:  852078ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1754 digits.
        Done!  Time elapsed:  839437ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1688 digits.
        Done!  Time elapsed:  1241313ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1597 digits.
        Done!  Time elapsed:  1349515ms.
    Running CHG with h = 8, u = 2. Right endpoint has 1491 digits.
        Done!  Time elapsed:  246891ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1445 digits.
        Done!  Time elapsed:  211734ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1416 digits.
        Done!  Time elapsed:  214641ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1372 digits.
        Done!  Time elapsed:  206500ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1306 digits.
        Done!  Time elapsed:  201891ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1206 digits.
        Done!  Time elapsed:  208343ms.
    Running CHG with h = 7, u = 2. Right endpoint has 1033 digits.
        Done!  Time elapsed:  201094ms.
    Running CHG with h = 5, u = 1. Right endpoint has 750 digits.
        Done!  Time elapsed:  23469ms.
    Running CHG with h = 5, u = 1. Right endpoint has 478 digits.
        Done!  Time elapsed:  23500ms.
A certificate has been saved to the file:  IO\14571021.chg

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

Testing a PRP called "IO\14571021.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.140602184 E-16 at X, ratio=5.041933366 E-494 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.2623602265 at X, ratio=1.107633729 E-272 at Y, witness=2.
Pol[3, 1] with [h, u]=[7, 2] has ratio=0.1270703678 at X, ratio=6.72794517 E-566 at Y, witness=5.
Pol[4, 1] with [h, u]=[7, 2] has ratio=1.477649186 E-174 at X, ratio=8.63103019 E-348 at Y, witness=2.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.03911147794 at X, ratio=2.144054797 E-199 at Y, witness=7.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.04917539644 at X, ratio=2.651389770 E-133 at Y, witness=3.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.3919912559 at X, ratio=5.095424080 E-89 at Y, witness=3.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.2428919699 at X, ratio=1.359158131 E-59 at Y, witness=2.
Pol[9, 1] with [h, u]=[8, 2] has ratio=0.3504998811 at X, ratio=3.529146728 E-91 at Y, witness=11.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.2937349965 at X, ratio=1.611891253 E-319 at Y, witness=2.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.563326638 at X, ratio=5.90659014 E-274 at Y, witness=7.
Pol[12, 1] with [h, u]=[9, 3] has ratio=1.048655420 E-67 at X, ratio=2.636116415 E-200 at Y, witness=7.
Pol[13, 1] with [h, u]=[9, 3] has ratio=7.30278366 E-46 at X, ratio=9.43315488 E-134 at Y, witness=17.
Pol[14, 1] with [h, u]=[10, 3] has ratio=0.007615588120 at X, ratio=1.603983141 E-144 at Y, witness=3.
Pol[15, 1] with [h, u]=[10, 3] has ratio=0.04059544957 at X, ratio=1.328223130 E-96 at Y, witness=19.
Pol[16, 1] with [h, u]=[10, 3] has ratio=0.0633493536 at X, ratio=1.140156497 E-64 at Y, witness=3.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.4864541112 at X, ratio=1.085608992 E-249 at Y, witness=3.
Pol[18, 1] with [h, u]=[12, 4] has ratio=0.1358885754 at X, ratio=1.108009656 E-313 at Y, witness=3.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.3455154375 at X, ratio=1.709396737 E-178 at Y, witness=2.
Pol[20, 1] with [h, u]=[12, 4] has ratio=0.0875163121 at X, ratio=7.93276963 E-180 at Y, witness=2.
Pol[21, 1] with [h, u]=[12, 4] has ratio=0.2017361631 at X, ratio=5.15859495 E-131 at Y, witness=17.
Pol[22, 1] with [h, u]=[12, 4] has ratio=0.3475027368 at X, ratio=1.797543961 E-95 at Y, witness=2.
Pol[23, 1] with [h, u]=[13, 5] has ratio=0.0902604029 at X, ratio=7.29014049 E-259 at Y, witness=5.
Pol[24, 1] with [h, u]=[13, 5] has ratio=0.575599528 at X, ratio=2.744858521 E-217 at Y, witness=3.
Pol[25, 1] with [h, u]=[13, 5] has ratio=0.2095569741 at X, ratio=1.493016287 E-197 at Y, witness=2.
Pol[26, 1] with [h, u]=[14, 5] has ratio=0.4098731933 at X, ratio=4.124510249 E-216 at Y, witness=5.
Pol[27, 1] with [h, u]=[14, 5] has ratio=0.06188941782 at X, ratio=1.762947468 E-166 at Y, witness=2.
Pol[28, 1] with [h, u]=[13, 5] has ratio=4.88523100 E-19 at X, ratio=1.255315646 E-89 at Y, witness=5.
Pol[29, 1] with [h, u]=[15, 6] has ratio=0.550413639 at X, ratio=4.721911330 E-296 at Y, witness=3.
Pol[30, 1] with [h, u]=[15, 6] has ratio=0.1713032360 at X, ratio=2.770464790 E-260 at Y, witness=5.
Pol[31, 1] with [h, u]=[15, 6] has ratio=1.864557540 E-39 at X, ratio=8.70002161 E-232 at Y, witness=2.
Pol[32, 1] with [h, u]=[15, 6] has ratio=1.240264136 E-34 at X, ratio=1.486019703 E-185 at Y, witness=2.
Pol[33, 1] with [h, u]=[15, 6] has ratio=0.03627007432 at X, ratio=2.086871033 E-157 at Y, witness=13.
Pol[34, 1] with [h, u]=[15, 6] has ratio=0.06000193404 at X, ratio=5.041849828 E-135 at Y, witness=2.
Pol[35, 1] with [h, u]=[15, 6] has ratio=0.3927934628 at X, ratio=8.79582730 E-116 at Y, witness=5.
Pol[36, 1] with [h, u]=[15, 6] has ratio=0.05777085338 at X, ratio=2.267316530 E-99 at Y, witness=2.
Pol[37, 1] with [h, u]=[17, 7] has ratio=0.03547613419 at X, ratio=4.247849653 E-305 at Y, witness=3.
Pol[38, 1] with [h, u]=[17, 7] has ratio=0.528554093 at X, ratio=5.029597106 E-267 at Y, witness=13.
Pol[39, 1] with [h, u]=[17, 7] has ratio=0.1710806678 at X, ratio=8.31809165 E-234 at Y, witness=5.
Pol[40, 1] with [h, u]=[17, 7] has ratio=0.03034317305 at X, ratio=1.267195451 E-204 at Y, witness=5.
Pol[41, 1] with [h, u]=[17, 7] has ratio=0.3756325454 at X, ratio=3.838333969 E-179 at Y, witness=5.
Pol[42, 1] with [h, u]=[17, 7] has ratio=0.2031941085 at X, ratio=7.44627750 E-157 at Y, witness=7.
Pol[43, 1] with [h, u]=[17, 7] has ratio=0.1114902724 at X, ratio=2.615185335 E-137 at Y, witness=17.
Pol[44, 1] with [h, u]=[17, 7] has ratio=0.2065511842 at X, ratio=2.678068251 E-120 at Y, witness=13.
Pol[45, 1] with [h, u]=[17, 7] has ratio=0.1344615045 at X, ratio=2.856101563 E-105 at Y, witness=11.
Pol[46, 1] with [h, u]=[17, 7] has ratio=0.2987214693 at X, ratio=3.118944275 E-92 at Y, witness=7.
Pol[47, 1] with [h, u]=[17, 7] has ratio=0.01819621348 at X, ratio=7.350363480 E-81 at Y, witness=2.
Pol[48, 1] with [h, u]=[19, 8] has ratio=0.001785360934 at X, ratio=5.025569608 E-285 at Y, witness=2.
Pol[49, 1] with [h, u]=[19, 8] has ratio=0.0870894790 at X, ratio=2.571860038 E-253 at Y, witness=19.
Pol[50, 1] with [h, u]=[19, 8] has ratio=0.03311939631 at X, ratio=2.210110867 E-225 at Y, witness=29.
Pol[51, 1] with [h, u]=[19, 8] has ratio=0.2006724312 at X, ratio=2.158615811 E-200 at Y, witness=17.
Pol[52, 1] with [h, u]=[19, 8] has ratio=0.3443179315 at X, ratio=3.433849129 E-178 at Y, witness=7.
Pol[53, 1] with [h, u]=[19, 8] has ratio=0.1640232730 at X, ratio=2.003701826 E-158 at Y, witness=2.
Pol[54, 1] with [h, u]=[19, 8] has ratio=0.1106213948 at X, ratio=6.30866257 E-141 at Y, witness=5.
Pol[55, 1] with [h, u]=[20, 9] has ratio=0.1125161526 at X, ratio=8.38217649 E-269 at Y, witness=13.
Pol[56, 1] with [h, u]=[21, 9] has ratio=0.0971608708 at X, ratio=9.44415071 E-310 at Y, witness=3.
Pol[57, 1] with [h, u]=[20, 9] has ratio=0.1328565272 at X, ratio=2.032778760 E-238 at Y, witness=3.
Pol[58, 1] with [h, u]=[20, 9] has ratio=0.4210678336 at X, ratio=5.464484760 E-233 at Y, witness=3.

Validated in 100 sec.


Congratulations! n is prime!

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