Primality Certificate for (8871^2341-1)/8870

Andy Steward	9,239 digits	13 February 2010
Primality Certificate for (8871^2341-1)/8870
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.825302% factorization of N-1:

From	Factorisation
8871	3 · 2957
Φ₂	2 · 2 · 2 · 1109
Φ₃	7 · 31 · 79 · 4591
Φ₄	2 · 13 · 3026717
Φ₅	5 · 11 · 101 · 1471 · 27481 · 27581
Φ₆	127 · 619573
Φ₉	19 · 49663 · 516474547743307789
Φ₁₀	70061 · 88382245481
Φ₁₂	6192846443424241
Φ₁₃	1223 · 47087 · 3163196999 · 789990752071 · 1650608907546181337
Φ₁₅	1801 · 278881 · 851410291 · 89672677938211
Φ₁₈	37 · 937 · 143872471 · 97704925489
Φ₂₀	p32
Φ₂₆	p48
Φ₃₀	151 · 4231 · 19531 · 983223601 · 3126315764371
Φ₃₆	73 · 3673 · 11593 · 244873 · 4302073 · 592290037 · 122455479118826341
Φ₃₉	131899 · 252608227 · 40415478871 · p71
Φ₄₅	p95
Φ₅₂	13 · 53 · 157 · 1613 · 4057 · 140401 · 518129 · 504758123285589207373 · p52
Φ₆₀	61 · p62
Φ₆₅	131 · 2341 · 66431 · p180
Φ₇₈	79369126235101 · 44283443381352631 · p65
Φ₉₀	271 · 16651 · 6714080501941 · p76
Φ₁₁₇	6968554262983 · c272
Φ₁₃₀	911 · 7151 · 16658981 · 254029885022412813098244851 · p150
Φ₁₅₆	313 · 1249 · 5447644021 · 14815713604849 · 298555851306337 · 18120856655034320943515293 · c122
Φ₁₈₀	181 · 354421 · 2972881 · 1809290353141 · 19699267774141 · 29504149347061261 · p134
Φ₁₉₅	491551981545337831 · c362
Φ₂₃₄	907191793 · 96645444013 · c265
Φ₂₆₀	77857362181 · 8484430117842221141 · c350
Φ₃₉₀	24251371 · 620361896054083249166000941 · c345
Φ₄₆₈	12637 · 36933157 · 21235149937 · 15591567329677 · c534
Φ₅₈₅	1171 · c1134
Φ₇₈₀	16910401 · 56685674761 · 10299962241081107401 · 179049712822245341701 · p701
Φ₁₁₇₀	6410025575703358188095881 · c1113
Φ₂₃₄₀	577981 · c2269

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

5 7982738277 6691852853 8955640644 5577572977 6423280296 7152203644 6066648893 2549545397 2001921758 8987303245 2535393988 3804930083 8600648913 5287427622 0537800098 8043942846 3581579075 5509773555 0625149287 4839222329 7396066555 6024966844 3206340014 7199054581 4063990311 3240869884 8606627188 0136633006 5914655058 0186524378 9243832098 4579058512 5203275293 2826132594 6628137343 6221850521 0484543453 0942415827 0332674781 6855539142 8006392366 4158125996 3103240413 3608292023 9710841271 7665878275 3376085679 7545392768 6486473288 7406450249 4323174287 1459026744 0172879062 2461756833 7280936163 7441993708 4844990924 8729371868 8540235345 2995958163 7641573849 4564595144 1073226562 7988495507 5642673395 6415152763 7230457325 9552866060 8483543375 7148220861
1561677470 5279837209 8145591816 5224216806 6079441710 7807180253 4339051303 4767817188 3273954350 6495662854 9567913713 4620327502 8148792085 2864515834 6396704933 5803126886 2683578565 7295823281
1154288471 5420222692 7810206536 2114626689 2779738721 9743881635 2973990819 4247117987 4325881214 1155129427 7880296350 3480638455 3259673714 1462984591 5097954591
1586 5976545761 2197903522 2563474633 4168215533 6178490356 0642241290 4133873632 6786592213 2308213039 0696210789 1964342958 2718607896 2701494461
56408 1558910375 7146952273 9961952901 1855452799 7578195236 6868162505 4006140679 1088296367 8256724641
186185 4531285000 8582165151 0512675278 8367991030 6239262861 9307843339 3806996281
4 1884778193 2520308171 4897698523 8160392727 7428122478 6993859180 9484933527
16050 8439801678 9357669538 9322593903 4182637039 1686553136 2125717011
24 1119002569 7705373397 5255795751 6631765183 6959750586 3619820501
21 7016236800 1584929635 2141672822 7982821057 3719627461
23747724 2303947599 1594014167 8514337390 2207446621
38 3513475591 7609242538 0440499681
6203618 9605408324 9166000941
2540298 8502241281 3098244851
181208 5665503432 0943515293
64100 2557570335 8188095881
5 0475812328 5589207373
1 7904971282 2245341701
1029996224 1081107401
848443011 7842221141
165060890 7546181337
51647454 7743307789
49155198 1545337831
12245547 9118826341
4428344 3381352631
2950414 9347061261
619284 6443424241
29855 5851306337
8967 2677938211
7936 9126235101
1969 9267774141
1559 1567329677
1481 5713604849
696 8554262983
671 4080501941
312 6315764371
180 9290353141
78 9990752071
9 7704925489
9 6645444013
8 8382245481
7 7857362181
5 6685674761
4 0415478871
2 1235149937
5447644021
3163196999
983223601
907191793
851410291
592290037
252608227
143872471
36933157
24251371
16910401
16658981
4302073
3026717
2972881
619573
577981
518129
354421
278881
244873
140401
131899
70061
66431
49663
47087
27581
27481
19531
16651
12637
11593
7151
4591
4231
4057
3673
2957
2341
1801
1613
1471
1249
1223
1171
1109
937
911
313
271
181
157
151
131
127
101
79
73
61
53
37
31
19
13²
11
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.825302%

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 = 17 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₁= 29120477 0220812392 0396500920 3033421573 9101570749 9735690331 3703799610 7813182781 9011399170 6946701849 1815506821 9867211381 7793975500 2441401495 6240648386 6164170405 1032324901 3954669599 9097027214 7364333386 1316345515 7508091070 9870221318 6462904125 1030125927 5495790401 9132868978 1872211257 4268537171 5009776544 1106373638 3968436012 0561994474 2370735941 6810351280 3423663139 1135095168 3501908551 2661889372 1152518092 9773875939 9130037829 3392180367 0638003971 9901533487 7397905301 2505600346 2274484062 1997265563 2010248213 2880321887 7048700334 5611762466 0435545205 6475179945 4698860559 6839350529 6101451096 9934174988 9343335479 5697528123 8011696480 6786361311 2804912038 1840089756 1555857300 5444687652 5860510786 1989497672 7598289704 5405827625 4371918815 4297719779 4187687895 6802618347 6240869157 8413187245 5565984214 3266416254 4958721033 3311643735 6832504650 5789791253 3937581941 0680918852 6527717315 4300688811 5491628099 2812992368 3203386331 3166292203 0945569014 3343685921 0777498960 6870373424 3529010559 1888671897 5028676025 3891722807 2333632976 2982049592 9774293913 5842877677 9017758036 8836206647 0632139189 6748995945 4267053595 4958085549 9047686383 6133794910 7622978998 1128274274 6453130739 3413734670 2897141829 2337617486 9412456475 7805382428 5768150585 1429303845 2023080287 7103720183 7413569451 0122487363 2086205126 6325094526 5544371370 0844376118 2615029489 6284698629 5407563934 7733187971 8891302742 8437015960 4740789518 0293644442 5849228259 6136308738 9905809116 8590731480 5314053336 7408428022 6575559891 2728757150 9764749765 3550032042 3430419215 9712084918 3952075443 7518090249 8681044043 0371296099 5794971552 3598663662 3894723908 1791679979 1918963185 5091250797 2985083151 4214624958 5358744729 1531257647 7837474454 9025851495 8143750107 1140078333 4996906938 9995244277 3694075548 7324045410 3214514533 2118385891 9245806815 5536599761 8979893769 1053291273 5573303699 1412882515 2303293762 0719126580 7142944123 2184868524 6846102404 5145477764 3369879060 6078884909 9741982153 0641202997 4120245515 8791684787 7797206373 2682539438 5355834892 2233724355 2499045646 2428265157 1772590616 3660676424 2963495572 0967549189 0898957107 8171718742 2366717104 0537425018 3400449342 4346912722 6176892148 9025062648 0070849231 5675470514 1354731123 6077488224 4993111433 6880645387 2283232019 3576497663 3387706618 8496655847 9212019621 0569161179 2212219024 7426833997 8355621440 9075709050 2173099250 8859539454 8668603138 8209586949 1912312155 1212224266 1602491180 9869771642 2928256797 5118201205 9512688811 8634672864 5277910792 5491280028 0628532737 9202056685 1445233838 7517810583 0918117276 0240577430 3922932191 1915933313 5953005081
c₂= 75 1221570543 5688643089 6703538706 4817644901 6392413127 1071932099 8597526423 6396948143 3717619926 8178284663 6395818196 2616110392 2725110848 1846428671 0748813766 1685002546 0390266829 0358300861 6728476151 7588340999 2411609653 6375548539 5644901055 1739847457 9028697699 3148919577 0456893505 5891771752 9217505108 4829320728 3971258927 3337613467 9594537656 2109632150 1377798683 3745686427 5819508736 6584220610 6320060618 6948116547 0575116814 2346953512 0415304402 5298272890 8087222225 4685222504 1460554231 3155354574 3358386400 6365433410 7181732551 3011527081 0435429252 3969972699 3979979766 6927956290 8734798801 1120746492 2739386356 3100859794 0829590262 4457123177 7469451814 1225483156 8304208037 8432882946 3875332592 2855048803 8241114702 6101733603 1064653547 8949230705 5521163678 2162200044 5750917273 5820567512 3624846075 5065549843 8615459005 3958129459 6579636652 1006654543 5449816680 8374869745 5694821705 6685742019 9339829136 1146721286 0757678719 2512001824 6248498982 9753074987 5899808569 6379354685 3211327904 3225097916 3884194728 9382532626 1846866851 3693284076 2955261293 2874263394 6367770680 6940813202 1784003486 4451163797 0255515009 9590068249 2302466233 2051308270 1784207032 8124915665 4034667298 8892477861 9938391259 8544345706 9454660796 8646878163 5264921105 5560867870 0480876077 9018159519 5997851249 0188123433 1049215519 2571054975 6185837063 7578734779 4035530767 2576977549 6507059643 7342293851 6255784097 6707046604 9564429023 2256786454 0722597799 0487165991 8313338221 8734181368 5864662999 3332119934 5331405825 8369549352 4527251584 6782543774 2620077799 4960147678 3350421399 3503513895 5763435178 9245579610 8654990273 7537187159 8342562395 8139857694 1320706178 2438277532 9796119876 9530243390 0729662991 9724115234 9383157530 8679348251 4138753995 2641469058 5274501280 8637925632 2835357579 0527740236 9929906006 8803994112 2432513119 5285861269 8204513821 1177407906 4694625440 2465218265 0990599186 9372748141 2736735585 7140128410 6104214095 0315372255 5808811745 5937981856 2037953758 9485317298 0171371701 8470833122 7535570962 8407664903 7789383708 0374407267 3131268741 1845208617 6135420018 0479353150 5548420779 4799537956 4265571781 2885631296 2045639515 4676100667 2728852535 9588459930 8756677264 8622451356 7629860792 9741982286 3546837283 1657877703 2729337820 7417884566 5402023739 3243239142 1791477726 7298173832 8249712799 7671979902 1643974003 0305917474 6634691105 0766588984 7131355710 9470573558 6652962357 3108512192 1175958763 8857372131 5540804375 0487360028 3596686297 3310360122 3177862407 6408620126 4356397353 9042920841 8637833623 2870878451 7037376400 1213152713 7116884124 4864795619 8101500173 2495456599 9129703629 0758489401 1715455310 1688927956 9865164501 6948228637 0436151365 3153149207 7960647815 7104043273 7589196453 2386262129 2525044983 1695945555 3033100019 3623467945 0472268580 5878190023 2657597516 7156503342 2278273255 4034907790 1513239046 4548791018 1626877590 8045052227 0725263893 9758234494 7457637263 3751047596 4743147763 4090829636 7177969932 4149387660 8504163456 2436454051 2758758244 9852831678 8376495589 2376553415 9753422341 6197318425 5615054977 8856141230 8085711149 1181865655 4424815490 1187512007 9093232262 5046376984 2017532811 5506551801 5099066891 6045903037 1828440474 7313172149 9649024052 0833716793 2476157633 4755519672 2384311532 6327003677 9011467761 7956264018 1424924268 9200096014 4894485486 9301482111 0306342309 5943586096 6737275576 2791804834 5108641801 9092615823 8351960035 5778101943 4229072499 0508264765 5865526445 5054305333 0531019991 5789743567 8115013285 2072001402 7161366809 1552331667 0827128572 5781657099 7266422165 4146356455 6095035003 4636190348 5884784592 6074415650 1542289193 3155690824 4390961005 3759413114 2242473983 4244699940 1418024622 2928378311 5977821532 9153739228 9627940253 3956608043 0024314470 9271314095 5755760228 8831766306 9633912287 7161187422 3261041948 9335330871 0925408371 1829603682 4542895636 6623197268 9859875531 9595591529 3765372544 1271044483 3477216667 4117394022 8613921979 9899860217 2574110584 1397241598 3738912594 6311464089 1504333856 9171420708 0130849534 6714239572 1953535694 8130866763 1456966871 2045549897 3808795216 3161415858 8877832854 2238239824 3956493142 6080571365 1972143781 3622673304 2563514722 4993480273 6691093817 9841187665 8676176641 2933139702 9245223633 5913628871 6358146932 4282005333 9698885282 6980060342 3612635452 0536823271 6810327097 7593193122 0112767279 4619960202 6164609107 0966874806 0270763757 1263698429 7428779118 2391282067 6966282728 5772214762 9783671943 8911708831 7262904201 2155277181 0959830046 7960314869 6440112801 3774623070 0219518090 5281193812

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:

realprecision = 3756 significant digits (3750 digits displayed)

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

Input file is:  IO\22A70925.cin
Certificate file is:  IO\22A70925.chg
Found values of n, F and G.
    Number to be tested has 9239 digits.
    Modulus has 2479 digits.
Modulus is 26.82530219% 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 = 14, u = 6. Right endpoint has 1804 digits.
        Done!  Time elapsed:  3726063ms.
    Running CHG with h = 14, u = 6. Right endpoint has 1785 digits.
        Done!  Time elapsed:  3752859ms.
    Running CHG with h = 14, u = 6. Right endpoint has 1762 digits.
        Done!  Time elapsed:  4555469ms.
    Running CHG with h = 14, u = 6. Right endpoint has 1740 digits.
        Done!  Time elapsed:  5719391ms.
    Running CHG with h = 14, u = 6. Right endpoint has 1716 digits.
        Done!  Time elapsed:  6874453ms.
    Running CHG with h = 14, u = 6. Right endpoint has 1690 digits.
        Done!  Time elapsed:  7541234ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1663 digits.
        Done!  Time elapsed:  1089469ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1649 digits.
        Done!  Time elapsed:  1084578ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1632 digits.
        Done!  Time elapsed:  1093750ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1613 digits.
        Done!  Time elapsed:  3611734ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1589 digits.
        Done!  Time elapsed:  1810625ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1561 digits.
        Done!  Time elapsed:  1049000ms.
    Running CHG with h = 13, u = 5. Right endpoint has 1526 digits.
        Done!  Time elapsed:  3327547ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1485 digits.
        Done!  Time elapsed:  357375ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1478 digits.
        Done!  Time elapsed:  1133547ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1469 digits.
        Done!  Time elapsed:  1176313ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1458 digits.
        Done!  Time elapsed:  1229234ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1444 digits.
        Done!  Time elapsed:  1276297ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1426 digits.
        Done!  Time elapsed:  1334890ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1404 digits.
        Done!  Time elapsed:  1435860ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1376 digits.
        Done!  Time elapsed:  1496219ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1342 digits.
        Done!  Time elapsed:  1632781ms.
    Running CHG with h = 11, u = 4. Right endpoint has 1298 digits.
        Done!  Time elapsed:  1877359ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1244 digits.
        Done!  Time elapsed:  265688ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1234 digits.
        Done!  Time elapsed:  244093ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1220 digits.
        Done!  Time elapsed:  238391ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1201 digits.
        Done!  Time elapsed:  243203ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1177 digits.
        Done!  Time elapsed:  234031ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1144 digits.
        Done!  Time elapsed:  265219ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1100 digits.
        Done!  Time elapsed:  269719ms.
    Running CHG with h = 9, u = 3. Right endpoint has 1041 digits.
        Done!  Time elapsed:  269375ms.
    Running CHG with h = 7, u = 2. Right endpoint has 961 digits.
        Done!  Time elapsed:  58406ms.
    Running CHG with h = 7, u = 2. Right endpoint has 942 digits.
        Done!  Time elapsed:  59610ms.
    Running CHG with h = 7, u = 2. Right endpoint has 915 digits.
        Done!  Time elapsed:  61593ms.
    Running CHG with h = 7, u = 2. Right endpoint has 874 digits.
        Done!  Time elapsed:  74969ms.
    Running CHG with h = 7, u = 2. Right endpoint has 812 digits.
        Done!  Time elapsed:  89109ms.
    Running CHG with h = 7, u = 2. Right endpoint has 719 digits.
        Done!  Time elapsed:  60391ms.
    Running CHG with h = 5, u = 1. Right endpoint has 580 digits.
        Done!  Time elapsed:  7922ms.
    Running CHG with h = 5, u = 1. Right endpoint has 355 digits.
        Done!  Time elapsed:  7328ms.
    Running CHG with h = 5, u = 1. Right endpoint has 80 digits.
        Done!  Time elapsed:  12500ms.
A certificate has been saved to the file:  IO\22A70925.chg

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

Testing a PRP called "IO\22A70925.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=5.986261358 E-472 at X, ratio=2.626323055 E-551 at Y, witness=17.
Pol[2, 1] with [h, u]=[5, 1] has ratio=0.590388665 at X, ratio=6.570953930 E-276 at Y, witness=5.
Pol[3, 1] with [h, u]=[4, 1] has ratio=0.03990545929 at X, ratio=2.268929061 E-225 at Y, witness=11.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.02029928351 at X, ratio=8.90322470 E-279 at Y, witness=3.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.2750253449 at X, ratio=4.049880353 E-186 at Y, witness=2.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.696391160 at X, ratio=2.206838917 E-124 at Y, witness=3.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.525486328 at X, ratio=3.562509997 E-83 at Y, witness=2.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.4041042497 at X, ratio=1.372747105 E-55 at Y, witness=3.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.4832654296 at X, ratio=2.101134722 E-37 at Y, witness=17.
Pol[10, 1] with [h, u]=[9, 3] has ratio=2.626385664 E-81 at X, ratio=1.762084604 E-241 at Y, witness=2.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.513253478 at X, ratio=7.711781374 E-177 at Y, witness=7.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.3220345220 at X, ratio=7.44832139 E-133 at Y, witness=2.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.2797826764 at X, ratio=7.50216203 E-100 at Y, witness=2.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.1836378314 at X, ratio=5.22158306 E-75 at Y, witness=7.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.2386839153 at X, ratio=2.075807580 E-56 at Y, witness=11.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.2581303980 at X, ratio=1.155602649 E-42 at Y, witness=3.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.0704401952 at X, ratio=4.319548140 E-32 at Y, witness=3.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.812470600 at X, ratio=1.453392773 E-216 at Y, witness=2.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.0698782975 at X, ratio=1.792982424 E-173 at Y, witness=3.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.0845267486 at X, ratio=7.06441783 E-139 at Y, witness=7.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.2926678755 at X, ratio=2.427775644 E-111 at Y, witness=17.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.3467680011 at X, ratio=3.984236653 E-89 at Y, witness=3.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.1703745647 at X, ratio=1.833695726 E-71 at Y, witness=17.
Pol[24, 1] with [h, u]=[11, 4] has ratio=0.3115878831 at X, ratio=2.655939306 E-57 at Y, witness=5.
Pol[25, 1] with [h, u]=[11, 4] has ratio=0.1224219658 at X, ratio=5.577958714 E-46 at Y, witness=7.
Pol[26, 1] with [h, u]=[11, 4] has ratio=0.2309220842 at X, ratio=6.524928930 E-37 at Y, witness=7.
Pol[27, 1] with [h, u]=[11, 4] has ratio=0.0671811219 at X, ratio=1.160492249 E-29 at Y, witness=3.
Pol[28, 1] with [h, u]=[13, 5] has ratio=0.4332538948 at X, ratio=7.90922433 E-206 at Y, witness=3.
Pol[29, 1] with [h, u]=[13, 5] has ratio=0.3882655297 at X, ratio=1.401970934 E-171 at Y, witness=7.
Pol[30, 1] with [h, u]=[13, 5] has ratio=0.04658314992 at X, ratio=4.427379094 E-143 at Y, witness=2.
Pol[31, 1] with [h, u]=[13, 5] has ratio=0.3829262008 at X, ratio=2.307317970 E-119 at Y, witness=3.
Pol[32, 1] with [h, u]=[13, 5] has ratio=0.1943926503 at X, ratio=1.416035678 E-99 at Y, witness=3.
Pol[33, 1] with [h, u]=[13, 5] has ratio=0.2881866177 at X, ratio=4.525635976 E-83 at Y, witness=2.
Pol[34, 1] with [h, u]=[13, 5] has ratio=0.2702972868 at X, ratio=2.138692689 E-69 at Y, witness=5.
Pol[35, 1] with [h, u]=[14, 6] has ratio=0.1968206242 at X, ratio=6.200785796 E-167 at Y, witness=3.
Pol[36, 1] with [h, u]=[14, 6] has ratio=0.1056311938 at X, ratio=3.406863761 E-154 at Y, witness=5.
Pol[37, 1] with [h, u]=[14, 6] has ratio=0.0780779115 at X, ratio=2.321760448 E-142 at Y, witness=3.
Pol[38, 1] with [h, u]=[14, 6] has ratio=0.2210439657 at X, ratio=8.94500836 E-137 at Y, witness=2.
Pol[39, 1] with [h, u]=[14, 6] has ratio=0.0922592906 at X, ratio=1.516672062 E-136 at Y, witness=11.
Pol[40, 1] with [h, u]=[14, 6] has ratio=3.742613816 E-21 at X, ratio=2.948765750 E-118 at Y, witness=41.

Validated in 12 sec.


Congratulations! n is prime!

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