Primality Certificate for (2008^6781-1)/2007

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

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

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

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 = 23171 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₁= 9652363411 5401383679 6315608194 0801725473 1411145449 1861982359 8012828847 6000649666 6419145711 0892736465 1683461597 7358618928 2629994298 8474369139 2482495503 4203004804 3184033117 7767399864 9301100971 6152995260 9353000038 8130654216 2794653200 4414639950 7524086863 9331250219 6328764880 4689770724 5016416657 9221028947 4001381862 9312892036 0538031986 4477548307 6480668203 3139175225 7992141547 3609848389 2612683572 7470707017 4489138013 3313518126 7908827576 0617452911 3312658528 1900179350 6415929844 7574789494 9631696488 0552043172 7735556449 6544661526 6163522013 9963305064 4541097431 6711068386 3271879093 2271320187 7690884112 4339689010 1330411980 2444266168 7112809969 5933861176 6583742218 6830038005 7384665308 8197393945 2176720415 1916350354 7355982862 3013516427 0700154490 9786964560 2994718067 6104484409 5324642634 1464385197 6556187180 9035652971 2943264949 8964943590 4667785698 4226007640 3812755598 1581058652 6884366123 4563135006 8576882274 2307058088 2608722334 0678153150 7079482592 1937981660 8569171792 2116391518 1646176359 6281882922 7067499072 3999025672 0511473722 5670525359 5810706122 1541117808 0536093653 6512872519 7222150427 5053529105 1463912436 3787741768 9003951435 4748413131 7636277491 4764410579 6785820998 2871992753 2287920899 2324264244 8005747351 5497091828 9399861736 6389740730 2660937233 7291359709 1046280262 5882039410 3522265141 4188687055 5481095731 5660423048 0467333746 2934750805 9497121545 6909017598 3413517526 9726816738 6982422967 3604817498 9842366989 1218759704 7732002774 2831990982 1899578598 6356966310 0385830540 1527307386 6228366435 2080067961 4835095944 9586844943 3232221232 0860958090 2988203852 7020940586 9344623645 1753162233 4596311009 6265032194 7598441561 9183767825 7267830737 0763331734 1876029639 6130409829 3516298477 8510140852 3380805475 1264838187 6100651777 8668718875 0436446428 2359118741 7842952157 4136528752 0289724906 7153456414 3270282995 8243791316 8929754849 7759843796 6965228870 0216079054 4626262787 7699416583 1086451420 9143296685 2808140671 2002737292 0855779261 3015042265 9841821038 3958223397 8289006540 1661864715 3003152702 3992801984 0468575371 4405021353 3973101308 6622883951 2126411551 8238735489 5413573383 4880084588 5722838022 6098208745 5214340718 9752889612 5701784866 4205172856 1362220749 5912924238 6216584027 2133407640 1622131391 1904207264 2148027759 4928071415 8478122591 2749253192 4753792902 0524449025 0142249233 0943901500 5180820559 4167225459 6579981975 0156079680 6754084982 6610876712 5304655325 9403457077 3237818443 8542055379 6905011609 2102382946 4725583758 7609946187 6013038735 5426620951 5630472170 2123368489 4134561590 6417929439 7682267765 2970536568 7738082172 6405762362 7073515342 4117593844 8953549755 3773131668 9161200110 7357640551 0899804550 1839546671 5427052837 3221764097 9810471663 7074651097 3608751230 7740697914 4644258584 7555774089 1384007596 6194724869 9042187127 3842919298 0945313141 0934722657 8129359562 3042908509 8175876036 9819801539 8178090137 5419257707 9693093442 2604940281 5878564641 8602036781 4846532972 2766882582 2860607617 7415654612 2040581406 5328850878 5640768416 5567527987 0646064453 7636489192 9354514500 2128211479 6115579749 3964411668 7894139758 4123870060 7387165958 2464870944 5502923227 7659901694 4453399582 3248764054 1836657146 8892039213 5743226190 7384006182 1723684235 7801133375 9103423194 1659986091 0033961715 2883164990 2319508060 8497522816 2805750967 7833472933 1403586231 8393172144 9765663975 4292448411 5784491116 0983897842 3349391976 3449955811 3531765563 6660637184 5863560033 3215920362 9316559099 8449276724 7082573066 7550547423 0161701714 6088269311 6113948295 0113047768 9053283260 9848062225 9772698189 2304991964 3550237620 1996860824 4869999334 5291596192 0907667127 3855008124 7232688363 2137355102 0423809126 0944610582 9115190795 4540141152 2207155271 8435153628 5305382979 1920756355 2047768354 8567266588 5967508341 9896484700 3753356959 7438642528 5311960129 9679902260 6483590124 8056342686 9196075014 6099221927 4835688110 9496231013 7007782975 1717510726 6584853870 9704253793 8425507729 5907822640 1508111953 2985094202 0193210967 8458209965 8644074468 2101446194 1987600368 3834380305 1588234581 6561155208 9894718743 3079848764 5138014926 2196567828 0964780091 2623094268 0966560621 1412035627 4742580114 2454941240 1031478830 8802559199 5100305612 5746202966 7129690680 0113596766 7863398066 8985485717 6687374879 0827435530 3129316624 7878771686 9525120097 0284205111 7088613804 7006491474 7300566972 9409418212 2469020828 3271380469 2421687247 5964925163 4925457370 9239702414 4680914456 8806228058 6072170232 8923149816 0309912940 1962506476 8862549010 3927750507 0004567743 2945569870 9672314827 8716382390 9661558441 1196787731 8030917576 6839324387 8722174288 4947138632 4363998832 8822367763 8754348026 9121274548 3420401033 8138150546 9227156015 6696194496 4115227376 9801329917 3389987397 6088895092 3373209117 0490729198 7364156566 6447608407 4540483040 3665350775 9793696134 0129744372 9254710778 2325890738 2992304442 4449364761 4686368290 5966436490 3667236662 2290933900 1061215775 5437037598 0037516802 6145953985 8127334857 2244723733 4136429920 7835012234 8059624005 8376349792 9872611536 3528400724 4414151296 6287242018 0567966394 0943636135 2016994074 2353754202 8953030794 3961540194 1984067760 0011240718 0669259881 5405304822 9043738065 6804659200 1112620472 1674631519 6315907538 8701630398 0920465067 6290095178 7733007290 0739108844 0282575477 1754555714 0316532054 6449271517 1660567232 4316757230 7405482278 6519286645 9279081704 8128045708 4173769374 1579087981 6870320709 5947667782 3521286596 4760976245 4272992367 2983394551 5289496002 2234441679 6540962510 2809989900 6689903291 2109722656 7111556258 9040391893 8271438669 8635591905 0265518571 8132995804 7138126372 4827401331 7703873404 8739884083 3499947054 1901729838 1832978251 2816990807 7891502352 5716071763 6285134200 0584237238 2701732160 4585334995 5424058353 9414377728 1403856630 8062207734 2672409976 4461775109 0848864588 4388616139 8136649250 2529981978 2329257987 0991146356 8923823506 9055163679 3705019250 3739209773 9511199972 7532505989 2091600679 1904640592 4989523382 7248078143 3292317339 8386063657 2254756476 4732057132 4701051568 6261819176 9845188282 7515579271 8861634651 9475013062 1733062495 2192672259 6244380515 6791388767 3823727835 6744148306 1550556762 4754925625 2125478152 8708160901 2927568059 7004731570 9525474277 9595347509 5800917080 5419750918 9752522794 3169521157 6731035070 1445871157 2530444814 3919502233 3809310719 7118717293 5924336220 8082316849 8793875646 5362542106 7936858730 3004605596 4271376844 4675641190 5493133706 0933307206 5082088658 5807396272 5235144896 0254581989 1930885381 9288843541 2802043147 0114116068 9688692787 5417287393 3577159815 9127186079 6341526692 2381861948 5376373922 4336650206 1670400497 7352973958 9041276517 3260898687 1836406850 0445261059 1629418697 1126273746 0242031433 0112127219 1143745941 2774047686 5706000879 4144092394 5047171803 4052636151 3626270303 3482513219 4423183179 2513172690 6783422333 8087794975 7132715520 8003452237 6227541770 2080928457 4183832691 8960659796 3261501007 0778148035 2338394905 2969305103 3650449526 2548269760 6015103688 6780020600 6792471523 3420313529
• c₂= 221 1603623785 5622979549 8305623375 6567579786 7780168626 9188127151 5388961387 2488858568 7974149223 9168995082 5931546889 3097807408 6901289580 2131533089 3113619920 5162292658 7221237295 0226115997 8378991578 5708282425 6253138650 4539827973 7158652169 1624393158 5380922209 4430329318 5244248884 4680272383 5484516502 2894964660 8798047529 6220997395 1846538438 1017237970 0504893458 7659735223 8442742579 4770503752 2352451804 7482379486 9750458023 2407872964 2057725303 7134522723 5333318046 1061707095 9872841157 6122844670 5983587679 9696876743 9988154012 7793359681 7794850811 6264249037 7005102923 6134346260 8675824976 2022091144 0672434145 0504475846 1198938570 1432470870 5432685890 9888269861 0582708359 9575256866 2748128707 0200840149 6411285272 0976413068 2647571710 5456178325 2811673637 9268987514 5030240777 5047905518 3699259422 7344855121 4367574688 4542209706 7208578294 1650178116 1617905873 5855497607 7858720821 6261825913 5685373098 4255781626 5364102566 9909919751 0354742773 6115301909 4562880124 7523385065 7816447494 7813495488 2578414317 5382125449 6213435568 6757450540 0002369269 3954204258 9824248607 9654522215 5688742200 2822158191 4370220472 5243873697 9484738660 5332299707 2889036266 6840107821 7936182257 5086218718 9246668613 3298619848 2196181634 6473892256 9654566623 1426911325 3440847437 7719931801 7990418572 2499752306 6724027942 0314058597 3285479021 7674350563 7474969156 5010595941 9836800352 1516229688 1514453166 6389450960 9695164615 2698793754 2163110563 4941098281 7587052341 4128262436 9365635270 9253214080 2025318562 7259173480 4375074947 9701317360 9805861810 9569129486 1882234557 5049424758 5832663757 8262586638 8556621889 2841966079 0998796492 3493376530 9299781096 4010498712 3164652815 9157347701 6412735409 6287857289 7002986909 9446468840 8023209015 3188691954 0886917424 6832223452 8814309155 0269664443 8103971619 3568231069 3398447600 2098846002 5696040199 8103176136 1893902284 6339736091 7164633569 3388329020 5580835208 0730287809 9751357541 2512206013 6066428748 5251728420 1588995649 0682786784 0803177698 3426423017 7021406994 7785389354 7273724445 4303274880 5404445833 7773013017 7888372582 1850816729 4766929128 4814481059 9209431442 8725962566 2940045976 2968525126 7343975632 3981558510 5933281579 9018606490 0933030410 8249784636 9973495187 9548761870 4799629635 5891699301 0815561912 3984320507 3296355896 2624040157 9978426282 6084314051 6978093808 0308158791 5671356734 8059181434 0395797512 1550758900 3775705201 1576408123 2773591708 5899012433 3008798428 1325874810 6727270383 8954489713 2325215556 7290224488 5360564175 8653091986 0109999306 6949857334 3817413197 9774367371 1298858987 9093109411 8083990871 7376698686 3950021401 3905527433 5062300271 3767420622 5668710003 8931919522 3340089658 0867180001 9909925380 7303013780 0755856368 4654755377 3889679636 0981502617 9556657420 1582925021 5226735587 5951613748 3622619794 5402066841 9743830753 5678858643 9854292071 4954796912 7875513551 9673351787 6962704152 4547400434 3029529247 8261300252 8562659595 8666126993 7785778186 0114643427 0561739159 3357554932 1139509032 7218703220 8048661791 9775503588 8369198506 4017878654 5631814455 5410630722 7050854293 6885576655 4989744786 0821574715 5532746720 9027200220 9885011302 7042438415 4350290885 7519094807 8598039901 9830751897 3217557655 5083898303 4503599300 3060733696 5804117918 3105843677 6057483371 9448783024 1083304409 5243472192 7687509714 3246037940 1748813991 3074703438 4350120080 7611398197 6244925598 6472573508 9390904523 2828142160 1448161693 5122754880 2081769662 8215614713 6179096167 4071503496 4557296444 0494188253 7423317683 6770645431 3121622416 0179578834 7690197120 5234612284 5647973811 4823169341 9686579243 7026301008 0982792325 4341007069 7506606570 6177666860 3249609399 9282044487 9371178132 1227180601 4974399990 4807674778 8644739426 5806861502 7063473273 2214468395 8929323576 2640883788 7169575880 0710331420 3808291927 0523215083 0483585138 0749573733 7419520890 0382192765 0426314193 3425756839 7671029633 7175272810 0192161113 4871986025 0671911586 5433676405 1754027476 5758390816 3985685573 7995673488 6525651044 8835493580 3479061239 6625925135 3087110311 9308231317 6895037569 6590722344 0258359409 7354778927 9972511641 9361101675 7735602822 2211988629 3394080703 9042673488 6911687099 2285367020 1761022680 8702564961 0363983270 0210871193 8601267987 5726669476 5962799008 5858717191 1646563633 8464152478 4115560774 3472330813 6194094214 2055439239 8976911201 0089146830 0245926557 0398806474 4051933572 1189450590 3803596302 7416756526 9374220117 3383175175 1739311956 7642887726 6163600224 0732165090 4625301620 2973896825 2094871762 8006085779 5661001441 4299957359 2298409407 5361811041 2662345170 9957581536 4162178096 3435689312 8058434947 7251228342 8803253543 5898133653 2417654788 5814528155 4343311251 1686194222 8828822755 7888687611 6179390963 4063096794 2524086270 5113866851 7366204657 5440380100 8702470743 4520010141 6850516325 1771610846 1391232548 6648279346 2349867916 5793739520 8443109817 2627495775 5415316469 1326175318 6239789949 8470791641 2101771077 2576376291 9136275049 9480741418 2415859842 0178620077 4424838068 4050215766 3235951671 4517571392 8093062936 9817805819 3422613185 1712613261 1538887518 7515922444 0801164259 5627429416 1597964335 2654559629 4676412540 1533084144 4765478517 6343624681 1714737133 2513241652 1028017338 1401992176 2743065621 4333946459 4261496768 0497419863 2485123420 4579861913 4125579961 2029798228 4156669011 8426429616 4515588200 3477433750 3247422358 3129623390 5171759510 9100099705 4833405221 6464150085 7903452890 5753110688 2362529328 8629734849 8585662797 7264133343 3491525004 2190519585 6289619100 9743771759 4112648271 7496800028 5254259823 2115375202 1021257957 7190064214 9639250420 0945560109 4845249572 7205629367 5858233423 6570243963 7509391045 0424956098 4618381164 9476933391 8047959220 5299102278 4784764331 6473396783 2368839532 6743999946 7065709347 9336869954 6160712347 1899428327 8385863130 6341849275 7612175515 4220843577 2391925009 3942705877 5553748593 1556247164 5200619931 5683017858 9091345759 4817658452 6345927948 5031613400 8900452169 6740086079 8240469896 8679883208 4848019806 2725340472 4101818893 9896666766 7518158255 9647778950 1108742645 1568908015 8687396230 3111910303 6155210111 6670770189 4073174631 5894629313 8568204922 9573056259 5625299565 8121133220 6138005636 4484674870 9671573378 2487455364 1668033781 2159313550 0121998877 6935305640 1065082243 1037706498 7380765354 9419064501 9779906915 2956085562 4269719216 8877692845 5560086632 2809614214 7992162741 1998225588 0671549120 2336723041 0279605325 6531828972 5044406711 8799702333 5884036705 3213454162 4796774719 9279529192 6245895612 6328864874 7038373117 5088039304 8651874899 7876640831 0985573102 2265433270 4663281447 7635502059 0928665992 0940248846 4207558923 6179360140 2676624973 9491416629 4831535220 4159306033 7620456216 7448218550 7060614777 8797455281 8289768152 3389187689 0183610526 0588782911 9916746010 0106127136 1547613289 9485510967 7046869465 8171355594 5359811054 4542634791 9172268919 9354513108 7770255844 2461626802 9358317797 6848628184 7072280563 3904722184 5574438595 3204854528 1918901728 3576567461 4872077792 6292070704 1607088150 5555409457 5234375114 2930317860 7589803772 4288601446 9001582037 1656986562 1298683422 6196882642 4934964561 9252796068 6065084206 0831070693 3098311224 1849644386 8037078513 0678037555 1382587363 6947420672 8126906920 2809965728 8352349080 6370548380 3044993322 0467085854 5729267893 6933530282 6901025359 8686292958 1890608690 3704438788 3932278544 4207566675 4537627505 6994876413 9440687427 8306158114 1250888951 2253353290 7214271918 5334458907 4079049533 4058718623 2250594893 6354388407 2006717709 6233620142 7517286407 6878545230 3452006078 9426160010 2835976840 7740508957 2573810236 9130991986 6092971697 6495599819 1635094935 8730746233 6945877601 6341680372 2677710093 6607586520 5542477009 2492644178 1091962609 1328486422 7332092540 4992301816 2309922365 4725787494 4145861941 7771003934 7161786640 3129729372 2562735192 7663171953 2806758690 2939325923 9048795417 5860683446 0783553908 2155097651 5776041358 5753230671 9569915942 6103663151 6709508768 2838300393 1131651564 2619903984 2984635754 7355699310 2504131410 5693626390 6588577414 2247539376 4195250437 3142291737 1351870059 8822483954 0763543438 4035747142 8514841706 8239252709 2729409044 4235206904 6596736795 7348424787 8792289751 8051738197 2598984994 5370242166 1143886048 6571409247 1135887981 9880129034 7356906332 1484457974 6457448707 2112604398 5866000016 3863125723 2707821713 8253108811 3100626270 2656129374 1177511108 0492483499 3801820910 8504985386 6707805593 2772065728 6496726556 9689377336 2208888888 2106587649 2817493433 6496741737 9073678648 8265604452 4748503328 9319572350 3906478263 3464457833 1489677513 9755417234 9030427254 9972816009 3633368400 2862274069 2928206456 8486984380 9056072838 1317762769 8797177287 4739903845 4302610901 3292171629 7394615688 7522291558 1508206860 4558100158 1505117783 7016069645 9377904783 8869513423 9967055194 4376891990 6818437606 5315805837 6342888673 0476455196 4642253477 7186057078 9064269761 0291580283 7509377755 9094755377 8186625423 1022674929 8342419163 4415121552 8772228812 8127670321 7925447635 3059029216 1913850042 0327318588 0383399991 2820905779 0130843771 4751782324 7543261524 0259204992 0776232974 7013789749 9284447331 9391859085 2169839695 2296525373 3916175869 9000218479 7831447238 2602441623 9526837712 1175889364 4251243320 4982244553 0280693044 9698992853 8582422275 0863826811 8134876720 3334005833 1312710787 6385789988 0404222014 5140477501 4469217195 2014292413 1968031329 4337225253 8241949574 7816633734 7611239626 7481281563 4562152477 2169449328 9499556054 0908928648 8757633432 4976216238 5906945984 8059244247 1897774837 7898795865 9043185175 9667742712 6340914145 0931200957 2271138350 4692962168 3687412340 4737082171 0585387703 9375316922 9281437506 3563181256 3024111953

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 ≡ 45 (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 = 7253 significant digits (7250 digits displayed)

Input file is:  IO\07D81A7D.cin
Certificate file is:  IO\07D81A7D.chg
Found values of n, F and G.
    Number to be tested has 22393 digits.
    Modulus has 6641 digits.
Modulus is 29.65334868% of n.

NOTICE: This program assumes that n has passed
    a BLS PRP-test with n, F, and G as given.  If
    not, then any results will be invalid!

Square test passed for F >> G.  Using modified right endpoint.

Search for factors congruent to 1.
    Running CHG with h = 6, u = 2. Right endpoint has 2473 digits.
        Done!  Time elapsed:  1126922ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1964 digits.
        Done!  Time elapsed:  306547ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1554 digits.
        Done!  Time elapsed:  301375ms.
    Running CHG with h = 5, u = 1. Right endpoint has 731 digits.
        Done!  Time elapsed:  182562ms.
A certificate has been saved to the file:  IO\07D81A7D.chg

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

Testing a PRP called "IO\07D81A7D.cin".

Pol[1, 1] with [h, u]=[4, 1] has ratio=4.135733333 E-1207 at X, ratio=3.680766183 E-1937 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=1.325483777 E-824 at X, ratio=1.325483777 E-824 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.325483777 E-824 at X, ratio=8.70050076 E-411 at Y, witness=2.
Pol[4, 1] with [h, u]=[6, 2] has ratio=1.432394284 E-509 at X, ratio=1.200519384 E-1017 at Y, witness=11.

Validated in 4 sec.


Congratulations! n is prime!

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