Primality Certificate for (7565^2521-1)/7564

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

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 = 1081 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₁= 47 3178232439 2408437444 9485762902 4964399546 4286650885 8027873174 5246798490 2948718169 6258195253 8029728830 9635702532 2208494147 4690896398 5032744627 5477103667 5441911070 2125555887 9398171579 0082582969 2685655803 7581484666 5658783620 4985148324 5212442029 0393343627 6906799435 3103239672 8511251235 3592007428 0296575573 3392138311 4945703219 0232107583 3300934918 2984931947 2754091575 1125358287 8222120191 5051775868 6488188848 5873747446 1320287529 1089203138 0268874777 1274163659 4829912030 5332310055 6857794782 7502511070 2521304637 9745902394 3043088839 0968822091 4599730681 7486661175 0793897254 1489730440 9220620004 6943372758 4730244219 3186393148 3403476143 0000082076 2428552021 3258207428 3882575527 2932406412 0885589580 5781802697 2101165808 7248536998 1770971931 0571158124 1023898598 9999709443 9960867981 4258898527 1033571368 2203229167 1060279778 9697799638 8131656638 4313223264 9246471573 2724986175 1367787617 0819325802 1190240799 1962853923 6183537063 9818500345 8570261100 2824416683 9918682203 3757485146 2676205568 1828416015 3162873278 6829977975 4157442252 8003430952 3321702138 2179050344 4309582314 3385698411 9885705533 3281520701 1876953543 8775325155 5333793501 8797608907 5830922655 5270945043 7402485801 1765480395 8496931852 2047618841 3229264744 0144537724 0148915135 9840908925 6708657232 9868527596 3703024223 5638534182 9548171836 1793204620 1728323062 9977458232 0959304231 7003485201 9465204671 2328272709 7376138217 8005676200 4856956175 3403939983 7125044724 5779006267 8884325176 0248441181 3959715522 9515197326 7243646675 8389544214 5403452790 9132031374 0315852112 8803536899 9089229495 9814105373 6982061799 7707441831 1844268400 9605022706 0148681982 4087209393 3748850989 4196002258 7058626326 4484019235 2770554706 0817630764 0365989831 1121824656 0622222845 9465988660 8355463710 9745160820 4700526835 7897798380 4780001533 5543544145 3513064768 6237807353 4107611773 9725536469 0600080860 0223234898 6469825846 8696213865 7800427518 5300816701 3064920514 7175032943 4599937713 9142947076 8753760284 2369140317 8438326408 8620125213 9580749267 2420118302 9707795207 3089862661 6077544951 5904396234 4345101259 9353382144 9944792294 5276447688 3283193467 3991311134 7911511969 9711321042 0036127439 9606710271 3654666635 1777404843 7922338179 8907377799 7012158227 7179847464 3902179430 3869620268 6797040187 5679738781 8799166718 4154484953 8370138678 7256782286 7819255739 5053332878 8076303160 2612765054 2379724339 4038871090 7026647377 4144584443 8415601335 3230525806 9008706159 4381191975 9333340054 3381830395 8023748858 9880401035 3237473330 4901917119 5425433287 6660531884 6506488522 6476464574 4830001660 0524349705 8566190092 8094615400 7027113200 3328395734 9169681875 5861787280 6377108627 0944556463 0751090339 7546140670 2912128850 0555057481 1846373099 7887035315 6103686784 5622036705 5973663488 9274856502 0384311092 3144047940 4310595980 2427240410 8281832593 1563173205 2862449987 5945461515 6429557489 6525778285 8226979110 4206196094 0156157136 3272058025 0612459106 0225712943 3132313417 9004495498 4275656149 4705910082 1820218291 9788182271 3387609709 3626683985 0624838029 2343461074 5109587135 3705630744 4686959162 7380859719
• c₂= 8 4813835472 5093899949 5740577582 9047522288 9882944231 7070917957 4003448116 2784103894 7488263110 2133926719 2975520984 0476077199 5442948207 3831935266 8811452821 5266624411 3796974638 6353953350 8428641938 2359252469 6438819731 5275247491 3825386564 7195470188 4500512791 3326308963 4082937365 5965225867 2992410121 7982769194 2883172534 8044852890 6925979929 4241857162 1600149978 6637031793 4921790776 5564051085 2630996084 1793394575 5439083847 6696815833 7931695404 9822356913 8133280545 4424905405 9223527366 0426068580 0528394806 6884328062 1364801077 4564088766 9528041369 2991501376 6006779924 5271241905 4195142975 4725189590 6591327634 3473715419 3161863210 8514124402 0469049832 4420894646 5088648533 9510507358 9963472403 2820805447 6143892897 3571441682 6357055082 8687015178 4895735193 5989987957 7662133112 8765881376 8916252055 0353406596 3301734509 4160321502 6591180643 1568155456 8035699304 4868763078 5843184275 6519554153 4758860818 8585995718 1142287933 8343036472 3033636937 6245766114 7314002607 7766152257 0477871892 1304901091 3399838361 5432158685 7207170990 1338024522 5532261521 3297226202 8105670682 0353683974 4967043838 3867928975 1961314243 3400429584 3674371051 5589272422 1849267732 4237400068 1950230510 6781660649 3085501864 4141948411 1264155366 1768196279 6150271547 5989634429 8766058467 4355095389 1087389989 3402011419 6985042171 1623918201 0472872543 7134600357 0580557119 6573811170 5765703203 1503176465 3345688168 0784954048 0245553909 8785307457 0356241533 3240075649 5763727585 6784413064 8301763653 6871699035 3001521500 7897844428 0534069366 9793432468 4813107061 0779025290 1088431739 8436974339 9784732308 7157880804 8341246193 9517947700 9378368172 7490384665 9726510860 1813639793 4363517419 0460291266 7418536400 8135787742 3772315499 3688214012 8971929737 8719803998 7584013316 8585541762 2512201264 9331839484 4005056165 3112101953 1016766874 9847735431 8360684250 0645652661 7658525899 5080049186 8506288236 1385579780 7160399398 9698103065 2587842546 8374253595 0980269813 2888504857 3327938272 2631284073 4362750781 5898201073 3717979310 8300620204 8046423950 7462512724 3730738271 1023919849 6128610981 4870660430 6149099034 2516196315 9580807053 7314050090 7478729911 6372911823 8009707878 8097452344 3468936779 2590389964 8474059704 4976821679 3700338479 3819064174 9948676234 6044927527 8671700371 2632500387 1920373624 7612434101 9591595937 0610808292 7847080736 0632133275 5414392582 9844963193 7843810914 8642410280 3204164899 9813169134 3033496395 2907797595 3816225902 1661424304 1808262311 1487596466 2467025698 5702687981 0835542901 4193538036 3591925818 2004219615 3125803413 1317108110 4751435379 5285414106 4373920619 5271878024 4901236246 0766185436 5834064116 7628130489 3409823832 1737455573 0418654849 1804341080 7513560107 2547170833 7782890548 0128164837 0286261761 6346783056 6029871861 9585814696 5519903143 0981484057 6088644090 3755849611 2446134699 3439107264 8840348850 4264628693 3437032109 5772874677 4307698025 5428455250 0638144424 0965161371 8750057940 0177848579 4273137359 8104690264 0345533641 2327310677 6981427877 0562529005 8665015634 4861707926 5290824650 5435862807 5598822872 6509031599 8646515874 8801495540 7568118877 6614405926 5462273560 6228455910 4185746081 2253025371 6889759718 2003391435 7683627854 1334564106 6176241469 4504732504 0514741694 3376901720 5042329603 3837978814 7959760418 4543830733 0489794106 9252348672 0463048003 6975390969 8264193763 8276957977 4934229336 5134640017 9345752057 3511610018 9106435028 1738609024 2316726167 7284971746 0815372644 1524279624 7654738701 9774437865 3705001185 7393717724 0196639639 0192508807 1298003135 6611170120 6277944341 3031868990 2023291409 1918054639 5689751054 8985132230 3134593419 9649815835 0164982235 9396341904 9442025275 5912410438 0574950904 3221082749 2535668159 7765264761 2314374935 2483417559 6846897778 5431093460 2661751535 7325435876 8130583054 6107996853 7652642812 7114186769 0299519223 5626483453 4872216275 9105856633 4323451307 2647962308 6696176139 9480314942 3227327111 8477147936 0192472064 2027041961 5810730723 9516697525 8603271737 5411298269 4544846582 0398046300 7313049801 5143377005 0089980120 8425195251 3404934469 2987376286 9482447248 8849968345 9764641424 5105703866 5670680863 3639775825 3476742698

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 ≡ 17 (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 = 1252 significant digits (1250 digits displayed)

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

Input file is:  IO\1D8D09D9.cin
Certificate file is:  IO\1D8D09D9.chg
Found values of n, F and G.
    Number to be tested has 9775 digits.
    Modulus has 2932 digits.
Modulus is 29.99442924% 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 980 digits.
        Done!  Time elapsed:  201437ms.
    Running CHG with h = 5, u = 1. Right endpoint has 688 digits.
        Done!  Time elapsed:  32875ms.
    Running CHG with h = 5, u = 1. Right endpoint has 398 digits.
        Done!  Time elapsed:  15109ms.
A certificate has been saved to the file:  IO\1D8D09D9.chg

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

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

Pol[1, 1] with [h, u]=[4, 1] has ratio=6.16870964 E-398 at X, ratio=5.660001890 E-580 at Y, witness=11.
Pol[2, 1] with [h, u]=[4, 1] has ratio=3.823983703 E-291 at X, ratio=2.422086806 E-290 at Y, witness=3.
Pol[3, 1] with [h, u]=[6, 2] has ratio=0.00000001119161487 at X, ratio=2.713709000 E-584 at Y, witness=5.

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.