Primality Certificate for (3556^2621-1)/3555

Andy Steward	9,304 digits	03 March 2010
Primality Certificate for (3556^2621-1)/3555
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.526157% factorization of N-1:

From	Factorisation
3556	2 · 2 · 7 · 127
Φ₂	3557
Φ₄	2269 · 5573
Φ₅	5 · 11 · 1511 · 1924606741
Φ₁₀	7151 · 22354147811
Φ₂₀	24001 · 6064921 · 7945261 · 22107077341
Φ₁₃₁	263 · 3407 · 33013 · 5853343 · p445
Φ₂₆₂	56743699 · 4441003753 · 608293240351 · 48342087558913 · 1135532676575428633631 · c398
Φ₅₂₄	1049 · c921
Φ₆₅₅	140171 · c1842
Φ₁₃₁₀	77291 · 22393141 · p1835
Φ₂₆₂₀	2621 · 18341 · 885578341 · c3677

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

18280 5545851718 8841648498 3165788959 4865041322 1378196514 1677502089 0372049445 4092077264 2900889685 5421056797 8606609103 2790426349 3090248706 3521430826 0865380267 8375132264 4928257601 9975879123 3139126889 6053189677 0359674244 5767873230 0714034325 0900170112 1010496911 2316876610 8683733900 3685036034 6007950593 0592169378 7031282087 5144863902 8205012671 0346583854 5761598432 9035721997 4537477342 2200637717 0735838604 7236365565 3902392494 9808386397 8207824209 1778665726 7397240773 8502643177 8195458373 2973038875 6290258424 0408731457 7830379398 0502020142 3654763645 9760230116 7468422744 0477909089 1607041021 2133007266 2298860976 7471529305 1283781313 1327780986 9813471112 0687239843 7209273075 7219778339 2548069079 4954307417 9217251456 7014646633 0465300728 5669539911 1448773746 6948032277 4854679259 9915322836 4948869791 6722575957 1769150001 9235418075 3062559678 4071969591 0770544997 5714740790 5734399598 0198654375 0785620681 1509200062 5303876007 3678951360 4997051047 5460062648 8686965798 2581565503 1544357296 7401195223 5111197472 3815359667 7503211429 1338551568 0136904866 4367377257 2375920047 5323067154 6602250911 4175168949 8997863625 5352750723 1278881502 5689625585 6007855901 5507542871 4928830682 1944634227 0103315867 7411473875 7801890444 2793838723 4258029591 6395063549 1637706198 5731576285 2202091790 5876294347 1779533104 5089626585 0466323520 3773407454 2773338942 7228858584 0018605022 4932780841 2872292545 4499733527 5051157499 6444410895 5841565757 7296161896 5146015347 8250306373 5256834488 3256623677 0088896257 6384394594 2949963189 8389205205 8058953366 0167594769 4779762899 9312895910 5614291458 4920671189 4510018948 0943171131 1848007013 0462423008 5656130592 0528460545 5690546670 0005533401 0349700140 2352797789 1566443935 6214425197 6436392341 3354169435 3525365071 0443657714 0214857279 2072813153 2717997559 5205654486 5899245347 6663821980 0825786778 5931171477 3066788161 0444631207 8981136422 6272115044 4082868017 8256958856 3582913171
24363 1308630207 8418588492 8928133227 6004994241 8151087670 1966460416 4829417812 1741254717 7524276349 5617931116 3361510524 4356483988 3699221820 0013616503 3191440274 7215710765 4947289412 0963984850 8459768606 8583372575 4043982754 8525524075 3114715942 9076995636 1380989336 1594655015 9293088167 8737139735 2759136860 3816927788 7236614335 8578668447 9552059578 7499909718 9838196237 2254194950 3148465371 4045118207 9410171873 6182429211 7510890257 7718095242 3008023923 3043182599
11 3553267657 5428633631
4834 2087558913
60 8293240351
2 2354147811
2 2107077341
4441003753
1924606741
885578341
56743699
22393141
7945261
6064921
5853343
140171
77291
33013
24001
18341
7151
5573
3557
3407
2621
2269
1511
1049
263
127
11
7
5
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.526157%

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 = 6 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₁= 70395532 2043241154 3317920568 1067768336 8019862456 5207799172 2159501068 5233216761 0622637380 9991925095 9993073376 5884182036 0811643462 6420489481 4923723144 0453912310 1556925213 4553037234 4499264709 5243350781 4342452499 3204555939 8118003206 1775270400 5338925360 8801397359 3838877965 6578099822 8673262554 2582077522 2129807075 4065853288 9799349787 6707440133 9256374936 3539998610 3566043575 6232407581 7417146065 2374243165 4349646934 9330184632 6902399096 0128979882 3403550779 1379195553 7730304756 5703933918 3488898657 2890504299 4735900525 2221816104 9357603032 9347503144 7905076196 6104391130 9229577018 4697955288 2368690597 2977859378 7778480745 5996303671 6842914180 8116893826 8754939696 7757572069 4692654739 2168776109 9318545746 3224122841 3557332615 8965652742 3740191306 5087458344 6893839985 8468575738 4539502532 4698258783 9858727560 3197847156 4978522806 9674178509 9133139937 8413348202 1433591199 1834364614 7314412679 3821462284 3577612976 2249523465 5965877637 7306904468 9345936024 5019653142 2609267961 9393844089 5691688868 6745058230 5571609151 5469987596 3163780758 1507453938 5197129215 0080583239 3018124059 7725954452 4950281527 4911407012 4948324882 8102148616 3028789555 2251277829 1048616102 0712750643 4514173110 3465775848 9043456798 6801644295 8887153111 5551462111 1213388140 7816982184 2841435081 8248501692 7592128165 2609235469 4666583123 8726486298 4422111424 7248566649 5449255791 7024217289 5798241216 8499559426 1263749218 4214310973 6979045470 2145837058 8678535494 6536056327 1557652283 0470117437 5654865567 7834955639 6894579449 6988079606 4915211551 1453224679 5576700561 8836148142 3066520443 5396614533 9895006590 1991909628 2849855528 7095068189 2304489068 9916808091 7526636262 8467285393 9654320288 3894679681 0171786650 8043165270 5253154927 6826277312 2839828958 1399340030 8378182663 1536281046 0477288046 2830908749 0490586330 8945998812 7684417759 0709478030 7952888445 1711557541 7783609900 1912331645 9716729224 9371872600 4902040659 3369615424 1252426316 2526791537 1225290409 3929593525 4948123761 1811657793 2109466310 3506965971 8808954362 8711897573 1589996879 9052949016 8279302907 2875943196 0367862574 2852106144 5898480079 7045077866 5302909879 6179409120 4374160651 3476157274 9317213183 6837184160 6168118234 0292998835 5500295185 4424579654 0984014448 5009713428 5930697727 1077728626 2313774803 2949479386 3848651858 7011008813 4561520407 7953179432 9059794408 2143960758 0292661204 3969466633 3760444123 6515537088 1534359269 1418795360 6714926001 9405898125 8157623497 2243914739 9450363066 0855607550 8620384757 7049375814 6423761785 6156152745 1321334849 9351796502 2705390589 8135840260 9423764378 0011293241 8990647029
c₂= 61271328 5534813490 6446423925 0069494646 8101360455 3274576971 0292800068 7017803339 8911431819 4017230051 2064584560 3725338685 7923750706 1131412931 0090591063 6437936411 5736170937 6989077055 3393938927 0595331835 6096954288 7590490019 2807850407 8487308998 2206304312 0997080929 7224618638 1794768916 1318175287 6315730506 4136668783 3361453872 2488229557 6530583558 6770827448 7091095292 0616757991 0457526498 5038273943 6830445865 5319681141 1108628593 0876571876 3540882487 0497751867 9809166042 9708081389 3000408721 6948667263 4967242891 6922027228 0626804760 0063716065 9525741297 6946412424 7335856035 4265891031 5907358674 0743035532 2820799484 6127645780 4451203308 4964643399 7888247935 4183329446 6190699619 7672594549 5861272516 8713248244 5013300634 9499254342 2761952637 2442941843 7139717921 5462161355 7704310765 4234939482 3146880154 9446831200 7325312775 6931565021 1234560309 3364445152 5140605891 8819385530 9411176582 9049947967 2222431639 0575786976 0990464603 4529249432 4620089698 9490289165 5549485541 7303812571 9124300523 5030722049 8632607305 3528784389 1134673381 6754835916 5285806898 4581485206 8053399951 4102422570 7810556821 7696091866 7466104663 7396575674 6226360130 1091146700 6707870188 6593187355 1037223086 2335403237 4465662910 4501442842 5279477237 3086897730 7332530002 7773803242 5914643487 4878241571 8093977225 4679481799 1473105210 5995194060 8052289537 2158998353 2452022787 7972480867 3909608464 2374748047 4921490545 9051069720 2116518150 1387463979 1017995923 1148229800 8258390139 5535397480 6916594513 2222094791 8573992710 5882226082 8918123720 4324560966 2393814768 1170803967 1381201302 8153705454 9685902053 4526449817 9233978661 8660864456 6271968353 4014163805 1505256558 1806400081 7762147117 7461777027 5548353906 2930739001 7928050453 1195871413 0616209479 0003320384 6283309797 8179042655 9179144180 3776479633 7376312717 0732839123 3828708919 6997554982 7441843241 3029176323 0745917288 8069967748 7871727176 1305746663 3750812595 4501678599 5968685954 6792536839 4112582001 8380557500 2890976730 0718761850 1880155410 1053821703 9499735447 9258397872 5540489815 9868020085 2313473088 7307438751 2917700062 9040544267 1669438413 6614252309 5161315270 3536183755 7013575277 1470710579 9864285869 8478264887 6536476588 9685704983 5465701685 9042776738 2627387358 7454196729 0876562492 0673890638 7719493124 4918843547 2951817604 3286149646 2561709899 8878389103 7820353147 0059616739 3616045233 5563929404 8267082459 4689426490 5812084413 1741970591 3882360360 1931199637 1557426080 1781532011 2196169722 1066825862 1165737352 6399417855 4195826075 4961646988 3948423552 2656747838 4000835766 8077756702 3735641781 0251856982 1499581840 2789345591 0057502687 3760152748 7584136657 4158518531 5982360222 2827524064 4685169116 2443049569 4918871250 3022282436 9541667680 1002306949 3318022707 4527851376 8905845764 7303691219 0997697668 4864093644 8443695897 3482303279 8364468235 1780226887 0451323478 2819880393 6317259749 2781692630 7751684820 4038840198 0707113276 0044832023 1636481419 2568265129 5051847306 1006511503 8941720387 7176527575 2442586020 5168413555 3000857209 7800454485 4684734608 2155712662 5548953141 4929281414 5033853121 2384478542 0092290072 7481949547 3325355347 4520843939 5287277333 3660188760 7588256595 8774877565 8431424672 8685640992 6630107949 9628072666 3580631091 6902795386 0443171962 2287749748 0282680460 7483761491 4415136147 5256460462 3701154623 1547125286 0705048406 8261304514 6924398032 3347238075 2429808760 5767802745 2009690067 0995412065 4664997096 4697334922 7009473468 2164325760 0488553257 7567490830 8038059783 7837510564 4858033704 6775756012 2943400134 1299191201 6685514907 5869009110 2413100259 8569149999 9767646748 7704219256 0794349092 5719107134 2686989441 1055216943 9751951978 3082950899 3130105447 8969719530 9225608943 0000559468 0569694678 8868883052 8591164991 6227334709 7898753086 4326789849 3247779789 6762761049 6863436204 6774729064 4966774091 1923489096 9560720489 0118796176 5139334650 7484749526 9269279211 8472280656 2027439300 0302523787 5188021089 7450713935 6214741958 9454065288 0292241581 7728831094 6786789850 8643212654 3622015000 6612906610 8325666068 7578166065 7639851276 5478731545 5961763072 9531437760 2028832088 5394845455 4719262304 8079913889 7261887487 1792822633 6344759505 7888179877 0160115590 2112238874 8496766081 6934335793 9121253473 9647945013 9520603530 6520853072 9735898098 1595211712 2351800794 7237846217 1131407223 2776917711 9839443533 9295516179 3324498429 4657117369 6467876122 2830029272 8393096246 4985126836 6602720135 2347093667 2303807329 7707442133 4324138367 0942119616 1801192772 9698289782 5330165391 9900975098 6322106185 1321237448 9438162630 1044181152 4828844412 2965094601 4818336240 8778919317 9693737259 6281662676

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 ≡ 56 (mod 63) 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 = 4007 significant digits (4000 digits displayed)
Input file is:  IO\0DE40A3D.cin
Certificate file is:  IO\0DE40A3D.chg
Found values of n, F and G.
    Number to be tested has 9304 digits.
    Modulus has 2468 digits.
Modulus is 26.52615731% 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 = 18, u = 8. Right endpoint has 1901 digits.
        Done!  Time elapsed:  55208844ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1877 digits.
        Done!  Time elapsed:  23156047ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1867 digits.
        Done!  Time elapsed:  23943078ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1855 digits.
        Done!  Time elapsed:  33980219ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1841 digits.
        Done!  Time elapsed:  33638906ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1825 digits.
        Done!  Time elapsed:  36894891ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1807 digits.
        Done!  Time elapsed:  306457531ms.
    Running CHG with h = 17, u = 7. Right endpoint has 1787 digits.
        Done!  Time elapsed:  343048500ms.
    Running CHG with h = 16, u = 7. Right endpoint has 1763 digits.
        Done!  Time elapsed:  64443422ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1747 digits.
        Done!  Time elapsed:  35246937ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1741 digits.
        Done!  Time elapsed:  35323313ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1735 digits.
        Done!  Time elapsed:  34980812ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1727 digits.
        Done!  Time elapsed:  34856891ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1717 digits.
        Done!  Time elapsed:  33981859ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1707 digits.
        Done!  Time elapsed:  33241360ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1694 digits.
        Done!  Time elapsed:  32597546ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1679 digits.
        Done!  Time elapsed:  30689719ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1662 digits.
        Done!  Time elapsed:  22007641ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1642 digits.
        Done!  Time elapsed:  22896578ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1619 digits.
        Done!  Time elapsed:  28373625ms.
    Running CHG with h = 15, u = 6. Right endpoint has 1592 digits.
        Done!  Time elapsed:  31540047ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1560 digits.
        Done!  Time elapsed:  20164344ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1551 digits.
        Done!  Time elapsed:  20823906ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1540 digits.
        Done!  Time elapsed:  21333547ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1527 digits.
        Done!  Time elapsed:  22347640ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1512 digits.
        Done!  Time elapsed:  5682141ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1493 digits.
        Done!  Time elapsed:  6633422ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1471 digits.
        Done!  Time elapsed:  3739547ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1444 digits.
        Done!  Time elapsed:  23620703ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1412 digits.
        Done!  Time elapsed:  28234031ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1371 digits.
        Done!  Time elapsed:  2644875ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1360 digits.
        Done!  Time elapsed:  1459844ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1347 digits.
        Done!  Time elapsed:  1223281ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1330 digits.
        Done!  Time elapsed:  988484ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1309 digits.
        Done!  Time elapsed:  1327657ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1283 digits.
        Done!  Time elapsed:  1244172ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1247 digits.
        Done!  Time elapsed:  1064062ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1200 digits.
        Done!  Time elapsed:  836563ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1146 digits.
        Done!  Time elapsed:  561734ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1127 digits.
        Done!  Time elapsed:  806812ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1103 digits.
        Done!  Time elapsed:  856141ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1069 digits.
        Done!  Time elapsed:  812891ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1018 digits.
        Done!  Time elapsed:  785422ms.
    Running CHG with h = 8, u = 2. Right endpoint has 943 digits.
        Done!  Time elapsed:  182390ms.
    Running CHG with h = 7, u = 2. Right endpoint has 927 digits.
        Done!  Time elapsed:  167344ms.
    Running CHG with h = 7, u = 2. Right endpoint has 916 digits.
        Done!  Time elapsed:  168094ms.
    Running CHG with h = 7, u = 2. Right endpoint has 899 digits.
        Done!  Time elapsed:  168937ms.
    Running CHG with h = 7, u = 2. Right endpoint has 875 digits.
        Done!  Time elapsed:  171891ms.
    Running CHG with h = 7, u = 2. Right endpoint has 838 digits.
        Done!  Time elapsed:  170531ms.
    Running CHG with h = 7, u = 2. Right endpoint has 782 digits.
        Done!  Time elapsed:  161094ms.
    Running CHG with h = 7, u = 2. Right endpoint has 699 digits.
        Done!  Time elapsed:  164703ms.
    Running CHG with h = 5, u = 1. Right endpoint has 558 digits.
        Done!  Time elapsed:  24125ms.
    Running CHG with h = 5, u = 1. Right endpoint has 333 digits.
        Done!  Time elapsed:  14266ms.
    Running CHG with h = 5, u = 1. Right endpoint has 58 digits.
        Done!  Time elapsed:  22671ms.
A certificate has been saved to the file:  IO\0DE40A3D.chg

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

Testing a PRP called "IO\0DE40A3D.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=3.172204895 E-493 at X, ratio=2.404157831 E-550 at Y, witness=5.
Pol[2, 1] with [h, u]=[5, 1] has ratio=0.3989820506 at X, ratio=9.97252049 E-276 at Y, witness=11.
Pol[3, 1] with [h, u]=[4, 1] has ratio=0.00005783850488 at X, ratio=6.93558104 E-226 at Y, witness=2.
Pol[4, 1] with [h, u]=[7, 2] has ratio=4.345868278 E-143 at X, ratio=6.639368862 E-282 at Y, witness=2.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.734784381 at X, ratio=1.902663093 E-167 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.4859387520 at X, ratio=5.864386140 E-112 at Y, witness=7.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.634184782 at X, ratio=8.12529902 E-75 at Y, witness=2.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.1181096203 at X, ratio=3.346331925 E-50 at Y, witness=5.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.4858927868 at X, ratio=1.367278799 E-33 at Y, witness=2.
Pol[10, 1] with [h, u]=[7, 2] has ratio=0.4774573024 at X, ratio=1.131648825 E-22 at Y, witness=2.
Pol[11, 1] with [h, u]=[8, 2] has ratio=0.3090239974 at X, ratio=1.929621954 E-33 at Y, witness=7.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.1878097415 at X, ratio=6.176213006 E-226 at Y, witness=2.
Pol[13, 1] with [h, u]=[9, 3] has ratio=1.185468155 E-51 at X, ratio=4.411016984 E-153 at Y, witness=5.
Pol[14, 1] with [h, u]=[9, 3] has ratio=6.99231025 E-35 at X, ratio=2.946514483 E-102 at Y, witness=3.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.03480642215 at X, ratio=1.258902807 E-74 at Y, witness=5.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.1021373207 at X, ratio=3.001547352 E-56 at Y, witness=2.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.1277595987 at X, ratio=1.973351050 E-215 at Y, witness=2.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.3554679190 at X, ratio=1.358283975 E-191 at Y, witness=7.
Pol[19, 1] with [h, u]=[11, 4] has ratio=3.680289159 E-37 at X, ratio=2.145610139 E-144 at Y, witness=7.
Pol[20, 1] with [h, u]=[11, 4] has ratio=1.503956452 E-27 at X, ratio=2.747927995 E-105 at Y, witness=3.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.856546003 at X, ratio=3.532674355 E-84 at Y, witness=11.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.605464152 at X, ratio=1.673083203 E-67 at Y, witness=7.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.2063630369 at X, ratio=3.227634135 E-54 at Y, witness=2.
Pol[24, 1] with [h, u]=[11, 4] has ratio=0.1063524877 at X, ratio=1.924876901 E-43 at Y, witness=3.
Pol[25, 1] with [h, u]=[13, 5] has ratio=1.649003034 E-38 at X, ratio=7.46138199 E-207 at Y, witness=3.
Pol[26, 1] with [h, u]=[13, 5] has ratio=0.1212654133 at X, ratio=6.235962288 E-161 at Y, witness=13.
Pol[27, 1] with [h, u]=[13, 5] has ratio=0.0660459040 at X, ratio=3.395749749 E-134 at Y, witness=2.
Pol[28, 1] with [h, u]=[13, 5] has ratio=0.1304349728 at X, ratio=5.462008330 E-112 at Y, witness=7.
Pol[29, 1] with [h, u]=[13, 5] has ratio=0.2256492224 at X, ratio=1.628580385 E-93 at Y, witness=2.
Pol[30, 1] with [h, u]=[13, 5] has ratio=0.1622928597 at X, ratio=5.06949207 E-78 at Y, witness=2.
Pol[31, 1] with [h, u]=[13, 5] has ratio=0.517216592 at X, ratio=4.138056570 E-65 at Y, witness=5.
Pol[32, 1] with [h, u]=[13, 5] has ratio=0.1629884837 at X, ratio=2.172002735 E-54 at Y, witness=3.
Pol[33, 1] with [h, u]=[13, 5] has ratio=0.2055820036 at X, ratio=2.070284407 E-45 at Y, witness=2.
Pol[34, 1] with [h, u]=[15, 6] has ratio=0.1465651207 at X, ratio=2.222027749 E-191 at Y, witness=7.
Pol[35, 1] with [h, u]=[15, 6] has ratio=0.1096952064 at X, ratio=3.680976357 E-164 at Y, witness=5.
Pol[36, 1] with [h, u]=[15, 6] has ratio=0.4362233852 at X, ratio=9.63969781 E-141 at Y, witness=11.
Pol[37, 1] with [h, u]=[15, 6] has ratio=0.1086308610 at X, ratio=7.023914398 E-121 at Y, witness=2.
Pol[38, 1] with [h, u]=[15, 6] has ratio=0.1323780015 at X, ratio=1.297608077 E-103 at Y, witness=7.
Pol[39, 1] with [h, u]=[15, 6] has ratio=0.4991431890 at X, ratio=5.978309446 E-89 at Y, witness=3.
Pol[40, 1] with [h, u]=[15, 6] has ratio=0.05971401292 at X, ratio=2.474112923 E-76 at Y, witness=3.
Pol[41, 1] with [h, u]=[15, 6] has ratio=0.1355540897 at X, ratio=1.678512815 E-65 at Y, witness=2.
Pol[42, 1] with [h, u]=[15, 6] has ratio=0.2653861745 at X, ratio=2.626091467 E-56 at Y, witness=3.
Pol[43, 1] with [h, u]=[15, 6] has ratio=0.2753838562 at X, ratio=2.420750196 E-48 at Y, witness=5.
Pol[44, 1] with [h, u]=[15, 6] has ratio=0.2535516772 at X, ratio=1.775601159 E-41 at Y, witness=11.
Pol[45, 1] with [h, u]=[15, 6] has ratio=0.1144646458 at X, ratio=1.026466914 E-35 at Y, witness=2.
Pol[46, 1] with [h, u]=[16, 7] has ratio=0.02747781064 at X, ratio=1.321178379 E-112 at Y, witness=11.
Pol[47, 1] with [h, u]=[17, 7] has ratio=0.2330114665 at X, ratio=1.778748317 E-165 at Y, witness=2.
Pol[48, 1] with [h, u]=[17, 7] has ratio=0.3520309658 at X, ratio=7.30293125 E-145 at Y, witness=5.
Pol[49, 1] with [h, u]=[17, 7] has ratio=0.01437257310 at X, ratio=7.83085062 E-127 at Y, witness=3.
Pol[50, 1] with [h, u]=[17, 7] has ratio=0.0773567885 at X, ratio=4.330049726 E-111 at Y, witness=11.
Pol[51, 1] with [h, u]=[17, 7] has ratio=0.2099927951 at X, ratio=2.596111685 E-97 at Y, witness=5.
Pol[52, 1] with [h, u]=[17, 7] has ratio=0.1776814246 at X, ratio=3.175539387 E-85 at Y, witness=11.
Pol[53, 1] with [h, u]=[17, 7] has ratio=0.1211640769 at X, ratio=1.300031901 E-74 at Y, witness=2.
Pol[54, 1] with [h, u]=[18, 8] has ratio=0.1860350619 at X, ratio=1.440351902 E-186 at Y, witness=11.

Validated in 191 sec.


Congratulations! n is prime!

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