Primality Certificate for (6045^2341-1)/6044

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

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 = 34 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₁= 3620909 0690797678 2557292989 9235373684 2685103454 8975030233 4591347748 3752697413 8593312759 6471746922 5283422418 4917634948 8942755085 2494237277 4810267180 3432178602 5235717928 1469794321 2902413553 2106428700 1457772525 2979558481 1119116544 6247539440 6764061636 8440762068 6451996673 8728837858 0653494118 7880359244 9159398005 7011168224 4339796016 9039396731 0018609662 7170873298 5298744115 3531850481 1586594295 0729004852 5655636962 9184056884 2709252020 3113151768 4378411392 4700413541 7595980735 7217378619 3703235504 7046744662 6854007838 3515751866 3772780424 0877507014 8172106527 0003577370 0149915260 2595269651 2573251545 2884034536 9300523171 0279149172 3046791498 5853674536 5521277536 5429243266 8570133180 2966993656 3593043965 4271412798 7498529586 3310818710 7729923816 8855652008 2172796350 9085824289 7684901990 4319271543 0168691491 4279685952 6325720019 1877936118 0610354342 8780455884 9208255743 8455000474 4295323844 2507687408 4304652898 0397073151 2648263655 4856045935 2374269301 8700967435 4591234660 1060290757 9549948289 9847497056 3822208430 7938415637 3307697660 8118530983 2095312992 5901497360 4360370547 1683104915 3954961838 5240279952 4790163802 0680290919 2806654513 8187433108 4935504674 5771607684 2690600627 0302023597 0897240089 3629463486 3268905059 4828830353 9227558056 6323270455 8115764754 5589384575 2644361584 2364503324 3550868715 9058573022 7835060499 2356729933 1476534166 1533301358 1421458138 5783649808 0109304522 2032829023 1137335570 6042988284 5843380337 1343363896 2555321589 9158798921 2197603378 5972274655 7741692175 8084227386 5650015348 4543622163 1065939460 0313770177 2054355548 1273080714 6055169091 7267178868 1661923722 2335929141 5785915202 9326874075 8872552302 9336697313 7307846977 4810437404 9546635293 6290039062 4890413039 2163513536 4134182499 8681577520 8271115273 9429055686 6427858541 3968847040 4676846829 6404958709 2688529416 4709285119 2467651519 6953635088 3393564630 0918244137 8162927781 2575838192 5534365617 1775745623 7671431467 1580677287 1683879086 2003608585 9544541371 4823269589 8230029687 9727021685 1870875920 3482520146 3884235249 1992332251 9907562306 7195395687 1497500709 1341116632 0221773213 5324787320 9276988595 9095704584 3203420825 1450824587 6984104114 0386294287 5881909305 2785587932 7762539934 2603160872 8911113471 2808566887 1617310164 2349073072 6646200086 2699057868 5189253793 2098735199 5960174853 8918905463 6672287561 1198207058 9053921790 9478651512 7367684133 5069053485 7983001673 1692228869 5515083790 8019292519 6188345711 2296851741 4589156845 1262428398 1561025891 3880612040 9831472511 3235632151 3761434369 9214204484 0018154794 1043873015 4601897517 1515352802 2802649938 1755196563 1231537006 5773235213 9398112751 3366420788 9649926292 8463445587 5256883969 5391357889 3650433743 9472281850 1397716287 5023634866 5352007205 6343716465 4673191524 4958636117 5300544661
• c₂= 119383 5270556821 6752260117 1932925548 4464416551 9885700323 2075726530 6219121249 5051091899 4425997491 3171644797 7469492517 1224158354 4299523248 0214936169 9003970227 6386150647 8401975131 2069104328 6644889147 7020006086 1051390417 9285597533 1805160076 3939823561 9714146015 2997909192 2461793764 5003248474 1615808051 8930406459 2253860989 1045703418 8565983762 7501929362 0025444592 1099016498 8340220523 3868145026 1507574680 7741849330 0475491800 0264107585 2699061928 1149038018 2707438983 4516222235 3043029024 7617393081 0467212481 3245087132 9659531318 6257012695 3729527924 5028698665 2284940798 8800668739 3473325707 3059423055 1283074606 6723751685 8715004024 5026136271 4890157748 7046134416 3415512514 6659294095 2150000599 2769775412 5161090236 9351176408 0128075292 2927411053 6106714196 8280194566 8543172565 7234839564 2998058487 3133052037 2704109574 6734290912 4177424645 1046139408 0952962958 9388054746 9574007382 7150048395 7508447037 6446516985 6677590400 5860982197 8943745356 5941201323 9991476895 2267055871 0733069708 6255889574 9909338086 9370639905 3194110481 0099604658 3999979460 3417599910 2102117208 7420719038 9744051827 9066168584 1777509489 9740497574 0477092934 9501853653 0255642574 0115804113 2713646288 0785870470 4537852472 7935504565 1895713857 9647529808 9245155675 1943239654 6751344717 0671376858 5922354529 6283482650 8438209147 4015817715 7352074849 6887619276 9606266571 3373096148 4758881319 2814583415 9842283607 6500907126 5095293013 6916333481 9893945406 3016817512 4597555933 7690376361 6156960462 3703730425 7546090691 5883111812 2521140633 3851877543 5781467183 2790597995 8483463766 2445674368 8086604882 8908923620 6882329836 4122098622 8268934475 3447373038 2056210276 6545620478 4696732997 8994685226 4765970440 7280279961 9462134371 1931368907 8599467686 2247492782 9791752005 6603816705 9871951827 0437094071 1430369336 1203009127 4567940790 8022808530 1068977579 7688649214 6619054196 7488752328 6411391628 0771892130 1420019114 8692721361 1773311421 0201716129 6952668945 3901473218 0426194144 2393195407 1463999329 9411333806 5380520465 6173265503 2701127911 2062608987 1898333198 7094659243 1754806315 4034536675 7991596617 4995030893 1674823841 3684372921 8066718995 6347332731 2122618613 3647250322 0844480382 2887638176 7322092274 8645091321 0131461376 1470180673 9717488684 6342581248 7090688436 9521887322 6539468812 0394792068 5392041025 7311976714 2335301869 1395738897 0744635739 7043664208 1167838731 8718085113 5269327272 5042770682 9501761873 4302068779 4081381104 9802083300 3025425964 3618453974 5388843994 6688111125 7195880178 0022778773 0267757551 2346444223 7452390321 3914078798 2632280824 3646443616 0946143388 9309465550 0116697114 5328064169 5359013175 2422905429 2790179899 9219635545 3187057513 4265917329 3509128233 4029427369 8977008655 5302484072 3202142672 0427042278 5155519676 2377212087 7451408221 9082096286 0617473001 9253181579 3369547501 0642274345 0728622579 3634970401 3466729225 3049703229 4549486146 7214633732 4922902407 0234953032 3085629639 0161286188 1745449397 5388947577 6623582292 5914196791 3156295596 8822070677 1600803475 5913660895 6455489958 2625303417 3565221217 3891748583 9037770465 9685397432 8808426760 0793571971 0889311467 3125149402 3695515600 2283632647 2275019910 3299751501 6752461374 3825083937 7527930763 0326256308 2953057980 6128819624 1841205313 8567633684 8064222425 6955636920 9492460446 3475606435 6454434869 6521958990 1422988979 3134428120 6800348250 8824059482 6920061511 0786135438 2355929818 4820667716 1702778429 1473744356 0439511217 7431458665 9293382602 2056678450 3419883148 1960801731 2402444878 0446923056 4513928191 0459019024 1984977230 4827359076 7000777807 9846210461 9822412525 4549609965 6296273231 5825563813 3355831297 7830787365 2645120021 1090666906 7516305459 0688433037 8738742720 5740701800 7478196571 8673295914 9907332256 5926436710 0582867034

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 = 1502 significant digits (1500 digits displayed)

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

Input file is:  IO\179D0925.cin
Certificate file is:  IO\179D0925.chg
Found values of n, F and G.
    Number to be tested has 8849 digits.
    Modulus has 2647 digits.
Modulus is 29.91134073% 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 909 digits.
        Done!  Time elapsed:  63125ms.
    Running CHG with h = 5, u = 1. Right endpoint has 660 digits.
        Done!  Time elapsed:  26953ms.
    Running CHG with h = 5, u = 1. Right endpoint has 438 digits.
        Done!  Time elapsed:  12641ms.
A certificate has been saved to the file:  IO\179D0925.chg

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

Testing a PRP called "IO\179D0925.cin".

Pol[1, 1] with [h, u]=[4, 1] has ratio=3.538894116 E-413 at X, ratio=2.531687367 E-445 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=3.276268834 E-224 at X, ratio=5.429959888 E-223 at Y, witness=2.
Pol[3, 1] with [h, u]=[6, 2] has ratio=5.015799412 E-81 at X, ratio=3.216150347 E-498 at Y, witness=2.

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.