Primality Certificate for (28839^8317-1)/28838

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

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 = 11 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 N ≡ 1 (mod F), we can let N = c₂·F² + c₁·F + 1.

• c₁= 643664785 3686566328 4687884877 7466063391 7240357778 2095270092 1841348011 6139723723 0359269037 9780383786 2732951060 2985868766 1686214428 0238064506 0017697810 1212743869 7254815020 6142461789 6256187880 8855860577 1998493653 6272018283 1730106073 2980835248 1431112069 8470533517 2204744128 8712206960 1672743293 9812303256 1934820570 2402150854 4528939208 6084974727 6959294809 4847423908 7931371837 5850009970 9237751454 1118614305 5664312723 7956874639 3385577208 7245441070 0481618636 5679469125 3403968862 6388620367 8909392934 8042780921 9051989244 2608654857 9440483070 7936970932 8652898680 8718421891 4749726207 5113572543 5489620155 9209739681 7849580294 1832619585 7123485986 6647772331 6278954461 7026701824 0630128162 2732006486 8717282511 6311512715 0556676912 0793442560 6429740542 9031849601 7977341492 4390050663 7488559148 4044549122 5871618522 1751579519 9563343709 0521335625 5229524467 1610682836 8684601397 9151652320 1973423101 3247830834 8892815467 8109729189 5024706200 4221324758 5438225713 2727016929 0918872512 8435086224 4109546105 4878840943 3579365108 9768560722 8709627595 8546679928 5166135986 2641692005 8415327301 8068183383 5403324167 8054050830 7350386216 6853831817 8367270352 9735679317 0403610509 5069507205 8705936832 0766305330 3024626045 4263850857 3010054746 6899129117 1241980850 4236527401 1090614891 3827550798 4166082243 8775506010 8074889207 8413591930 8731123466 9284636174 0285797186 9051592822 4434180183 6655867158 6468469789 1775525821 6056066088 3358607103 7148763691 9915593551 5733053185 0375445378 4660459127 1295895069 9378424291 2104848007 0257388574 7219186690 8639058238 3087102845 7367335600 5999129079 1928638640 0611541459 1106245075 2414048651 7325487541 3501757527 8697832997 2905293787 5608233461 4452483135 8174356710 7855567187 1495672097 8445278294 7111813048 8450047685 7490161703 3381228043 6058904377 3195559155 9465634291 6970035076 9782891135 7388338994 5136538278 5325979252 2583418743 1387374838 4952864651 2278423710 7941982875 4613868545 3582640942 1802609220 5011148170 3507521636 6793984234 3694209601 6214478175 8697999356 4776157562 9277749784 7350398569 7511405595 1522255029 3402470120 0614999494 4182848332 3676691697 2116603615 8081639953 4671208981 0782983275 2132419472 7860946805 9285952195 9629165887 2321607770 6825404756 8585053962 4728845964 6599135359 9225156260 4593334099 1420037587 0250385262 8425694007 9447035845 1783396894 8506862972 1774410143 9638593130 3909727839 4815850643 8077135312 3921220203 3490754815 2733509987 0867595972 1171261746 9493909803 3038860379 8209821116 4263815340 8397673190 0916259353 7855607080 5858794604 7050097806 6678160728 5101860735 9588190205 8942174391 1244211365 4901550658 7703822679 9600238040 1629200156 8480366209 8480578485 2014872919 2260497544 8519609333 9566560179 2139007600 5584328952 6942746030 6748372195 9461653812 5150272882 6995363453 8574883988 6377530042 4042614780 7716948402 8408973846 7954138070 0329415103 7981827190 5324653447 0043866468 3852778693 5027629498 4861722281 7656653688 3907413813 9732708864 5589794824 5251207850 9993162521 4497384592 1747673270 5894103413 8178867497 7316413926 5622877976 3682153039 2803148402 3612923867 7831113495 9984478608 8673899554 5858951524 4692988476 4429034612 3785339721 4729057563 8768989374 9982800612 2246741065 3073625572 2635650860 2309870364 2359719808 2725726824 7456681133 4275847360 2985951419 9893675361 4700328158 2204909030 6611315285 6503609500 0640690483 1842727908 2053859688 4090795907 2834659538 0912998784 0453119064 5605000187 6343377641 1682033554 6724580738 7297585994 4169983711 1858644594 6619289847 7159283995 1789430041 8805031997 0927830458 8903666714 6660426000 9278852384 5246451385 6266013263 8468688115 8470386267 8841714065 5646241665 9715671645 1946646484 7792380871 2686363863 0690970579 4086051894 1304617800 2747736564 9437559811 4541773261 7543830150 5158779019 9463139560 6067818380 3829060970 3948724690 4407230280 0702384195 6754424127 5078946384 4132881302 3982322970 2547736518 9717251302 5820879775 8243869549 0696902130 3303650640 2488481660 2849477944 2106259841 1685909614 0103822562 9346267944 0743157846 0998593990 0915577878 2348892677 2010046964 8031202778 9918318480 2925744012 8699386768 1790606307 0834551527 8661828585 1818007655 2660694153 0822037083 3803091395 1076174511 8211940315 9316507523 1856662763 5271285657 4206042871 4398231192 5209741708 7016694551 8457874070 4798692629 1512366254 1550617653 8597365196 0498670538 4407786711 1874229313 8574716004 3874096234 6651623174 0775157632 2177177167 1301970272 3813359520 5433355981 0420401973 1552932578 9842469063 7374354913 5910534919 5820491986 6438034670 1263933084 8749935750 7249553952 7524315351 3728595697 4858204004 5676026316 5276316510 6271300568 0739111705 6251823281 6385986299 3852926609 3029774464 8477085465 4882158508 3345682138 1561695018 9201069954 2609184123 0623571163 8132538981 5933520084 8467085825 0690649116 6553966813 3879468872 7405054702 0532071354 2906869071 1735594271 7417099516 6069705371 3076225138 8455268906 8335169316 0982928010 9154020449 9955359459 4171620313 5820011994 8321640198 5570526301 8590106501 9213809033 0859410634 8890917960 5774723229 9788661915 0365103481 9280084915 3169565612 1359654520 6588405525 0697615263 1817239645 6101541791 0965843584 9459153189 7853355920 5813570158 4467774606 4443405277 4143613954 1858223881 7416084086 2281995336 1287772488 8680493262 0101321626 1298244946 5655376300 5039018997 7218279146 3593172752 7727261839 8283927086 5007167102 8925684208 0719146149 9780603199 2590035856 3039231173 5086379161 4175693641 5979890773 7911895366 9082550526 2234097069 0803343163 4120492779 3277870875 0979748874 3844596875 1817039470 2811169876 8034852480 6804607037 4288362910 1303531876 1679023409 8683864992 7349425265 1732552757 4211309065 1467590573 8668936367 0274580566 9993487782 2624347681 0479210722 1516415655 7874976094 5017308400 0516237084 0887491578 6306085616 6780387217 6169443297 8745511568 9598029451 0759460652 3210621869 8896848380 1188300715 7579798111 5690843748 9663907515 4818697376 3035099917 1458539549 0440408858 6192218463 6251141173 9877468711 6712755449 7501518536 2328195174 2519125260 2734510646 2045347590 8767996384 4943722706 8617225072 8302134859 5581763180 4045463853 9471787614 0249300346 9025673074 5640106213 3694178534 2122218647 8961264835 6759573241 4070342677 1329899036 2524281339 1694835529 7860490648 2362546574 2859361661 9447750193 0518912874 1959854446 2719914849 9654155601 0408083834 1647834507 7191791007 0666671043 2634415004 4088456654 1585376655 7005073891 4635931264 9064641126 9329045869 5717151445 8489631082 5144628094 0311070441 7314636860 1765724396 0503040190 4454088655 4586423676 8634621341 5865556088 7714867852 0312972321 7358979299 1354345762 4157300606 6513217631 0969650702 8457194209 6922894780 1364631131 5039970864 9353730692 5684096590 9895318296 6300948542 3122838817 2996411475 1879363645 6086659341 3300742190 4677724746 9731575892 2498301687 5124834581 3227172367 5908629629 5974207907 8382356480 5301825897 4243374392 7686205767 3778708788 6790402731 4788119612 0271156834 2774439938 6607840024 2832895041 2058172505 0875010787 0306102965 3326499595 4856280493 8499814966 8794664595 2059588489 5524773214 6101840028 4073672812 7413119293 7458559819 6028959642 1010838918 1699366344 6366152493 9086933971 9378630860 5842494201 7124512955 8313931360 8160867645 9570112906 8961817171 5333967398 0967870956 1888704964 0337698592 5552631562 5697535703 2680713614 5114323619 6877098002 8512789460 2133817475 3202306393 6554691617 1569076117 8959562968 8532720871 7205770639 7349609416 9162449485 4957293457 6662608878 2093850250 5747580558 2616777209 4332762640 1564048992 9916643902 2449001437 4985083779 2885444985 4978907569 8702772140 8449165250 2359140655 9138897493 6543987109 0681315256 8650910051 4506494615 0171874911 4073024896 2944922958 4309315378 1519348012 8560143449 8435729888 7159956690 8192781824 0763719407 4706373147 6358036144 9109344708 2186617297 9966769009 1161041432 4322877497 3216263831 6807604066 0498149524 3475811970 7615430028 2376538843 6407186136 3989376612 9696741503 9100534300 2769884606 7297974938 3581262292 6405754523 2453662481 3928832948 7230536572 0037576587 7565816835 8529923636 1507855014 2664783575 1718879768 1732122170 7918150313 8500964232 5455629621 4251906578 7725602110 1614881272 7867150440 0575645220 4201663625 7517828321 4218152150 4689961963 5953909795 0944462231 4998628226 0427647621 9981581769 8820414905 2983040953 9987083596 3268884335 1200063278 9668077416 3523036374 6824296739 1410707684 7878674191 8348665395 6255083553 0753689239 9464960498 5314417795 6638849343 7499755314 8234636541 6543085491 4979536425 1436396491 4314958481 0329746507 7123445399 9872761973 3541474139 1249072812 6559819909 7182183297 3813178044 2283697644 7548846861 7036885764 4969764341 7586451601 4391796161 3086904563 0888137899 4041731411 9496201507 1130800760 6817164247 7267077268 7496013102 4140588323 2651541837 9118841908 1917490761 8309352076 8317752703 0895495547 4196852847 1354502650 3891133655 8745201352 3563775634 0923441741 3902612027 7502368912 0382931873 8506936396 6134078504 5414734139 2972056815 3400725748 5669155530 2773037342 9500479004 8231586730 8161809727 1944719397 5601898783 3242325097 5351271812 8365025318 1194950714 2595802694 4233779862 0861847635 4063916407 1653251488 7939436666 5995613860 2111629736 4756118094 5183159897 6375807349 3735222291 1305682903 8238353991 0395726733 2048420461 3748374020 7574886232 1126896763 8435190318 9257665683 2010859672 0548939736 8116959640 3375957007 0388694414 6560572214 1332086316 0772398145 5575429094 0958225208 8567512950 8259426157 4863408282 7233267735 7871296385 8757826874 8869975994 9254184368 3149210179 8369480395 9060236859 4266435148 8523980332 7756345332 8836285374 4713235639 0753612048 1847839518 9041129278 2693767063 2790612054 0230619817 2640001719 6493712065 7555363041 2383795388 6540944065 1247181386 2923983806 9446545486 7972353140 3808913622 9459444981 0165559601 0075219412 5555741986 0438120267 0960892374 6239774555 8688711514 1432747637 2441690523 5750775966 2727433397 3950446522 2569226582 0138197343 8859112633 9195028212 1050037839 9213656160 8042979837 5060695429 1457489335 5199540797 5194076183 4589829868 6437986334 0838402277 9695129949 4122660383 8293600981 3079502626 6508396904 2296688834 8802336184 3997026098 2318695036 3501391948 0244894344 3210232449 8830798096 3043586633 8264767351 4848799975 6123182511 5091486305 3599184634 0625808755 7831725519 3027468480 3624835377 2060843620 6647814757 8670293565 9776680169 1941403679 9112040367 0857439052 0811295646 1446094566 5355900343 6650381761 5245498872 0344178225 9551341748 8264246994 6812057259 7361762745 2626715918 8776114911 4846092403 2285669548 2277363715 7537025722 2355766787 3137473576 3267425924 4015208890 6077890481 9464122710 5859668220 0847174639 9725370057 2283044103 1856263418 8585482616 5041212339 3931190326 2747333971 3346477892 2292593213 7244049701 2596503718 2308020943 7858391879 7169654977 0042697386 5160548840 8722958775 5879807180 1909456501 5922882441 3989201471 5620178941 0657313951 5405849794 3740375671 9640672530 9560739440 0296234978 2410325134 0599909620 8403447288 0528444529 5061357403
• c₂= 12 0070694028 1729155595 5496092056 9253000976 5436937018 2431761772 2168020206 0229021774 5055556056 3088114181 7314994980 1947083723 3996815420 8317956685 5984631945 6400047433 2998952761 6586931064 0453477330 3847140432 0195579238 9873058070 6786445004 8492857707 5671932998 8610909017 9851807425 8731673355 4992403525 9034717090 5057051324 9334009248 4911919113 8889408613 8173358664 0280046592 3493489468 0652311375 7739167177 3084219195 7016764330 0820266824 5202114909 8157348405 8230570035 5964037760 4678893665 4866670694 4413461114 6671007359 7623414826 8183438042 7796334426 2476225764 7707333401 2726410187 8963760845 7872689165 0987510157 3351095981 3687665773 5401200612 3097850670 4933319475 7039691894 0053554545 3152202755 2337423482 4021507292 5922344431 2289247169 2922244263 0558768212 0351364593 9080730967 6698247206 0088635336 2240043735 9337937080 8268585478 1690041043 9511306148 9546625653 1928964286 6728365707 0219711748 7632217164 5665666394 2084348182 8883225433 7014547826 1712414909 8946505316 8888624053 4013972284 1200632224 5715393260 4831243452 0385094529 3179770948 8014010839 9329445548 2531082019 0567059358 1298389323 9775417224 8740629757 4197615060 9962009490 7271656906 9182493469 0213434501 1234124076 0461377463 1698209680 3045589767 6471462222 4458079586 0536945276 2392800742 7810700559 6902886273 6319813942 9927289601 3798465868 1878266110 2127937052 7890347823 8701966143 8774037013 0838882739 4078592573 7301162093 9131060851 0602864895 5001008850 2692159789 2618320350 8760897965 6588823166 9706211373 1426819107 6898391640 4270445719 5752145551 6530315007 5900909137 0867789213 0582654172 4114091363 4831469726 5332325986 8826404627 2618235190 0435785920 1949984027 6633294700 0379609708 9651368365 5896616290 0428810225 8081726013 7418251514 6760054010 9181994588 7722936178 8142504328 0490140816 6192318783 9969878517 6880192709 4243115447 9725850451 1351195103 0765401706 5679921984 2636399432 6043821448 6576567739 8079908018 3803989801 2711243086 6365211149 3796734276 9169985003 5706135614 0874783676 6592585212 0893053776 8711719787 4959384341 0876108244 3325347123 5729512070 4792103391 3333918208 5556187135 7950596603 0224963778 2216631635 2374743639 8724738242 2965187745 2888777127 6265611363 1606840380 1646406032 1087688438 1289106072 7387637605 2328578334 2252454286 3504854305 1251062258 3133303119 6217118248 8162386094 5517185614 4573735442 3156244553 9041210044 8097100013 3461384121 2854389656 3318716851 2175563973 6222348084 2833940468 1459908592 7072922879 8316024318 3582748444 7387294176 2449663523 1564775809 4649137969 4399642751 1695549740 1635852876 6916726467 4946555702 8389532136 3069623575 6699356305 6093090552 9168419535 7232870182 2879880374 2818224402 6817188945 9818912657 6234338858 1879162528 0350077560 3614923076 0388555059 3390510204 3505459808 7693497001 4110144092 0839064579 2516111658 4287038030 2603806880 8274010182 0600635000 3718289398 0208656966 3386099665 8564676532 4896119410 5637097055 6527378902 0492698111 8059021082 0885113339 9141908620 0381304260 5318551183 6749036272 4478923759 5969289601 5030191041 6874400528 3525861008 1021701521 3578688634 2664507662 3094585008 3034277730 4970928502 2556646479 6824712160 5710602315 0326072026 1556164589 5788993264 8200262295 3327912313 1860420192 4423021747 9677774546 7597219320 4068863553 5172362562 4705733206 6415121229 3910425779 5318389213 7701982913 1723336381 9200991253 0324580706 0407851811 9072179419 6553118676 2584887060 8758692582 5667085633 4983652442 9765849838 6055199702 6998524892 4290432041 3076286758 0077778845 5689421647 2719771889 3250388201 9659220575 4712478433 4639515852 3871757849 2259708743 9545670074 1211135766 8579808747 1685488328 5805637676 0988492368 9661878219 7353821227 0654193440 8099316383 1946981760 0698721129 4498784657 8686899540 6423854630 8136883638 0255307478 5794150773 7556190449 6053772393 3479345427 7298778442 5997461035 9184353451 3186171326 1685769991 0784031726 5331045856 7100526199 9394283822 1965179732 2661732860 1040516617 2708933496 7515274799 9308162780 4544515527 7351059954 9109102973 3883818990 7669877753 6759894649 4871817355 6661899651 9471315373 1030088466 2784386001 9277292060 7973986659 3260808664 0450436446 0916361788 7232739475 3163098093 1338783480 4202858143 3031634739 9927007989 8475294996 1316447211 5961611600 2375189794 7794762972 1199439118 6995996444 6831517108 9607579066 5434042512 9809935942 1460023972 1873743650 0605285690 2687745563 0367729301 0291961155 8562691474 1824505820 2695171012 9207003592 4372377893 6602568935 0799041732 5256512026 5258722224 2343625818 9495349975 1251125901 1156207883 9312439298 8162496658 4593107451 6442729066 3205068880 9014624187 6114923578 8979343876 4579115626 4735879117 8355905656 6698079262 1604628113 2061546907 0613041422 1724710705 5908997635 0599931569 6201384518 8033455845 6260699952 6063021429 0207053356 6714197594 8646258209 1730820322 9235257128 2348719501 3281055969 1189636273 1832995433 3281920768 0541015961 4445223209 6413742200 9989559417 6088025176 4501246363 9955130054 9010225870 1307735487 5971991573 2691247899 3278531470 6839422546 2645088183 3421236420 6940957267 1498277147 3400809903 4682086943 9285154402 9737937442 5649824632 9834007733 4430321924 3001691055 5539519803 1290153957 6251277349 6697354781 9312302623 1593264739 9617381949 0863380277 8843133382 8454961896 1997931899 2031736735 4745271114 0554545502 2089464367 2227253887 2899606130 0156721037 8266760234 6440732643 1145142772 1184115295 9184603319 3329985644 8491540671 5695573643 7295687446 2239081630 6882707864 9186115121 2854007656 1316369472 7366243347 5573123188 6852419211 9871663473 0783213016 7346581055 8770290929 8667305147 5588512955 2462267154 6538820953 6244402959 8092543009 8935298622 6550437522 5113768037 4300036836 0755648373 6454196863 3848923590 5659409533 8432865486 1955485746 1247603229 8426853665 0989926359 1836801748 2517926375 5277040369 5565104103 8826929625 6181627410 2197237692 3193850173 2958162266 5803565582 7579316124 3674217523 9234943884 3369155612 0368383680 4747912851 1729042960 6311585006 7011183780 5668791471 5395689828 6724560395 9128314491 8153740048 4829569399 1969583114 4836169562 1507659261 7690239236 8588111065 4773545562 2278477061 8473688371 4125944110 3924606876 4799043075 3833521166 5057991116 7008671144 3556760632 0074584221 6772583083 9856568831 5329237067 3762736799 5420053569 3930592859 8955184702 5331695375 5385561840 3657455954 6635929833 1347651838 2380990440 9487663811 2925539319 2065885453 8965423299 5168940289 6452959754 5776666384 8054911722 5228239404 4235394988 9253149688 4449284346 6248992377 7870920342 6675766720 7991911774 6274058496 6475343027 2369344990 6341869317 5204467783 0115965145 5550928885 0011133831 5535752553 1151249090 7470278972 4653719445 1853713899 7168087087 5443639945 0268277807 0181491177 1406520762 0943081411 7129681076 6864356831 9577042462 6384378985 2173309742 5449160945 6473476812 3495623055 4825626516 7445487585 3694888629 7939653494 0754149984 8470054261 0556909355 6187939673 6482446922 7179545237 7841595230 9230564372 5435031494 8730799277 2500458448 2108445301 9138788566 0104124645 8635341946 7629766146 6035943982 9889126171 6293631856 7291214177 9671950898 2981889951 7428957951 6910150620 4131618379 3638553462 3916059463 5750182237 4043433901 6683965863 3379869135 3735439441 6668754799 7421385439 5650445716 2771740427 3235032495 8614041411 3034118452 6336792198 8824392049 5962416568 7067320499 0490815898 9162007161 0686981148 7263861640 2167943982 1097638354 7782822661 9218121236 6434414336 7726242831 0534527649 8514766655 5649118024 5778525172 9497871698 2100923976 5990311124 7864429822 3616045302 2633137709 5692902808 2821089491 3918495679 1397435736 6305583236 6037421418 1498964479 4952219375 2405880187 4692151210 5079722071 4755562359 3408395825 8616248572 5852528974 7791121243 9369551157 8454101637 5706259591 8142152980 7433434879 6494897095 9030961729 3968096964 7971963478 2927433904 2603539743 9463816887 0797586105 6346728174 5965304874 8321588872 7255472558 6256684563 3269224588 5846913421 2918767861 1119500346 6281544737 8866529906 2384119488 1389295538 5587262735 0961949143 8783113819 2830548296 2916660808 6959124045 0706859817 2152857070 6876032749 9160042080 6369374488 6674988135 4574681947 3502479751 6883580554 1588614059 6946860468 0646167722 9998004891 5817974486 0786400284 1453914715 4953197635 6073306873 9226371608 9458084664 6653792580 9367205081 7647584537 6470045410 9974534241 8270824935 6125013787 8895510704 0785857395 3480570742 0417611178 4191855960 6325719553 5827588881 0021873469 6981841850 6950670138 0557156768 9347347121 3153459998 5160119344 0206171578 8438252262 3047891568 8021623231 0632837503 0661128445 3415674613 1041275284 7524836391 6610903459 2397953222 5514111290 5055680996 6162874403 3553476285 0638041992 8612023100 6490236141 7290398252 6759092581 2066910244 9869282283 5037359687 2728251929 1856751375 2819254849 0628232935 8787291187 3830451248 5609244779 3863416391 2817800431 5073007901 1459020917 3763093605 3483828712 1484293386 3929454160 8810990325 8686146083 5268153744 1501829510 5849727201 9575684065 6279372124 8657367535 2379647922 6136194144 5492937590 2706321117 5581480335 0968818257 9967344676 3213501356 9579376103 2210684478 1693955184 5184933301 6363024599 2257963939 6923379498 4902730324 0868116860 7238823803 6069594272 1598160280 6633703716 0092337067 5052229964 8135398784 7038110691 7250090456 9031788322 9786633317 7882425242 0418946449 1051229550 4614936696 0310915345 1434144330 6494073276 1397116936 8792783397 4864523041 3602838085 9609759521 9797059622 0326873442 1859415855 1693867922 3769264262 9814871868 7667905430 3059945700 3916746351 6209676798 0858750243 0649762634 5608130748 2190245215 4908675417 2838177938 2535624543 0791918077 0554332763 9140487029 6779673916 6343425732 6692299957 3279183945 0699796294 7628451737 0829984708 5003432639 8639875641 9306388277 2010795550 8749049187 9594454768 4485906919 5551539380 5593783576 2674189406 8988657635 9373088973 0865879598 9410714457 7129702720 0520036342 5801942820 4452052442 7895824169 2157491635 3365469018 0904370351 8880799373 6865641458 9003819824 2205752609 3717068329 5590921644 1285299505 3471374468 0021145753 8576252302 5188229388 7613278023 2581065842 3657877072 5201724402 0826354020 9386943655 2757700673 0910566573 1288589350 5917503237 6360485748 8184591552 7516191709 4254155314 7085201405 8417756109 9558091546 2287793059 8255937117 4768824418 7026211602 7590770501 7154615170 3927600854 1058277229 2371057842 5337666502 0052722844 2613583786 2130651474 2572609647 3339658307 1271491551 8350450914 9083559935 4718831753 3110267571 2966928985 0612479701 5239238402 4546323264 7388308687 3142044233 7953113497 9229803686 8099590542 2742591092 0150266634 6466302829 7308130653 3599882742 3652030811 5091241272 0766369020 1292094203 7633499545 0234019264 1780132944 4896641568 5111746245 5118264667 7413152018 6862492942 9267959278 0705480911 2259853590 5700804470 6104705759 3085794898 2609729707 1491417990 5818379983 9750167659 2459009800 4422326913 5563035143 2043958032 1312999120 6360709865 5762520321 6913208033 9984981465 0856234048 0408001305 7692153217 9412428387 5222435111 8019565747 2373678184 3835176437 6757239322 1629685609 4097790743 1834851468 4797905298 7961005390 1052312739 4799150456 7822933455 5641178565 9860016648 7855952703 6129502571 2065179240 9618383009 6075140874 3006788967 6285464301 9263974934 7187050650 6958935963 9454037965 7975119424 5566652268 3623330464 4117436382 4242412141 3934954077 0486451799 0028546929 5350799588 9931896734 0282045275 5754698181 6773199585 7272440481 4019414774 7637207936 5187800214 0431699147 1183228662 8056988035 3440345125 4201026445 0541752525 2242849887 9917805478 6671065115 8101611729 1340855777 5453939888 7236261522 1514784531 2477484060 0572540509 2122665153 7711086024 4293725698 6347687196 1163887294 6220645467 7427873536 1750869645 3540485415 8407922872 1205173343 4651775973 4643683712 6340131791 7482801434 3230627159 3201376875 6695687180 4775907050 1185091556 1120175226 0749325968 9873451134 5271297279 7483009585 7094969914 4341870236 7318021757 6363879721 1534419763 4264640072 5297565252 4076728165 5100897648 3833301269 9849076266 4858594291 4764308847 1073675989 6095941103 2174391276 0601733061 7819546186 1077120849 3510440137 6629195961 5953321954 5130373667 2939254792 6617111229 1723373215 5424011173 9916502367 5447403171 7570153059 2986037885 2737839231 5337393936 6920524244 7198864502 5345336020 0056203937 0197452563 3081998867 7130132917 6707400625 2211663904 6981595722 1732327711 0142498013 8265824564 7245536664 7737361246 9206124906 6763015083 6338752628 9626941641 9311305259 1227555022 9634770068 2904903275 7852558984 6287296239 3265016669 1597774004 2535403729 2404920609 9363177973 4900557881 3994571571 9710204134 5173340399 5508578763 0012635908 0239953615 3029658569 0429647679 5156626512 1770089103 1106134021 6110287645 2606467929 2775158233 4956202191 1831755262 6794701481 2012538718 2203722523 8607027665 6516271988 2978827168 3850979784 6758286727 7431155380 9062584994 7676003399 2888479305 8003250125 9000982745 6047322683 8180245267 0979823114 6011211015 2568341942 7645644815 6710552995 7017038307 4623053062 8653228557 3311842506 1790019232 5208640669 0603815899 6591863344 1997881902 4507025885 4953774316 5452926258 2718290772 2125924343 9416587671 3834945805 2293833762 0223859818 5772162454 4418877085 3061588644 1480623182 4209094100 2358651697 5246446549 7941988144 5306537690 0347701996 2547397738 6283552317 4495121184 7917728089 5414607342 7212885423 9329785992 8072479799 4670915369 2028707239 0984937240 0347025367 6978176365 1194671013 3562823017 3852224238 8436009595 8664315315 4068243805 1019935918 6404729279 5568201684 0107451608 9625938977 4716326884 6221784723 2539761531 8988244902 7118260079 5734009224 6691041518 7276985377 5226378976 3135491880 4578130910 0071266753 2165138170 6671609937 7718538437 9883551538 3250472427 6263703580 7569992783 4608076637 1097239503 1364557454 3436100064 6813536198 1064782010 5226158064 0808190603 1514784196 4418991098 9156984100 3137970186 8009151910 7860867619 4581853299 8933558468 8634357109 8880444507 5556750993 3195506484 0061034310 5727215939 1234753975 3378512798 6539856341 9527339170 1245163946 1055008881 7100702611 3445463520 5150472666 0315246247 3921500655 4385746587 3650022339 7775028418 3160019669 9890754604 4037108207 4121757225 8849484971 4100639496 8466022657 4847560252 3138657823 5933159087 7254758078 7086833857 9381395166 2985368266 7499954130 0433110193 4193447969 6505560187 2851221293 2617424655 9795615448 7803694548 9921518544 4143407671 4792091693 1302682157 1389473131 8741259424 2314088208 0715243217 6199502976 1001002140 3140774904 9465580579 0775727631 2622410295 5932765880 2089161098 9331411966 9610055527 9442648905 7936322209 2473067907 9979064590 0242918088 2743442564 2372494532 6923039543 3167178850 2634985870 0253138693 1845449558 8920365503 1478903705 8181823850 7252340878 8798644647 1114399329 1545838696 3406264675 5548798704 9641189233 0707117253 2329416604 7412738649 5657539036 8221488569 4882193652 9681002414 3390115665 7547767444 0348158088 3144137809 4465434713 5183051769 4364580703 6014065770 7771207554 9195625809 2162863915 7075545445 5040449621 6144283577 6818643940 2714179068 3615169623 7292532534 3086240518 8742308066 2877918342 1649683538 5956121920 3523283142 1590563984 8996891763 6278767375 5928999148 9040979734 4491978849 7148660827 2013098251 1327738414 4438020374 8007152760 5161346899 4937973862 1320610486 6955212320 5598498370 2678583394 0871411341 0243476434 6111027218 7781489674 1432472671 8339094212 8396671756 4007792153 1789078369 6160535283 7789955802 6786696503 9399471197 8913081820 8095565038 8023311636 9771837416 4434457722 9860830283 6693344408 9818742888 8720796217 4178979874 2157835192 7014319208 6928082020 5065760515 4579428511 3325001689 2663148394 8765868098 7443037854 6178637360 0925584530 3416459431 4819360574 5850067460 7785056206 9757171837 1303003236 2137999263 6462414327 2246750986 4637987219 6054800543 1045264076 6880756352 4091430991 4895122193 4785800855 0344594179 4358732606 9944431012 5171691661 6166724403 0687812105 5988691506 9735133430 8822764989 6307457199 5799488320 9782747819 2152227561 5191922136 3351308405 0990457747 2210339755 8591247756 9072942401 4044472362 5273525724 3322044809 9812341689 3593104116 6463022755 5596528883 1696058996 0681962275 9743185908 3910656530 2029139695 4981013988 4131492835 1879376790 0922363587 6132571293 0420435563 2496728404 5002312952 6457378901 8785615884 0245445629 4215183407 8735955454 5146480430 1064052447 8290140070 3806605571 0828838841 0501752239 4643916854 4771210732 8019032182 3879075765 7888088525 1295896593 7919928877 4876935774 1565717132 4578486055 6664638226 7039684764 3245241286 2459799854 7349238956 0401293861 6713578513 8706747011 9940550019 0912724032 8043974878 7296150797 9921270791 7646726264 1298082915 6192087840 0728259113 5559311361 0820607195 0175696165 8984104890 8310926300 5095443263 3124523487 5448375031 8546120409 0867111366 5495989342 9395038091 5218319153 8746282722 2696766902 9543791464 2887652366 7866569221 2250439630 2738166206 8427648006 3645705288 6711821936 6802026812 7140721669 1824438028 1694546384 4474815580 9916432723 5583443752 5236185278 8131968963 3511321608 2870987959 6177325231 9823650917 2444931294 4712755572 4919158909 7496008055 6317466452 6281383283 3004695247 4285608905 8914929389 0703184533 6697873311 6534374824 8943968998 8010979645 9096908475 4550148078 3682852348 1325891853 6046039517 9233527952 0189568040 5624545335 3331125264 3810256444 4475276134 2284091684 5426000870 0077236303 6479925706 9735783601 3477805158 1981121307 2283177696 1863939686 8099640357 8193378108 0729788109 4538548107 8707633726 9233426518 8189374739 7501415969 7168536023 6788096498 0721970020 2576990063 8408003264 4122308925 0563450974 6601613158 8556460035 6376696305 5300005962 9472432905 6891794235 9047940807 1648452880 0603505118 3830870226 1908246819 1567632982 5050034644 2000250355 1667129157 6157257109 8731659179 7328331887 0716618672

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 ≡ 53 (mod 63) and therefore cannot be a square and N does not have exactly two prime factors.

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 = 14006 significant digits (14000 digits displayed)

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

Input file is:  IO\70A7207D.cin
Certificate file is:  IO\70A7207D.chg
Found values of n, F and G.
    Number to be tested has 37090 digits.
    Modulus has 10270 digits.
Modulus is 27.68746492% 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 = 10, u = 4. Right endpoint has 6283 digits.
        Done!  Time elapsed:  13328265ms.
    Running CHG with h = 10, u = 4. Right endpoint has 6048 digits.
        Done!  Time elapsed:  25265360ms.
    Running CHG with h = 9, u = 3. Right endpoint has 5796 digits.
        Done!  Time elapsed:  16151047ms.
    Running CHG with h = 9, u = 3. Right endpoint has 5692 digits.
        Done!  Time elapsed:  17369359ms.
    Running CHG with h = 9, u = 3. Right endpoint has 5553 digits.
        Done!  Time elapsed:  18135719ms.
    Running CHG with h = 8, u = 3. Right endpoint has 5376 digits.
        Done!  Time elapsed:  17352187ms.
    Running CHG with h = 8, u = 3. Right endpoint has 5215 digits.
        Done!  Time elapsed:  20907891ms.
    Running CHG with h = 9, u = 3. Right endpoint has 5054 digits.
        Done!  Time elapsed:  37424672ms.
    Running CHG with h = 8, u = 3. Right endpoint has 4712 digits.
        Done!  Time elapsed:  40897234ms.
    Running CHG with h = 7, u = 2. Right endpoint has 4501 digits.
        Done!  Time elapsed:  611766ms.
    Running CHG with h = 7, u = 2. Right endpoint has 4331 digits.
        Done!  Time elapsed:  660594ms.
    Running CHG with h = 7, u = 2. Right endpoint has 4162 digits.
        Done!  Time elapsed:  1267671ms.
    Running CHG with h = 7, u = 2. Right endpoint has 3922 digits.
        Done!  Time elapsed:  1098954ms.
    Running CHG with h = 7, u = 2. Right endpoint has 3562 digits.
        Done!  Time elapsed:  4110000ms.
    Running CHG with h = 7, u = 2. Right endpoint has 3021 digits.
        Done!  Time elapsed:  5429609ms.
    Running CHG with h = 5, u = 1. Right endpoint has 2210 digits.
        Done!  Time elapsed:  338062ms.
    Running CHG with h = 5, u = 1. Right endpoint has 996 digits.
        Done!  Time elapsed:  1058344ms.
A certificate has been saved to the file:  IO\70A7207D.chg

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

Testing a PRP called "IO\70A7207D.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=6.599080422 E-860 at X, ratio=1.084129774 E-1855 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=3.883058889 E-347 at X, ratio=3.614263791 E-1214 at Y, witness=17.
Pol[3, 1] with [h, u]=[7, 2] has ratio=0.632083022 at X, ratio=1.059710357 E-1622 at Y, witness=3.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.1607431466 at X, ratio=4.602983348 E-1082 at Y, witness=19.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.3125459556 at X, ratio=1.191239260 E-721 at Y, witness=5.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.0686159516 at X, ratio=2.130001264 E-481 at Y, witness=3.
Pol[7, 1] with [h, u]=[6, 2] has ratio=0.4690745216 at X, ratio=8.24607494 E-339 at Y, witness=5.
Pol[8, 1] with [h, u]=[6, 2] has ratio=0.594973278 at X, ratio=5.43478190 E-339 at Y, witness=2.
Pol[9, 1] with [h, u]=[8, 3] has ratio=0.001304284580 at X, ratio=5.95298133 E-635 at Y, witness=2.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.4387104916 at X, ratio=1.342812519 E-1027 at Y, witness=17.
Pol[11, 1] with [h, u]=[8, 3] has ratio=0.605936034 at X, ratio=6.389540706 E-484 at Y, witness=2.
Pol[12, 1] with [h, u]=[8, 3] has ratio=0.1302508875 at X, ratio=7.68536635 E-484 at Y, witness=5.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.4285375965 at X, ratio=2.700481293 E-529 at Y, witness=3.
Pol[14, 1] with [h, u]=[8, 3] has ratio=3.798221464 E-141 at X, ratio=1.033400749 E-418 at Y, witness=3.
Pol[15, 1] with [h, u]=[8, 3] has ratio=1.609427720 E-105 at X, ratio=2.935790603 E-314 at Y, witness=11.
Pol[16, 1] with [h, u]=[10, 4] has ratio=0.2732920955 at X, ratio=2.970173891 E-1007 at Y, witness=13.
Pol[17, 1] with [h, u]=[10, 4] has ratio=4.773847702 E-236 at X, ratio=4.548211068 E-940 at Y, witness=2.

Validated in 226 sec.


Congratulations! n is prime!
Goodbye!

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