Primality Certificate for (3284^2857-1)/3283

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

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 = 418 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₁= 153 8218806532 6028228912 3256598545 5317482706 5437986245 2179407297 4794346199 8725131930 3096228285 3919038485 2363269598 2298346813 9853624178 2747403298 2041641012 2473942943 9841079902 1837832612 1914203603 3619827891 5708570488 9240799779 7652294047 2176448690 5389078492 6562862954 1987480403 7852173268 4440331204 4854892752 7155175948 9840589417 8529406346 4940862505 6862648710 8534853803 7519607924 5101747732 4866576617 2311388228 6812097355 5584296294 1225186922 9193036027 4560372169 9924711748 8956427237 6214468026 2314206356 0260248681 2400550503 9038032958 1306565378 3468301984 5910635915 6712442102 2313539567 3540118586 9571979015 1819744102 3819879834 6563257420 1245164420 0860463158 8996140520 9000502516 4295572201 1397698468 8752323326 6559135115 6251962433 0402556195 7609762228 4655049513 0477046553 0459476232 5221569629 3641987330 4908905471 7730695181 8167678457 8434494734 4866368136 2033154180 5202615439 3998773980 4485494709 8399986929 3302987597 2840454982 4424399692 4100927255 9155726987 9753837542 7694581250 5363791594 0798644221 1266774123 4185163476 5404147366 1198471381 4897819119 9235757155 6106174283 4940103135 2265347860 3633212787 9217907664 8141935977 4250152960 9483942436 9757925547 9011132265 6937116332 9371603638 5541437336 3257342646 6681826172 0467741452 8672368008 0945311153 5502100977 0975414342 2239035386 2168925896 1076129161 3800426854 7167079102 2348703898 3290524827 2304464719 4167688756 0296253899 2945129080 1270523318 6277557803 5757252067 4688374875 9096921108 9173983213 1459928722 0183841816 8890766512 0641319150 7863230056 2482937307 7069222833 4746765652 9939004544 7044799970 4809414508 6152613066 1000044167 1270760488 3793569585 7135070294 6698440759 3203636357 4331013027 4372851141 0834492903 2893733890 2209524671 3441177278 8461683498 4249900005 1321924455 3448324764 2431283666 2016802300 2557009316 4076823833 7203583966 5601365131 2400509287 2037210272 3181892179 2536007777 3949541858 6855452950 6875495558 9562199413 3508336274 3277433948 3035519373 3560048900 3529606474 4182508839 4504972418 5939503939 6342260522 9965113856 0219544295 9826770754 5468732503 9017682626 3621699429 3620696948 4395974032 7215587228 8732695872 9934662147 3610613969 4479731359 4487230034 8409087655 0164716991 7746916581 3761545486 5458955856 2651155029 9671467468 3342555962 9583540924 4454521978 3783610920 8535638936 7668167593 4054023246 3888821872 8697814286 9390189383 9979289454 4475722360 2749992059 6379773770 5850421087 6675039665 4031383259 5469456201 0231257278 7186832108 9496201992 8919202884 1386424335 0147538076 1111200822 5333737616 9044558237 8249188938 1092273170 8917610691 6698463262 9252252701 3685349262 3053362401 2615501616 1086847246 1426195667 7540698622 6470512762 8049621319 2506992593 3246664641 3086683282 3243304165 9461899794 9190158222 3307397596 0908190302 6746362825 8106322884 2392897294 5739696632 5589153125 6832581914 8034313478 4919806785 0735332314 8003127902 2240017364 0206320720 2129800374 9651156967 4486535871 1052442094 9683064671 2458195232 7920340900 7821167833 7428042021 0393414701 6835604042 2548662479 6443704788 8648970351 0071252933 8268140639 2375790321 0599556176 6673307260 0593833284 0292343711 7195216892 2982302297 2969269798 4057921309
• c₂= 9073524 8990988952 8809342760 0541168423 3543562045 9621922843 8310437519 5272908175 0948591484 4280059468 4481957658 1329035621 5333702422 8064190006 8975301815 9859310461 1823778432 6272701909 6191076003 1066055626 0935558357 2231077144 4336567626 9336372095 7062773193 5311059615 6425681041 4597681199 9911595415 6013659538 0778076216 1307574113 0067542814 4954245101 1416181745 7621035311 6738499312 6972068372 2108152007 7480862891 3257142816 1136920482 5239660157 0810867042 4494343426 2456147422 3755038331 5866544505 3928528818 0379127758 7393120265 8115205115 1280916061 4927809190 0111424420 7704442974 5962802782 7001636439 7374708643 8773159690 4919250579 5408656515 5415590072 6531217313 9114563437 7595432909 1355579245 4530989907 6103446965 7367783029 8754289210 1447586364 2583181420 3111921796 5280373693 0621497570 5887416700 9020612628 0868363251 3310125262 8806802621 0792468824 8856799524 6666336237 5396866604 3739399503 3259637959 7249356320 6507043281 2625418868 2182101822 7883024408 8366564077 9504575131 6791371984 0043591562 1212722763 7880701015 8222679474 4624482686 1532179290 9515244589 8514811627 0100473216 2975356055 0515391411 0965020884 9364490811 9652532809 3111403281 4556086628 5462322882 2120060407 3802815525 1933074651 3197495153 9196205227 7583027518 2423982948 5937343248 4190047401 0565583015 3756506416 7342235258 0798943714 8386993420 7780066331 1615904931 4813717435 6419107977 0888954579 7754352156 9647015691 8376137059 4544127570 3554104741 9470516482 6671032784 2968625379 5765720792 3339067306 6394764939 8123169316 9821368453 9785776978 5958711402 3729292178 0681818781 5128108213 4645700419 8078632426 9110810016 9865595858 5552806188 2904227100 9062874940 4731233891 9507126018 1035207724 8163303639 2377320508 1181790475 2034412436 1554021955 1797419857 6759445045 9556644723 6050148980 9625020186 2884461829 8417860570 2201059347 0544977404 7534301259 0740869027 8875971403 9932293850 7277035196 5579147925 2452934652 9048068456 1191712375 5799868572 3553218455 2540574873 4720697951 4554136857 7509451549 0384331971 6139666470 5554850720 5843694483 4110529812 7513389145 1645950258 5843146128 4467636218 0589965038 8898608528 3449195434 1502592129 6047379613 4119925064 7378829607 2706307212 4046171765 8004620955 1193232565 2852307949 2266411272 1971862075 0684736733 6706265238 9506032972 8762113354 7775167769 0940803907 4734998647 4820369451 2528354209 7514697776 4898297571 9110144064 1310032257 5830239210 4194069452 7213149543 5316544448 1307096409 7882920862 3080765743 9460122661 4315719266 7548559963 8574484443 6334252118 7075819158 0206109392 4706193173 5332515210 0303568402 1733389182 6252918002 8880199102 1104249331 4461047432 4336561602 3166537605 6146296462 1699749290 7904658042 1222490352 8976435837 4402031981 3853326012 9391644912 1554855866 5818446798 9458796807 7262281084 2364164819 9239276525 8910319388 2650743456 5758938344 5711460555 9863212770 2101439394 7442355229 6883988563 7949138641 7859738124 9709726356 3116961219 2625819115 0083362594 2872050005 9130099199 3651830405 9089949575 8334539660 2627183492 8308520883 8508279784 3605441051 5902384728 5062821494 1665166256 6260975389 7411914731 9916098804 2150432113 0126482809 7014141851 0837099663 1937047653 3020972860 1359262604 1468721956 2395916437 0682062484 7837070539 0605366458 8074912421 0015592606 6984114866 3536803829 2525866803 1228963959 7534621932 7309384551 7856002222 1604551383 1243306004 0390223743 3459482056 0622995320 1205339842 9866729641 5037625732 3248358641 3662358431 4880730261 1814217766 3138321939 6394013319 0533840776 4235932626 0616383518 5338228852 0520967896 6370389583 9856021142 6622792277 7153529247 8048409310 1357698991 8677000762 9168603801 3884866940 3606920052 3131109184 6871829580 0092711198 4212583116 0153290318 3817952949 5769983683 8505231261 9985164638 7983805405 6236179678 3444925534 3861052028 9975256422 5181005660 0764535923 0124642236 5072331827 2613884813 9798621098 2059178304 1394895075 5977910557 2034470868 6581808822 3821045983 8112161714 3759307262 7829809491 6025199610 1721097367 9360541355 0367016694 0834032576 9934744975 0043687268 0720052437 0850482817 5727144641 9119206405 1578004013 3290187863 4682174682 5720339752 6827793149 4955518620 5851031390 3241848771 4005928210 1805171419 9980558016 3827622262 7233989119 0830337850 3329575074 1145344517 6203721012 2199800219 1528579661 2548808860 5631819272 9356583281 0110058440 2479904693 7281579387 2148814536 7386178265 0642907066 9973054854

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 ≡ 32 (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 = 3005 significant digits (3000 digits displayed)

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

Input file is:  IO\0CD40B29.cin
Certificate file is:  IO\0CD40B29.chg
Found values of n, F and G.
    Number to be tested has 10043 digits.
    Modulus has 2973 digits.
Modulus is 29.60260889% 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 1125 digits.
        Done!  Time elapsed:  103938ms.
    Running CHG with h = 5, u = 1. Right endpoint has 908 digits.
        Done!  Time elapsed:  26828ms.
    Running CHG with h = 5, u = 1. Right endpoint has 824 digits.
        Done!  Time elapsed:  29875ms.
    Running CHG with h = 5, u = 1. Right endpoint has 657 digits.
        Done!  Time elapsed:  32718ms.
    Running CHG with h = 5, u = 1. Right endpoint has 322 digits.
        Done!  Time elapsed:  15719ms.
A certificate has been saved to the file:  IO\0CD40B29.chg

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

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

Pol[1, 1] with [h, u]=[5, 1] has ratio=3.277324243 E-321 at X, ratio=5.254029306 E-643 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=7.40368827 E-336 at X, ratio=3.978480043 E-335 at Y, witness=11.
Pol[3, 1] with [h, u]=[4, 1] has ratio=8.88972581 E-170 at X, ratio=6.393116952 E-168 at Y, witness=3.
Pol[4, 1] with [h, u]=[4, 1] has ratio=2.120579725 E-85 at X, ratio=2.587782524 E-84 at Y, witness=13.
Pol[5, 1] with [h, u]=[6, 2] has ratio=3.439276271 E-219 at X, ratio=4.863276572 E-435 at Y, witness=3.

Validated in 1 sec.


Congratulations! n is prime!

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