Primality Certificate for (89^11971-1)/88

Andy Steward23,335 digits30 May 2009
Originally by Tom Wu 2009
A066180 #1436

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

From Factorisation
8989
Φ22 · 3 · 3 · 5
Φ38011
Φ5131 · 691 · 701
Φ63 · 7 · 373
Φ7502628805631
Φ973 · 6807972547
Φ105 · 31 · 400291
Φ14329617 · 1491001
Φ153892362992828641
Φ183 · 19 · 8718957649
Φ19407741 · p30
Φ214327 · 6815459113 · 8281163311
Φ3033151 · 120081279391
Φ3571 · 3221 · 3139991 · p35
Φ38419 · 58711 · 1726379 · 2858235254856451102639
Φ427 · 43 · 127 · 8443 · 31333 · 24698067997
Φ4524703741 · 5869174411 · p30
Φ57308397361 · 26205153553 · 64156711609 · 110689786879261483849 · 259589135279367544177
Φ63631 · 1971901 · 35885986039 · p51
Φ70211 · p45
Φ9028650459490921 · 2675667780679681 · 795787283527238521
Φ95761 · 6714601 · 1123157296866691991 · p113
Φ1051051 · 1537621 · 3235261 · 267214716195146703447437422562520456421 · p40
Φ114350395182714847 · p56
Φ1264539277 · 4099137663888793 · 21062392661862533682541 · 38446247824311279000318481
Φ1332927 · 354047 · 48929327007211179761 · 3019434409417859181869738532979 · 23951217836326037378215298615132348447310456341310123229375773418560883 · p81
Φ171167757157 · 469005661292895001762371525637 · 2167174701521677009644782562981482674303 · p134
Φ190191 · 1901 · 15146818079392621 · 52948932423599020031 · 2469467652296763115318663993936011104869721 · p57
Φ210134372281 · p86
Φ2661597 · 41322241509739 · 9423055447844765546061119036668303899067072236192530130676552317619702390990040003 · p112
Φ2852225851 · 135551701 · 5629604449951 · 8376410251871526831391 · p232
Φ31520161 · 1787867551 · 77920323619951 · 21367609695414361 · p237
Φ34219 · 8463794159539 · 142930732537727801627301765041299884820393293196326972842650995257535946922023440378841 · p111
Φ399130602367771 · 5091409074798439 · 92957292708831868393140148841149 · c363
Φ570571 · 2851 · p275
Φ6306301 · 108663243300991 · 359931808994487031 · 4322696829498252451 · 56446744592436000160410195816610790848272342457180531 · c174
Φ66587552571 · 43149950492043667091 · 54307168149603562110475145351 · c786
Φ798c422
Φ85511971 · 711638731 · 35663932185978584946691 · 23019663630281523487565428377358097766453991 · p764
Φ11974789 · 311995657 · 35669522701 · c1241
Φ133010202255437240651 · 9234420785371044761 · 60852507059273073081950769901489509011 · 506651396724139292973223195238130636461 · c731
Φ17104234864591 · 1233454707491164759506195721 · 56720247909816966079065745811260507729561 · c765
Φ1995385617541 · 1062852974906941 · 4674705441489931 · p1645
Φ239429465353 · 1378730198623051 · 1361339262450710449164416674313464213 · c1205
Φ3990127681 · 347131 · 22974421 · c1667
Φ5985132826866247838386026847074523570651 · c5018
Φ1197047881 · 71821 · 7204894610050427986159381 · 110956215666343670301789060637551481 · c4984

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

96755 3077854145 4219503428 1907597229 3827196004 4905609377 5197572290 2837919792 7415288522 4452937920 3209334447 6398720590 6269314370 2249776850 5141052052 1002815146 5156702310 7981510708 7500814864 4503394060 8708099739 0390351700 3498046399 7101908659 9408199617 6720292317 6435711740 0011660708 0777094374 4789221684 8825440176 4265938651 6074063016 6990521733 1658278131 3156452273 0659353563 4721780276 9567968750 1278177377 7227025143 9040433549 3716331814 7060363729 7742063595 2545502533 9850572701 2068554563 6079634436 6089415185 6942902195 8549187615 1673056993 5651316411 1449867811 3055119979 6473719337 1162621955 9778631873 3266278583 8129167816 2785732228 3976645392 7459885650 3273135526 6312890287 8010843792 1064110118 3254836739 4817661105 3863776626 6132259631 5099971197 0798366910 9741320977 7663623811 7886700033 4489034069 4200011683 2267255568 1056696525 2131714678 2668280196 6704902322 8142280188 3333791593 3036901743 8883122454 6988429618 4736043108 0639717210 5662997116 8388908525 0080114666 0606966807 3143630731 2245300193 0540015373 0161427001 1153884292 1778428659 1174720239 4316399557 5343371805 7959522853 8221770464 3121298935 4762326528 5353953950 6450136967 7249680126 8453214948 8724116286 5566987018 6885480708 0933012419 2648898238 2823391494 9361670827 1588955007 0455568333 0883944591 0085697341 7891326395 0612814964 4509155711 6413638162 0412960984 0457740002 5649478524 5800483783 8605332156 3969455506 6565468548 4026840630 8780986357 1262178901 9145409809 2468832912 1896980494 3234610520 1285577967 0456459372 7135605804 4640813391 8975674605 0216840278 2735849617 5153878264 2905474653 7297706025 3212633668 5135098892 4521608840 0115383296 6747395487 3786999424 8526850967 5566335907 9470163119 6871250889 8481564195 4349647047 7039177937 7119528211
1957 7862797667 8570645237 6178490523 6354241754 0445735744 4868828335 9164543420 0711374600 4056749414 5504372201 0708237416 9978278734 1557019127 1330069357 2131663434 7778219614 9731183873 5490823402 6564619092 4321153463 0861771887 7512487328 2683733603 3223552147 4643544490 8563659413 6281935795 8793163583 5000271858 4812578360 3281569376 8683252154 8232693608 6239449076 9505746588 8084713544 1705045141 0511922735 9589367490 5844280405 9264861580 1533496390 8618378629 4227453737 4742697523 1225659116 9474023979 3206638800 2121571303 9958491483 0881758334 6715933416 6669532310 4930028321 0065223857 7700245863 0668211943 4474163741 0811577846 1637976678 3822918599 8679563783 7612055621 2992974225 0878188432 4092498179 2671685978 4903221654 3909356158 5699322403 4396410721 9021583571 8660003303 6073265611 0288098538 4252955581
31309 4720623918 5699225310 3812433616 5693120632 2401368691 9644841793 0075153411 3877403581 8652009776 3083793772 6943702532 7916409375 5263233163 5585244567 8441821225 9901168276 7390643540 1701501145 1516922768 4659530781 9644593126 5423966353 0603578530 5621764281 1299519501 7112937396 9018273201
8588305 2372387937 7829364977 1020796916 3591346054 3481039435 4176464866 2637019898 0238412507 8123169924 0437977880 9547321203 7918072790 6045644586 1455478043 0011647591 3837756215 3043009271 8045466050 1734073259 3183692245 9368642897 9042862914 5486407801
36 6379186045 2840626194 5262227689 3189114856 6198162307 7499344653 3439503735 8514300944 4345253162 9135080254 2586536043 6789919775 2179690873 0662593731 6109641352 7189554045 9317090023 3098481693 8865259864 8240676825 4786462203 9564719961 7156773031
2006 1667895727 4260413957 5088565333 3225575460 3900501440 1034496445 8645079488 4205321900 2795169296 4892304822 0817328826 2566171077 6907495783
391 1359130059 6515762346 1965315653 5080211066 1353088953 0179738989 3219455211 2048375922 7611951641 4145503869 6710305511
55 6279026609 0328834945 1662686990 2956919986 3108594559 3610225382 4087915402 9312567212 5475730369 4145507516 0545628709
1 4882538697 9399622845 3486142239 0154263586 4398910774 4708487551 5473857919 2097337495 0950369283 0048396483 5605499761
1429307 3253772780 1627301765 0412998848 2039329319 6326972842 6509952575 3594692202 3440378841
273879 0058840235 5895254774 8438068143 5780127013 2378076312 1760869381 5874366034 8577634761
94 2305544784 4765546061 1190366683 0389906707 2236192530 1306765523 1761970239 0990040003
9 2237452345 9419261082 5597911535 3870236760 3449663133 5034145019 5922130654 7234631657
2 3951217836 3260373782 1529861513 2348447310 4563413101 2322937577 3418560883
3192534 0495426497 3136967362 5821508536 9057524200 0843930401
434844 5177925553 3149037817 0433351802 6452052351 0538888623
564 4674459243 6000160410 1958166107 9084827234 2457180531
3 3744288297 2800845950 3148199774 6348246326 3275747509
29236 8249098271 8263605637 7138896891 1082878011
2301 9663630281 5234875654 2837735809 7766453991
246 9467652296 7631153186 6399393601 1104869721
5 6720247909 8169660790 6574581126 0507729561
2694047972 7321296617 7246950070 4479955991
2167174701 5216770096 4478256298 1482674303
506651396 7241392929 7322319523 8130636461
267214716 1951467034 4743742256 2520456421
60852507 0592730730 8195076990 1489509011
1361339 2624507104 4916441667 4313464213
132826 8662478383 8602684707 4523570651
110956 2156663436 7030178906 0637551481
83999 2383619206 2908311215 6644098941
92 9572927088 3186839314 0148841149
3 0194344094 1785918186 9738532979
4690056612 9289500176 2371525637
4207458127 7118017283 1231619071
3044689926 8488869270 2752314551
543071681 4960356211 0475145351
12334547 0749116475 9506195721
384462 4782431127 9000318481
72048 9461005042 7986159381
356 6393218597 8584946691
210 6239266186 2533682541
83 7641025187 1526831391
28 5823525485 6451102639
2 5958913527 9367544177
1 1068978687 9261483849
5294893242 3599020031
4892932700 7211179761
4314995049 2043667091
923442078 5371044761
432269682 9498252451
112315729 6866691991
79578728 3527238521
35993180 8994487031
2136760 9695414361
1514681 8079392621
1020225 5437240651
509140 9074798439
467470 5441489931
409913 7663888793
389236 2992828641
267566 7780679681
137873 0198623051
106285 2974906941
35039 5182714847
10866 3243300991
7792 0323619951
4132 2241509739
2865 0459490921
846 3794159539
562 9604449951
50 2628805631
13 0602367771
12 0081279391
6 4156711609
3 5885986039
3 5669522701
2 6205153553
2 4698067997
8718957649
8281163311
6815459113
6807972547
5869174411
4234864591
1787867551
711638731
385617541
311995657
308397361
167757157
135551701
134372281
87552571
29465353
24703741
22974421
6714601
4539277
3235261
3139991
2225851
1971901
1726379
1537621
1491001
407741
400291
354047
347131
329617
127681
71821
58711
47881
33151
31333
20161
11971
8443
8011
6301
4789
4327
3221
2927
2851
1901
1597
1051
761
701
691
631
571
419
373
211
191
131
127
89
73
71
43
31
192
72
52
34
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) = 25.642516%

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 = 2 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 ≡ 21 (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, we also make use of a partial (0.3238%) factorization of N+1 as G:

22
41647271
345848533
39334160917
222946072284908512271
7137077042934537673236868831
Here is the stdout:

parisize = 8000000, primelimit = 500000

Testing a PRP called "89_11971.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.6276345495500688194 E-1380 at X, ratio=3.580073548520162205 E-1380 at Y, witness=2.
Pol[2, 1] with [h, u]=[5, 1] has ratio=0.08660704902544096269 at X, ratio=3.3936549920888186994 E-658 at Y, witness=3.
Pol[3, 1] with [h, u]=[5, 1] has ratio=0.007060644288023561680 at X, ratio=1.3527880275180646789 E-329 at Y, witness=3.
Pol[4, 1] with [h, u]=[4, 1] has ratio=7.694101170290470078 E-112 at X, ratio=1.0465645168878783589 E-275 at Y, witness=3.
Pol[5, 1] with [h, u]=[4, 1] has ratio=1.0407484864493000166 E-193 at X, ratio=1.1030445043210059088 E-275 at Y, witness=5.
Pol[6, 1] with [h, u]=[4, 1] has ratio=4.511090965074270439 E-235 at X, ratio=1.0791938965290461405 E-275 at Y, witness=2.
Pol[7, 1] with [h, u]=[4, 1] has ratio=3.110122511856801657 E-256 at X, ratio=3.3832484827740377300 E-276 at Y, witness=7.
Pol[8, 1] with [h, u]=[4, 1] has ratio=8.872749154206530550 E-266 at X, ratio=5.580498414015664906 E-276 at Y, witness=5.
Pol[9, 1] with [h, u]=[7, 2] has ratio=1.1262493967659725278 E-158 at X, ratio=1.8186119493212746442 E-647 at Y, witness=3.
Pol[10, 1] with [h, u]=[7, 2] has ratio=1.2971375494992113004 E-333 at X, ratio=7.730393532825986227 E-496 at Y, witness=2.
Pol[11, 1] with [h, u]=[7, 2] has ratio=3.475208283184315273 E-224 at X, ratio=1.6776840328877040217 E-332 at Y, witness=3.
Pol[12, 1] with [h, u]=[8, 2] has ratio=0.17191352918397914197 at X, ratio=1.3501666378789559442 E-297 at Y, witness=7.
Pol[13, 1] with [h, u]=[8, 2] has ratio=0.08685480477240545768 at X, ratio=1.1604250092500893465 E-170 at Y, witness=2.
Pol[14, 1] with [h, u]=[8, 2] has ratio=0.09090047494910361583 at X, ratio=5.103062575433676584 E-98 at Y, witness=3.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.10401045455876733599 at X, ratio=6.498699574866059618 E-331 at Y, witness=19.
Pol[16, 1] with [h, u]=[10, 3] has ratio=0.008117400135258075392 at X, ratio=5.082494391432160645 E-495 at Y, witness=5.
Pol[17, 1] with [h, u]=[10, 3] has ratio=0.08635824519284576177 at X, ratio=2.0267658172977691788 E-330 at Y, witness=3.
Pol[18, 1] with [h, u]=[10, 3] has ratio=0.012674748137336487208 at X, ratio=7.608149990471885206 E-221 at Y, witness=5.
Pol[19, 1] with [h, u]=[10, 3] has ratio=0.05172879542200615169 at X, ratio=1.0562498093053093778 E-147 at Y, witness=11.
Pol[20, 1] with [h, u]=[12, 4] has ratio=0.019235200054676021500 at X, ratio=2.0816038266543071378 E-554 at Y, witness=3.
Pol[21, 1] with [h, u]=[12, 4] has ratio=0.07774206369888864278 at X, ratio=1.0657878408348948562 E-403 at Y, witness=7.
Pol[22, 1] with [h, u]=[12, 4] has ratio=0.03437644411117730445 at X, ratio=5.701514329638646543 E-294 at Y, witness=5.
Pol[23, 1] with [h, u]=[12, 4] has ratio=0.007574084119533420700 at X, ratio=2.204123948583350118 E-214 at Y, witness=3.
Pol[24, 1] with [h, u]=[12, 4] has ratio=0.021448809055287624244 at X, ratio=3.210665225648335482 E-156 at Y, witness=7.
Pol[25, 1] with [h, u]=[12, 4] has ratio=0.005545263614259560663 at X, ratio=4.661708018943123030 E-114 at Y, witness=3.
Pol[26, 1] with [h, u]=[14, 5] has ratio=0.04013590208351762291 at X, ratio=6.798598290223572616 E-475 at Y, witness=5.
Pol[27, 1] with [h, u]=[14, 5] has ratio=0.05205791299013295463 at X, ratio=1.0932528898866788670 E-365 at Y, witness=5.
Pol[28, 1] with [h, u]=[14, 5] has ratio=0.03684700897030245628 at X, ratio=8.469295359499301626 E-282 at Y, witness=3.
Pol[29, 1] with [h, u]=[14, 5] has ratio=0.03211802344930026146 at X, ratio=4.169519063187898225 E-217 at Y, witness=3.
Pol[30, 1] with [h, u]=[14, 5] has ratio=0.0007829063801177717266 at X, ratio=1.9660298739276459676 E-167 at Y, witness=13.
Pol[31, 1] with [h, u]=[14, 5] has ratio=0.04102403050727998453 at X, ratio=4.120768035721435585 E-129 at Y, witness=5.
Pol[32, 1] with [h, u]=[16, 6] has ratio=0.023264787203660780686 at X, ratio=1.8498731517983751678 E-450 at Y, witness=19.
Pol[33, 1] with [h, u]=[16, 6] has ratio=0.007429526928510799737 at X, ratio=1.0177015446773477022 E-360 at Y, witness=5.
Pol[34, 1] with [h, u]=[16, 6] has ratio=0.009595965114034005882 at X, ratio=6.055686060340420475 E-289 at Y, witness=7.
Pol[35, 1] with [h, u]=[16, 6] has ratio=0.03190182764590156245 at X, ratio=1.5113376503765830509 E-231 at Y, witness=47.
Pol[36, 1] with [h, u]=[16, 6] has ratio=0.04802602954892544437 at X, ratio=1.3934160344400962711 E-185 at Y, witness=11.
Pol[37, 1] with [h, u]=[18, 7] has ratio=0.025307651942113461604 at X, ratio=4.835552820002924950 E-472 at Y, witness=3.
Pol[38, 1] with [h, u]=[16, 6] has ratio=0.005901196380147038511 at X, ratio=3.087130380024557399 E-68 at Y, witness=11.
Pol[39, 1] with [h, u]=[18, 7] has ratio=0.006885237989511493483 at X, ratio=1.9434038354803348134 E-375 at Y, witness=19.
Pol[40, 1] with [h, u]=[18, 7] has ratio=0.003432980526624849114 at X, ratio=1.6905937002582526076 E-309 at Y, witness=11.
Pol[41, 1] with [h, u]=[18, 7] has ratio=0.004825496687717025156 at X, ratio=2.886113119406868059 E-255 at Y, witness=7.
Pol[42, 1] with [h, u]=[18, 7] has ratio=0.005157919956925831649 at X, ratio=1.7027458713703474762 E-210 at Y, witness=2.
Pol[43, 1] with [h, u]=[18, 7] has ratio=0.010884061269051163250 at X, ratio=9.988863015495347215 E-174 at Y, witness=2.
Pol[44, 1] with [h, u]=[20, 8] has ratio=0.002000921912743121300 at X, ratio=2.503009890787826333 E-445 at Y, witness=7.
Pol[45, 1] with [h, u]=[20, 8] has ratio=0.00003338263496929236844 at X, ratio=2.5039445216267157700 E-375 at Y, witness=5.
Pol[46, 1] with [h, u]=[20, 8] has ratio=0.012950616094528861736 at X, ratio=2.2979276231726596000 E-316 at Y, witness=7.
Pol[47, 1] with [h, u]=[20, 8] has ratio=0.014983565001885331023 at X, ratio=9.086248814015717698 E-267 at Y, witness=5.
Pol[48, 1] with [h, u]=[20, 8] has ratio=0.002869955519565375994 at X, ratio=5.457590251717533512 E-225 at Y, witness=7.
Pol[49, 1] with [h, u]=[20, 8] has ratio=0.0017577071234049536226 at X, ratio=8.294742153627984320 E-190 at Y, witness=3.
Pol[50, 1] with [h, u]=[20, 8] has ratio=0.011777831171316476521 at X, ratio=3.707089653771678045 E-160 at Y, witness=5.
Pol[51, 1] with [h, u]=[20, 8] has ratio=0.007277373214562809450 at X, ratio=3.377144517245425541 E-135 at Y, witness=2.
Pol[52, 1] with [h, u]=[21, 9] has ratio=0.010633997254611386123 at X, ratio=2.1931960197392222864 E-274 at Y, witness=3.
Pol[53, 1] with [h, u]=[21, 9] has ratio=0.004428920219803951330 at X, ratio=4.128480859888360236 E-247 at Y, witness=2.
Pol[54, 1] with [h, u]=[22, 9] has ratio=0.002818988029597297585 at X, ratio=3.539477340343346077 E-326 at Y, witness=11.
Pol[55, 1] with [h, u]=[22, 9] has ratio=0.0004912077514066266543 at X, ratio=7.081795190279813147 E-280 at Y, witness=2.
Pol[56, 1] with [h, u]=[22, 9] has ratio=0.010611671817143623172 at X, ratio=3.472728168072166020 E-240 at Y, witness=3.
Pol[57, 1] with [h, u]=[22, 9] has ratio=0.0008040264706712018540 at X, ratio=3.258416001069933594 E-206 at Y, witness=7.
Pol[58, 1] with [h, u]=[22, 9] has ratio=0.013223525788128237961 at X, ratio=4.867682533951676213 E-177 at Y, witness=3.
Pol[59, 1] with [h, u]=[23, 10] has ratio=0.0005347855881484648913 at X, ratio=1.6889875708337374280 E-339 at Y, witness=19.
Pol[60, 1] with [h, u]=[23, 10] has ratio=0.003674233742184270100 at X, ratio=1.0366688395432904620 E-308 at Y, witness=7.
Pol[61, 1] with [h, u]=[23, 10] has ratio=0.002444672206245324286 at X, ratio=5.537525022646524968 E-281 at Y, witness=19.
Pol[62, 1] with [h, u]=[23, 10] has ratio=0.000000016707758966911152969 at X, ratio=6.891974076249926785 E-261 at Y, witness=7.
Pol[63, 1] with [h, u]=[23, 10] has ratio=8.246841472787701256 E-36 at X, ratio=1.4662405334570236994 E-241 at Y, witness=13.
Pol[64, 1] with [h, u]=[23, 10] has ratio=0.006348679351796856524 at X, ratio=1.3296521143600452526 E-211 at Y, witness=5.
Pol[65, 1] with [h, u]=[23, 10] has ratio=0.00004002614647898101914 at X, ratio=1.3633237411147619888 E-192 at Y, witness=2.
Pol[66, 1] with [h, u]=[23, 10] has ratio=0.0013340556701777180632 at X, ratio=3.036919221985604575 E-175 at Y, witness=5.
Pol[67, 1] with [h, u]=[23, 10] has ratio=0.010797511837541458393 at X, ratio=1.3739753020432144047 E-159 at Y, witness=5.
Pol[68, 1] with [h, u]=[25, 11] has ratio=0.002128908579847056864 at X, ratio=8.599530773021368685 E-381 at Y, witness=2.
Pol[69, 1] with [h, u]=[25, 11] has ratio=0.011191012683457016786 at X, ratio=3.140237578183987821 E-349 at Y, witness=2.
Pol[70, 1] with [h, u]=[25, 11] has ratio=0.0005368598477042684036 at X, ratio=2.495590292440575163 E-320 at Y, witness=2.
Pol[71, 1] with [h, u]=[25, 11] has ratio=0.0011776063530132000897 at X, ratio=7.681719546194277147 E-294 at Y, witness=5.
Pol[72, 1] with [h, u]=[25, 11] has ratio=0.003733037701423788068 at X, ratio=1.6655008162302403898 E-269 at Y, witness=7.
Pol[73, 1] with [h, u]=[25, 11] has ratio=0.0004716144036731915163 at X, ratio=3.136490935730841646 E-247 at Y, witness=7.
Pol[74, 1] with [h, u]=[25, 11] has ratio=0.006654280787176095130 at X, ratio=6.933035192446414584 E-227 at Y, witness=11.
Pol[75, 1] with [h, u]=[25, 11] has ratio=0.002628071824628631658 at X, ratio=3.926919189753072506 E-208 at Y, witness=2.
Pol[76, 1] with [h, u]=[27, 12] has ratio=0.002140989207660000089 at X, ratio=4.494284462617937037 E-424 at Y, witness=3.
Pol[77, 1] with [h, u]=[25, 11] has ratio=0.004535446123679673568 at X, ratio=8.835352388838363855 E-159 at Y, witness=7.
Pol[78, 1] with [h, u]=[27, 12] has ratio=0.002085062630903842715 at X, ratio=1.3773141862296258476 E-378 at Y, witness=11.
Pol[79, 1] with [h, u]=[27, 12] has ratio=0.002107514042204827413 at X, ratio=1.2382927131375664639 E-349 at Y, witness=3.
Pol[80, 1] with [h, u]=[27, 12] has ratio=0.0015134564878487343238 at X, ratio=6.309792873086469274 E-323 at Y, witness=5.
Pol[81, 1] with [h, u]=[27, 12] has ratio=0.0007308393252279501130 at X, ratio=2.994514532690816401 E-298 at Y, witness=7.
Pol[82, 1] with [h, u]=[27, 12] has ratio=0.0012054242470060426216 at X, ratio=1.6774688300833391471 E-275 at Y, witness=7.
Pol[83, 1] with [h, u]=[27, 12] has ratio=0.002583268771034132285 at X, ratio=1.3890359790167784195 E-254 at Y, witness=3.
Pol[84, 1] with [h, u]=[27, 12] has ratio=0.002861581573217274174 at X, ratio=3.891277992305916962 E-235 at Y, witness=17.
Pol[85, 1] with [h, u]=[27, 12] has ratio=0.006274197837916598271 at X, ratio=3.5020106014877371408 E-217 at Y, witness=3.
Pol[86, 1] with [h, u]=[28, 13] has ratio=0.0019258270711376581060 at X, ratio=3.376822899863925413 E-374 at Y, witness=3.
Pol[87, 1] with [h, u]=[28, 13] has ratio=0.002695578795170324074 at X, ratio=1.985155782148016194 E-360 at Y, witness=7.
Pol[88, 1] with [h, u]=[28, 13] has ratio=0.0014469443905976850799 at X, ratio=3.584772088176161542 E-347 at Y, witness=17.
Pol[89, 1] with [h, u]=[28, 13] has ratio=0.002998539410261169340 at X, ratio=2.0748801050215478842 E-334 at Y, witness=7.
Pol[90, 1] with [h, u]=[28, 13] has ratio=0.0017255385572497470788 at X, ratio=4.437743009778393459 E-322 at Y, witness=11.
Pol[91, 1] with [h, u]=[28, 13] has ratio=0.0016225297701974585832 at X, ratio=3.0831289973661454892 E-310 at Y, witness=7.
Pol[1, 2] with [h, u]=[5, 1] has ratio=2.697031699238860107 E-1380 at X, ratio=2.721327373652221996 E-1380 at Y, witness=5.
Pol[2, 2] with [h, u]=[5, 1] has ratio=0.10705508251270807009 at X, ratio=5.206878373572677967 E-658 at Y, witness=5.
Pol[3, 2] with [h, u]=[5, 1] has ratio=0.3333985427166455234 at X, ratio=1.7950098562725369696 E-329 at Y, witness=3.
Pol[4, 2] with [h, u]=[4, 1] has ratio=6.964841614849832521 E-137 at X, ratio=7.883524555351360668 E-301 at Y, witness=2.
Pol[5, 2] with [h, u]=[4, 1] has ratio=3.606724515701922816 E-219 at X, ratio=1.1760902963875158209 E-300 at Y, witness=5.
Pol[6, 2] with [h, u]=[4, 1] has ratio=2.6175421991267143176 E-260 at X, ratio=7.403088177711536565 E-301 at Y, witness=2.
Pol[7, 2] with [h, u]=[4, 1] has ratio=1.0469190416062769626 E-280 at X, ratio=5.441394066784074375 E-301 at Y, witness=2.
Pol[8, 2] with [h, u]=[4, 1] has ratio=9.053314793206067075 E-291 at X, ratio=9.537437480241060494 E-301 at Y, witness=3.
Pol[9, 2] with [h, u]=[7, 2] has ratio=1.4393487668771091203 E-157 at X, ratio=1.3651537649682312076 E-647 at Y, witness=7.
Pol[10, 2] with [h, u]=[7, 2] has ratio=1.1171169349033105514 E-332 at X, ratio=1.0399239762164730378 E-495 at Y, witness=5.
Pol[11, 2] with [h, u]=[7, 2] has ratio=7.307316491849909943 E-224 at X, ratio=2.4788539342068100114 E-332 at Y, witness=3.
Pol[12, 2] with [h, u]=[8, 2] has ratio=0.03210638610606863384 at X, ratio=6.608764615149762445 E-298 at Y, witness=3.
Pol[13, 2] with [h, u]=[8, 2] has ratio=0.06396284508963929494 at X, ratio=1.2287648813926929973 E-170 at Y, witness=13.
Pol[14, 2] with [h, u]=[8, 2] has ratio=0.18867961204082568362 at X, ratio=4.317794622524219145 E-98 at Y, witness=5.
Pol[15, 2] with [h, u]=[9, 3] has ratio=0.03522475081585598996 at X, ratio=6.957849491323385601 E-331 at Y, witness=17.
Pol[16, 2] with [h, u]=[10, 3] has ratio=0.03796485492054546388 at X, ratio=5.482299549367765805 E-495 at Y, witness=7.
Pol[17, 2] with [h, u]=[10, 3] has ratio=0.015523145461949960007 at X, ratio=1.7170153940167003362 E-330 at Y, witness=2.
Pol[18, 2] with [h, u]=[10, 3] has ratio=0.03758488086959789016 at X, ratio=9.143633655548932911 E-221 at Y, witness=5.
Pol[19, 2] with [h, u]=[10, 3] has ratio=0.03631649094835362057 at X, ratio=1.2483296965092361103 E-147 at Y, witness=7.
Pol[20, 2] with [h, u]=[12, 4] has ratio=0.015995873332353288222 at X, ratio=2.1150463838826216342 E-554 at Y, witness=17.
Pol[21, 2] with [h, u]=[12, 4] has ratio=0.09997554883319061183 at X, ratio=1.4754253841572911990 E-403 at Y, witness=3.
Pol[22, 2] with [h, u]=[12, 4] has ratio=0.014120167697435035747 at X, ratio=6.046461389212203122 E-294 at Y, witness=11.
Pol[23, 2] with [h, u]=[12, 4] has ratio=0.05883981114328891747 at X, ratio=3.062201215562837759 E-214 at Y, witness=5.
Pol[24, 2] with [h, u]=[12, 4] has ratio=0.016328964711131802362 at X, ratio=2.966481389077048647 E-156 at Y, witness=2.
Pol[25, 2] with [h, u]=[12, 4] has ratio=0.04855705752101181923 at X, ratio=4.675358260192131547 E-114 at Y, witness=11.
Pol[26, 2] with [h, u]=[14, 5] has ratio=0.018076934976142081032 at X, ratio=5.610344511951583432 E-475 at Y, witness=2.
Pol[27, 2] with [h, u]=[14, 5] has ratio=0.0006609903108622118298 at X, ratio=7.634979847286988220 E-366 at Y, witness=5.
Pol[28, 2] with [h, u]=[14, 5] has ratio=0.028437050422738190064 at X, ratio=1.0541052121745242853 E-281 at Y, witness=2.
Pol[29, 2] with [h, u]=[14, 5] has ratio=0.04470158826602348428 at X, ratio=4.012503755697252436 E-217 at Y, witness=3.
Pol[30, 2] with [h, u]=[14, 5] has ratio=0.0004131272546560228339 at X, ratio=2.2498582625868938484 E-167 at Y, witness=2.
Pol[31, 2] with [h, u]=[14, 5] has ratio=0.04588777333387185553 at X, ratio=3.790561614785791424 E-129 at Y, witness=2.
Pol[32, 2] with [h, u]=[16, 6] has ratio=0.004882646431975632741 at X, ratio=1.8215329800416762258 E-450 at Y, witness=11.
Pol[33, 2] with [h, u]=[16, 6] has ratio=0.014875293411644849198 at X, ratio=8.463120392992621585 E-361 at Y, witness=5.
Pol[34, 2] with [h, u]=[16, 6] has ratio=0.024059458271665445274 at X, ratio=6.115849407490656748 E-289 at Y, witness=2.
Pol[35, 2] with [h, u]=[16, 6] has ratio=0.007267010114379166157 at X, ratio=1.6538968639097066515 E-231 at Y, witness=7.
Pol[36, 2] with [h, u]=[16, 6] has ratio=0.003117787036594418798 at X, ratio=1.4413235532614177300 E-185 at Y, witness=3.
Pol[37, 2] with [h, u]=[18, 7] has ratio=0.019787829462183970350 at X, ratio=5.379118032510874648 E-472 at Y, witness=5.
Pol[38, 2] with [h, u]=[16, 6] has ratio=0.016624020568024547203 at X, ratio=3.213661242229349314 E-68 at Y, witness=3.
Pol[39, 2] with [h, u]=[18, 7] has ratio=0.0016037053762497140487 at X, ratio=2.2982354320309409650 E-375 at Y, witness=17.
Pol[40, 2] with [h, u]=[18, 7] has ratio=0.0016526757568233879183 at X, ratio=1.8271142587485652267 E-309 at Y, witness=11.
Pol[41, 2] with [h, u]=[18, 7] has ratio=0.008828484873134986003 at X, ratio=3.079480441800319633 E-255 at Y, witness=11.
Pol[42, 2] with [h, u]=[18, 7] has ratio=0.007116719469440952554 at X, ratio=1.7271967197390732131 E-210 at Y, witness=2.
Pol[43, 2] with [h, u]=[18, 7] has ratio=0.00012908567117953554950 at X, ratio=9.304691754601338030 E-174 at Y, witness=2.
Pol[44, 2] with [h, u]=[20, 8] has ratio=0.006958040387039118401 at X, ratio=2.2329911427725664572 E-445 at Y, witness=5.
Pol[45, 2] with [h, u]=[20, 8] has ratio=0.0008344038514504084139 at X, ratio=2.4261485170209140644 E-375 at Y, witness=5.
Pol[46, 2] with [h, u]=[20, 8] has ratio=0.013129176324140056248 at X, ratio=2.1842985158473835198 E-316 at Y, witness=11.
Pol[47, 2] with [h, u]=[20, 8] has ratio=0.002660044212762904803 at X, ratio=8.336998472527172290 E-267 at Y, witness=5.
Pol[48, 2] with [h, u]=[20, 8] has ratio=0.004036742455543674494 at X, ratio=4.555404022392737834 E-225 at Y, witness=11.
Pol[49, 2] with [h, u]=[20, 8] has ratio=0.005662099927381009773 at X, ratio=1.0202232878533004217 E-189 at Y, witness=23.
Pol[50, 2] with [h, u]=[20, 8] has ratio=0.005192003929348401192 at X, ratio=3.492003093831764079 E-160 at Y, witness=5.
Pol[51, 2] with [h, u]=[20, 8] has ratio=0.023703035309880702168 at X, ratio=3.694043093012294643 E-135 at Y, witness=2.
Pol[52, 2] with [h, u]=[21, 9] has ratio=0.004840187948601853691 at X, ratio=2.2492350014526484224 E-274 at Y, witness=13.
Pol[53, 2] with [h, u]=[21, 9] has ratio=0.0014425549454055985963 at X, ratio=4.010874271667781490 E-247 at Y, witness=3.
Pol[54, 2] with [h, u]=[22, 9] has ratio=0.003722455414957501526 at X, ratio=3.886418251977453318 E-326 at Y, witness=2.
Pol[55, 2] with [h, u]=[22, 9] has ratio=0.009153693835673468553 at X, ratio=7.245121049883145039 E-280 at Y, witness=11.
Pol[56, 2] with [h, u]=[22, 9] has ratio=0.002359372538362088087 at X, ratio=3.178675749642641646 E-240 at Y, witness=5.
Pol[57, 2] with [h, u]=[22, 9] has ratio=0.002695376023557842404 at X, ratio=3.200336164110746866 E-206 at Y, witness=13.
Pol[58, 2] with [h, u]=[22, 9] has ratio=0.010997305024975105532 at X, ratio=5.109492848835602702 E-177 at Y, witness=2.
Pol[59, 2] with [h, u]=[23, 10] has ratio=0.005393935318190739750 at X, ratio=2.484953399330564612 E-339 at Y, witness=13.
Pol[60, 2] with [h, u]=[23, 10] has ratio=0.0007889473569082460419 at X, ratio=8.491328920220983746 E-309 at Y, witness=3.
Pol[61, 2] with [h, u]=[23, 10] has ratio=0.0018738487047188125120 at X, ratio=7.829132133408909538 E-281 at Y, witness=2.
Pol[62, 2] with [h, u]=[23, 10] has ratio=0.00000003954772763435028654 at X, ratio=7.104964084090141535 E-261 at Y, witness=7.
Pol[63, 2] with [h, u]=[23, 10] has ratio=4.504222674499113578 E-35 at X, ratio=1.6026741389573257810 E-241 at Y, witness=7.
Pol[64, 2] with [h, u]=[23, 10] has ratio=0.010391921175709166460 at X, ratio=1.4844679113273990320 E-211 at Y, witness=2.
Pol[65, 2] with [h, u]=[23, 10] has ratio=0.009317534876000226821 at X, ratio=1.1156398985129602949 E-192 at Y, witness=11.
Pol[66, 2] with [h, u]=[23, 10] has ratio=0.003789854486214475990 at X, ratio=2.774612975095634850 E-175 at Y, witness=13.
Pol[67, 2] with [h, u]=[23, 10] has ratio=0.00011194582193241333855 at X, ratio=1.4218695131680493929 E-159 at Y, witness=7.
Pol[68, 2] with [h, u]=[25, 11] has ratio=0.003562508724754614967 at X, ratio=9.001651782077120158 E-381 at Y, witness=2.
Pol[69, 2] with [h, u]=[25, 11] has ratio=0.0011194838483371833177 at X, ratio=3.088200529274584466 E-349 at Y, witness=13.
Pol[70, 2] with [h, u]=[25, 11] has ratio=0.000008212740856607978446 at X, ratio=2.670897365079623067 E-320 at Y, witness=5.
Pol[71, 2] with [h, u]=[25, 11] has ratio=0.003007379124514089538 at X, ratio=9.539856223576833253 E-294 at Y, witness=2.
Pol[72, 2] with [h, u]=[25, 11] has ratio=0.005272578169155549923 at X, ratio=1.6774639566648019732 E-269 at Y, witness=5.
Pol[73, 2] with [h, u]=[25, 11] has ratio=0.008402632226402782931 at X, ratio=2.938036110851068221 E-247 at Y, witness=11.
Pol[74, 2] with [h, u]=[25, 11] has ratio=0.0019277241574896004474 at X, ratio=7.069370205923520798 E-227 at Y, witness=3.
Pol[75, 2] with [h, u]=[25, 11] has ratio=0.0013403896476976787768 at X, ratio=4.153001981356500745 E-208 at Y, witness=3.
Pol[76, 2] with [h, u]=[27, 12] has ratio=0.004095921533260436613 at X, ratio=4.659646719994380944 E-424 at Y, witness=11.
Pol[77, 2] with [h, u]=[25, 11] has ratio=0.003206991085056617513 at X, ratio=9.238052409430196440 E-159 at Y, witness=7.
Pol[78, 2] with [h, u]=[27, 12] has ratio=0.0009416439947623540681 at X, ratio=1.6009826376976127056 E-378 at Y, witness=3.
Pol[79, 2] with [h, u]=[27, 12] has ratio=0.005781757920972739952 at X, ratio=1.2016817692575006528 E-349 at Y, witness=23.
Pol[80, 2] with [h, u]=[27, 12] has ratio=0.00010509323230450691724 at X, ratio=6.848542060642634626 E-323 at Y, witness=11.
Pol[81, 2] with [h, u]=[27, 12] has ratio=0.002364674468838728044 at X, ratio=3.289204643040281341 E-298 at Y, witness=5.
Pol[82, 2] with [h, u]=[27, 12] has ratio=0.002573593414136458872 at X, ratio=1.7074160079434692510 E-275 at Y, witness=5.
Pol[83, 2] with [h, u]=[27, 12] has ratio=0.0015489610111122002963 at X, ratio=1.2981774817055430499 E-254 at Y, witness=17.
Pol[84, 2] with [h, u]=[27, 12] has ratio=0.003917670529926937422 at X, ratio=3.668869209763165404 E-235 at Y, witness=2.
Pol[85, 2] with [h, u]=[27, 12] has ratio=0.004640924800463198913 at X, ratio=3.0050576338230114472 E-217 at Y, witness=11.
Pol[86, 2] with [h, u]=[28, 13] has ratio=0.0008403246085377766062 at X, ratio=3.557776796629505378 E-374 at Y, witness=29.
Pol[87, 2] with [h, u]=[28, 13] has ratio=0.002582218320535849434 at X, ratio=2.268274656193541833 E-360 at Y, witness=3.
Pol[88, 2] with [h, u]=[28, 13] has ratio=0.002599970018356594929 at X, ratio=3.819077500527086208 E-347 at Y, witness=7.
Pol[89, 2] with [h, u]=[28, 13] has ratio=0.002306076716086692479 at X, ratio=2.5548637881224193240 E-334 at Y, witness=7.
Pol[90, 2] with [h, u]=[28, 13] has ratio=0.0006424165092147135069 at X, ratio=4.294955958886652571 E-322 at Y, witness=13.
Pol[91, 2] with [h, u]=[28, 13] has ratio=0.0010421579758292881981 at X, ratio=3.0299266831491240734 E-310 at Y, witness=5.

Validated in 250 sec.

Goodbye!

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