Primality Certificate for (8185^3673-1)/8184

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.096953% 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.096953%

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 = 319 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₁= 2 1539442734 2506381681 8600613508 3762894919 9872319589 6675463970 3971268718 4166133949 9284152178 5999426324 8490996690 2619809535 9274501503 7314895825 6855539487 2690432274 9043805002 0121250098 0184358713 9958752560 2599730915 0977628575 8288159420 0707006185 7200959404 2182005599 9965298053 5441067381 2492381918 0507821986 4801061508 7964816278 9263662289 4604305656 7617299591 4409430343 8744165144 0411366198 7361683238 3728404688 9813703071 7983818700 0856737559 4254635336 0027330931 3921540469 8540435849 3311250973 6819388647 7919159612 9037256257 8775821329 9784310766 6317188983 8477371830 6410529300 0253709117 8297201401 8617973387 0552104471 7317545789 6494867569 3163011615 8033978624 6069687401 7681382433 5753413685 0952876126 0245265614 2597082364 0938577678 5501348563 5527232641 8954704872 5707132264 2350433101 7466590123 1993188319 8237956936 5140988534 2083354078 8347372712 3243204656 9862536997 2563204860 4980381031 9205859854 6964741016 9663983915 6083697504 0196672629 9008323863 6758126164 7667360251 2273083501 7886888940 1634172402 1313586855 7355355501 3993405810 9203340947 8804516251 3493639390 8483943735 6448896325 4307448497 3470803246 0340768859 9652901880 6714536443 0709755829 9193823185 1352698105 2223336691 9305370514 5836000822 8784458973 7899860815 3723220850 8979005949 7249128976 6108553819 5136797238 6539947792 4578624485 5331771193 3190852249 1459454186 9141062423 3152721194 9682097747 0317249040 5679134883 9067191169 8976818983 3407327634 5490349028 0463837368 0323866808 5410764888 1518041879 9787452936 3721440385 9096685258 5890811622 9863423155 4471102520 8127598191 4592404316 2381005372 2428361151 2101587378 4499141823 6913719076 6921109876 7284134938 8920920052 7879417789 1776469889 2651779202 6000240024 1409200313 0217043075 7460211461 5601024554 0778871007 7380390336 0992326830 1637822813 5972566612 6050117320 7821820954 5533323587 9140968990 7720342976 5000203838 8669240853 9267307067 8831036586 7356671718 0296081518 9588230212 3866619557 0122720158 6597133717 6938756468 3564543894 3117870951 2526392082 5531726059 7172495923 9578658649 4617253859 1278494668 5026389377 7882756569 3332204217 2186931164 0798953187 7087828337 0793976779 4392116238 5521360156 6036333575 0572667223 8808533857 0136846291 1055517023 7770513484 1272805329 1073697153 2440261600 2190920864 6602980614 8284247869 5241697677 1999273910 0113828714 3149647105 7212471040 4931035989 3063500370 3588508249 5870929365 2522052972 1836116722 4311840425 7437557271 2048362781 4843355440 2390042035 2679383359 4054253893 3146314262 7986606201 1949219412 5349820431 7501816418 3512482443 0345478231 7435423908 8518487824 7752186823 5815768497 8211982126 4075328022 3381512671 8483328480 5811163258 4846423144 4378322245 0571480560 2162684461 5487316255 1091708729 6835887559 1288050662 8790985792 0549509922 7431570737 5440171759 3295445338 2135475345 4656611437 2046608097 3379419325 7741903203 7164714083 0306226025 0468337161 7573829045 3917508663 8579444988 2690122696 4935774082 7858414590 6413436568 2581224155 8530341903 3002135825 8203247870 8793536239 6399040222 5331867634 3633716361 9492138415 2255191629 2805968139 8013253935 8734482192 2589194739 5758806217 3462763716 9143196438 2383154500 1762447666 3469648997 4193398787 4801566911 1101528213 4792652333 9283683973 0867510054 9450359520 4528434536 4264889411 5893181515 6192497686 6351268145 5877182795 8742905378 1739426656 3088150395 9023799298 7037757110 4960709803 1367625477 0904410194 0779790775 0301613220 8044229515 7099251733 7882747866 0702037759 1898972421 4062764157 4264771715 4433811718 2357631579 4007716281 7291548462 5933802425 5456139981 0444568086 3076475256 3435594398 1902074536 5267885844 7568986774 2858978002 9035137088 5444006447 6559482840 8513031316 3819962359 8099141194 9648524664 6188027657 4198245256 9465838475 2940781190 5405531135 5106503505 8523214342 0866936195 7221381511 4020662490 8790352844 5360493761 7866629368 0574433426 2416682633 4826917260 2744658796 9908936254 4298684128 2218528241 2914889603 8846279967 9679403454 4544371728 5473187146 0232493938 9341067644 8542963511 7713368018 0541222138 7536119037 0836015233 3449315674 3953965075 3202161896 1187921893 2237509372 3819490813 7812479556 4424592513 7572574078 8288389594 8140610198 9261037917 1921630771 8168643900 0336436736 5756916690 4586585550 8988301273 4389672037 6229400971 2105116402 3877786225 1667623775 7941969027 0214137600 1767450741 6049425155 2852594912 2805244739 5120677380 4859161066 7794197248 3448310681 5696215438 6304713200 7805358230 2162115030 7160333785 8592509983
• c₂= 8960673 4714799530 8236953807 2529278324 0122011595 6259352254 2467836077 8602711314 5892215047 2808961116 5055956648 4048307790 3445540601 5161616219 9881853201 8937053816 9882704628 7914129370 3432578311 1813116689 0725548568 1825374755 4851219563 5838384290 1556866648 7063557220 3066654548 3433435598 2473154559 1152469389 3129925722 0338097610 4702307837 4671762267 3401743304 9184719615 5974537516 0265692143 8095446394 3625518927 6234752676 5880944513 0759541660 6094900812 8056970725 5982186188 5874735494 0927139058 1302590171 2712133729 7880474711 7595057474 3695213791 2686669780 5465994698 7925697572 5010110820 9406632357 1416082729 3763932973 8583252658 4934818330 1726550349 8633584067 1508302406 0049873181 0363141001 0492684596 0238657866 5784996034 8201532694 2006952651 3732825665 9166359579 9975855915 1143890523 5614381925 9424098828 4384893191 5604539920 4530087858 4378291130 1547802853 9720477553 8039623595 0198173241 8053196267 5644923848 1522098146 1070038472 9585930362 2105472496 8523666604 2758023504 7750464157 5056921505 6078292047 9482259868 3162036036 1037169652 9079858049 7744072546 1027726474 6123093903 0996095488 8744038014 5854831674 5367589038 8956575093 0288723807 8957066806 8190963706 5071435373 2348664935 8698054572 6697120961 1683603350 0232123942 7964215115 5133274267 8488844646 7957773897 2068587864 7317246032 0046061179 7224537262 6510868005 2286690192 2474896098 6394034819 4218308249 1477782077 1439930633 2773935866 9560192856 8481363288 6987629347 5091979773 2926642467 7018991527 2112203516 3298193002 7059809166 3169580528 2743222910 9297752309 1061650354 8851285669 7288688942 4927897626 9249490930 5473390638 6077323080 1653727227 6789101195 9172975805 8179948324 2549319360 7733750389 4315953534 2608649460 1243415475 8889740662 2671631982 3275809560 9015132099 6676064359 0773827320 9910923532 7595478683 9992742029 8031673250 8348800174 5757176852 1501212121 7630379993 7994461720 3042086881 9030300548 3189825037 8229024671 8946974651 3575369446 4517460366 3044947822 3717176033 0830764185 2387002147 9049462295 0231003336 1179382644 5491243750 8270697560 7468965335 8753093168 9684127072 5900888869 0828052918 6857078729 1833820515 6650883067 0373208818 5962153760 3818397918 4716969682 1051587847 3058706602 4261180242 7056036689 3350694088 8459343316 9699697942 5341317880 2157888780 8109161451 0076429494 1096562611 6679294006 7982645125 1186208290 1868969736 3709224350 4240749268 7464766227 0653856760 6672737414 1313952338 7135032564 3461791699 0816744845 8034516321 2675596308 8235827371 6759098869 2016381038 3164965059 3175914531 8423406573 5210296831 1064333549 4731399184 0905479315 3347610575 7259319016 2239223911 3206120738 7715786123 3501789827 3036715538 9636930566 7108616751 0503614651 7011209606 9447090287 2452693592 9342439254 9290241014 8559988402 4353226455 9278774949 1162010496 2247699262 1461039691 9534695774 1847487878 4871800660 7539144640 0650179712 9589133583 9143452485 0291668735 8764954929 7441846578 9512006563 2952800879 4988552963 8175456470 4477685977 0069745870 4546938359 0635901714 2839541989 8572279227 8712437229 7401228909 8211782101 1411975043 1509594317 1085596781 3117141885 9066589621 5629616342 2983947604 8251144736 3967807225 1226148525 8149139791 8938759436 5609058934 3291469619 4370690050 7997277227 6006276880 0937581235 2702251503 0528261135 6306429032 4424948856 3464990509 6842047304 3587104240 5214132418 8616357183 7707811569 6709833161 4989133213 5750730179 3537603408 9415871844 8494492941 4310266828 5053991458 2170807719 6235101093 6924341077 6329696273 9862362670 8448819688 5974136056 6661529281 0751556329 3821741812 4880258599 0085002947 0671199461 8493268634 5724624890 7827318296 2228779723 0417891023 2381437589 3222605872 3639862615 0127092252 3369181253 8960118826 4801243736 1530980120 9679054084 0781905822 4186143965 4012787301 3236050437 7421160566 0641441536 8885350210 0222296595 5025133984 8755242982 0950037234 7644830320 4037839748 0373414547 7709503053 7725383009 0615686084 7971925118 2259256589 5856808897 9004562344 5414037796 2808501136 0664900034 7001440392 4341669280 8510646909 8627810887 4769050865 0980525154 3400916875 8280243924 7832466844 6756981807 1290639043 9696074959 8392317455 7636902306 7362894244 3577265612 5928660586 8288786355 1538385005 6261815287 1066218714 6151902260 0236773189 6935829395 8621130382 4759646961 1872075216 4132695676 7987579856 0440950410 7292249442 6023863376 7191424270 0700549811 2335200345 2365443322 5163560219 5297123127 4017765294 3941119350 2348727647 0789799506 5583772098 0184955559 8775969116 9659858123 5496954700 7458504260 1240723412 7102478883 4824910743 8905971586 5825294438 4674454007 6063930867 1954701565 1443798494 8938282533 0644770689 3045542854 2578595779 3535199670 7113440549 0929671613 9455098713 0173531682 3066498269 1640020718 8446918256 2108559864 8838921682 1000551254 5841692511 3711052333 8619513703 1833807555 3507150457 7391551458 9602168852 5543697868 1381396674 8140717050 7531925522 7707774578 2423750955 9160931954 6683986470 9741443665 6808765499 6322700081 6926441372 6325074704 7085393457 6710971159 4724504280 0225688144 8382866658 4234905138 4502794234 1887976427 6119320598 9562905616 9061871508 1784346934 1422586404 0186871352 6132319075 0453416631 5754718818 5764217999 2098566841 8770542870 3843528700 4749515352 7614313695 6915270092 3522371769 4235956850 7363256394 1888959419 3573809588 9546739317 2890148710 3960911136 8552145750 4673220223 0758245824 7048274581 1338506489 8472826172 9354373907 7427207497 2006019573 7551337551 8176058341 1501331587 0053774039 9473450269 0587359420 2091139820 8091930997 2680654095 2863781056 4371675640 9577684371 3738623639 0905479624 9762729417 4422009416 4394027023 9121150322 3146596843 1098770314 9755614306 7396752431 9028387899 0066214012 3378691989 0476060620 8640952433 5625091318 7098184942 5615539246 4599686276 8246049847 2690577269 8936477277 4483533089 1753586736 3899373336 2086108108 4538345937 2639619433 3945990108 8094523109 2790360700 9777351713 1551190873 4182813056 4822061728 9990809198 6780921482 5014925082 9807219284 1098129581 2224407316 5094935375 8777867426 3403157966 2214596466 8613252315 2878231173 7599846692 3197220452 6690051851 7960331910 3259498245 4019388079 1755891428 8984330604 1741459603 8132174900 7623850580 9437956243 5392534728 3980559002 2925107399 9363137329 4414286155 4880513367 5911447313 7455691074 3899541294 6481630704 6560543485 5699529117 0749216467 2186285031 8368236230 2593549772 8122829050 6408141995 0401778188 9782897939 1753694737 8996681922 6681631466 3499109481

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 ≡ 29 (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:

realprecision = 5009 significant digits (5000 digits displayed)

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

Input file is:  IO\1FF90E59.cin
Certificate file is:  IO\1FF90E59.chg
Found values of n, F and G.
    Number to be tested has 14369 digits.
    Modulus has 4181 digits.
Modulus is 29.09695310% 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 1827 digits.
        Done!  Time elapsed:  246609ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1669 digits.
        Done!  Time elapsed:  248031ms.
    Running CHG with h = 6, u = 2. Right endpoint has 1431 digits.
        Done!  Time elapsed:  276828ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1143 digits.
        Done!  Time elapsed:  14282ms.
    Running CHG with h = 5, u = 1. Right endpoint has 892 digits.
        Done!  Time elapsed:  100843ms.
    Running CHG with h = 5, u = 1. Right endpoint has 390 digits.
        Done!  Time elapsed:  87922ms.
A certificate has been saved to the file:  IO\1FF90E59.chg

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

Testing a PRP called "IO\1FF90E59.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.606943692 E-529 at X, ratio=1.908445789 E-918 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=1.665425427 E-503 at X, ratio=5.735074794 E-503 at Y, witness=5.
Pol[3, 1] with [h, u]=[4, 1] has ratio=7.78204974 E-252 at X, ratio=8.73750917 E-252 at Y, witness=2.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.0905400123 at X, ratio=4.108413976 E-577 at Y, witness=2.
Pol[5, 1] with [h, u]=[6, 2] has ratio=2.696198515 E-238 at X, ratio=1.395026494 E-475 at Y, witness=13.
Pol[6, 1] with [h, u]=[6, 2] has ratio=9.18657576 E-160 at X, ratio=2.613637053 E-317 at Y, witness=3.

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.