Primality Certificate for (9539^2341-1)/9538

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

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 = 17 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₁= 807 0086644840 0229715390 7332625100 8317978128 0507634513 3906694056 8343003618 5567978486 0632646364 6211637891 7277950632 2986440899 3050800218 9088611787 3718905897 1660135042 7730187155 1849880659 9691366176 9333942482 0940062777 6245441763 2497972245 9170878890 5733326003 7601341867 3928528757 6117746470 3608356115 7848581928 2490751791 1987639442 1802729279 8285265599 1662174588 6657995360 0919598936 6559813803 2153645918 0592081252 8720762421 1747436241 1569157018 8416475844 8540633213 8232084113 8893153232 9648777851 8161168485 7789038866 1417966878 0024724757 2744273462 8282011183 2884797079 8915334159 3128403038 9164488127 7383984124 2775020360 0069398516 3764121492 2041927133 4601632075 6707267500 3161021517 6762748602 7666889884 4654035991 6991210006 4211138728 5052427269 5355686010 2345842383 8263136028 2698157976 5017180417 8436472043 5948757541 1796153927 3307424733 7711639251 4998301071 5607224086 4039544718 8305050428 0215341094 1558429671 0775282303 3536682602 6619645721 2933050673 8394337597 9898197088 7081573058 5381730285 1985412616 1113452985 1448192351 8227774657 3337598024 2349117383 8064812897 0441092855 9172016519 4815489980 7899193551 9206272385 5486829731 9519941033 8208084869 1646953308 3514402704 3342985639 2025394022 5067642828 0659109115 9396234000 1396838495 8994323042 8034245104 5902893384 4342185667 6874085010 6042414518 7786116933 3136150241 6903330531 5072367149 1608205768 9582671119 4800061711 8430008981 9015872310 3676414956 7716496275 1879408365 1629022953 6830659085 6371621681 6181421428 1410095601 8810580930 8676525910 5433909514 4407624703 5387569813 5560823956 1686018852 9018085561 2647338173 1077966785 8467117948 1525683052 9876394259 1916314019 9567341668 2659292969 1962632740 2181840484 6844780507 3411314411 6664417457 2999091220 7487320724 4820350834 8926633961 5613535034 1263882645 2496087439 8455775640 4341131437 3373756980 7526557658 2890843969 1706130658 3994070653 9798429076 3927146504 5179416638 6371806313 1676424149 5879310536 4079712025 2278496991 0644158243 9642465059 2970703002 0326208793 3277627975 4580185289 9036957324 2113848817 8794575977 0458245192 7043900343 7633853532 6045667029 8853356908 8933280407 8295784008 2345716627 9605879406 4393424006 7696789834 0449361546 8175773045 6483095310 7365809650 4609549304 1970791397 1912953293 4606310622 6857580955 7600688791 7484830973 9642963410 1062212836 8537816579 5872945135 9650738550 2399080586 9197487102 5612175422 3485923749 0506292131 6571229611 5483790154 4924232846 3353071819 4524533028 5210376699 9781199710 3846877508 0871194926 0521277758 7618515377 9366169580 8639315687 5461723953 1318774345 5530182652 1731211807 8242778923 9506231186 3764483800 2693379806 5803763910 1394952456 7231240538 5103952962 5217536438 4269281562 6088220811 7389742298 3308474218 1670516814 5955740450 0866313556 2409165150 9868478939 0223889763 6738822386 7083260412 2167245225 2551446513 9306841092 4497661185 2282148074 9147748651 8909450959 6452012005 4453932729 3754732845 4237078588 1966407747 9331587167
• c₂= 1308156 3501770489 0757984127 6091430495 4267687366 3603536489 6482393550 9710066622 6673132388 8174416861 1558972672 1767972166 4334003090 5407794220 3965148452 6838239130 2266680593 8726426431 9411900324 4324942821 8285742754 4221843867 7743499006 6983576506 8527283766 6328514956 2730941159 2703426980 2256547776 7585858481 0564986692 0673415012 7651606975 4187971840 7330809652 3118685675 9252444952 6645582674 6262885009 4614377589 4438353749 0166030030 0298665544 0939873374 7776280797 9424718491 0325002192 2557015441 5454863223 3706527148 1727090250 6944710843 2002636695 3198804046 7531770331 8360177531 9312749423 9021773672 0033626889 0884301845 0742935808 2093383503 2347011707 7382613484 7399794149 0253212335 2641454455 2921343373 4132313198 4015691546 6705895598 0499687286 1003883816 1139518477 1240191178 3576653820 8833730219 8668842730 4907609072 1829985595 0989497073 3501374882 5844382005 9978084388 9859976929 1467219906 0771791382 5311769362 9853827551 1819969923 8563914285 6979488445 0168660567 8764116529 5124372021 6003633791 0122609254 2043800489 6338253349 5911834157 9342460087 4763592426 8198799065 0082978845 6204744585 3792128003 2187620675 0768136136 7709134342 6507129181 2445499374 1542136860 1300561970 0930816867 1826523050 8529176483 0024519041 0053447356 0238850530 1780150569 2515899700 9318246083 4615276975 5200781086 3065952012 2329465828 3785951495 9131593236 4936268100 2925019401 7920743842 4796408585 4040886482 9620798398 1540002344 0720994380 7372898297 6655037284 6004235188 4254253497 6166874008 6170422176 9702317180 5398103219 5194036171 9047902688 1322457052 9995915847 7623635336 7904791541 6294264424 9237126297 8107993585 3516455671 9964906807 9056635229 3002523912 2489871943 8038587334 0302651359 4904755244 2293556603 9882150970 5236802667 1464668217 1197271043 8223924008 9983104964 4489912956 4743490171 7954387759 4791794121 4715957421 5790360309 3973168442 7628503284 0207576718 7949171407 8907129047 1556245816 2008135743 7849081917 6877188893 0707338526 5376198972 0473746268 6389324142 2252411654 5951573292 9542457921 5978596918 5695863441 5919925527 2220691886 6434602403 0741274578 5374207624 9194179271 2729953203 4052340188 3947528553 4696861063 8579426008 3887986456 9071856300 5414378892 6697759149 7011588339 8620642246 1573820081 7093971973 2792300301 3521656447 5677696080 8194429954 9706742572 8036093549 8537273017 7512234551 6159360199 2916969843 5288536894 9947135938 1227619503 4055163244 2426970401 9786695633 4975074399 5931764751 7015863876 4326817925 8482044089 2898077168 9347367947 3319605950 2683985249 3076339726 4273733000 9021154505 7225071150 8437889433 3864076661 6117333597 4219998721 9326644774 7193170198 3103875623 6312317958 3925362450 1769952864 4993945482 3992220653 3067357423 6484298598 1581140154 2064701802 3807337549 6415888451 7466003580 5782439696 5150703291 0299774322 8645648419 7962722370 1574959550 6696611571 5033035288 0576584767 3511896492 4561306266 3143412807 9135424385 8881187382 6558351810 8929898699 3858172804 8187205628 7982777043 6939097643 6339016648 3578507881 1727859777 7932876069 4429249251 5269149701 2773815849 0922370483 3511748980 8421645057 2815102440 9479115477 7135940748 0790437788 7633363795 1430106577 8615645628 0045624400 6669340301 8638213762 0474832395 9708990691 3363301665 5536149649 6850654480 8071509732 3108271218 3990832760 4966170331 1981499359 3209120762 4180089992 6208692698 5647275192 9070488645 1664937132 0460845870 5676007371 0943042253 1666086930 6493131679 2527501696 9135661388 0326611122 7633696869 5137085768 6598110627 5704368542 5536856295 8596252972 6393446685 4811801427 0841877321 1799342367 7094488039 3839627483 2858045411 0073139090 9099163753 1381196851 5022759245 5432352497 0712105547 1145397892 8933379633 0913986261 0737996794 1611466683 3066971174 7321083950 3196264995 4681973497 4759483648 6158055906 8818217852 8962608714 2718137324 1935951785 1924400478 1536306581 9527230170 3930070831 1546151630 2367726684 8050866072 2964405706 7357130846 8821809688 4859361132 1238729968 6215116010 7632218376 2243870122 1789379449 2110458028 0361736374 6894362219 7658132715

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 ≡ 21 (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 = 2003 significant digits (2000 digits displayed)

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

Input file is:  IO\25430925.cin
Certificate file is:  IO\25430925.chg
Found values of n, F and G.
    Number to be tested has 9313 digits.
    Modulus has 2773 digits.
Modulus is 29.77823339% 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 994 digits.
        Done!  Time elapsed:  66641ms.
    Running CHG with h = 5, u = 1. Right endpoint has 758 digits.
        Done!  Time elapsed:  30734ms.
    Running CHG with h = 5, u = 1. Right endpoint has 592 digits.
        Done!  Time elapsed:  36469ms.
    Running CHG with h = 5, u = 1. Right endpoint has 259 digits.
        Done!  Time elapsed:  21000ms.
A certificate has been saved to the file:  IO\25430925.chg

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

Testing a PRP called "IO\25430925.cin".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.048203082 E-394 at X, ratio=7.38800918 E-653 at Y, witness=29.
Pol[2, 1] with [h, u]=[4, 1] has ratio=1.378306325 E-333 at X, ratio=1.517953822 E-333 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=7.459576484 E-168 at X, ratio=2.760424603 E-167 at Y, witness=2.
Pol[4, 1] with [h, u]=[6, 2] has ratio=3.895856371 E-210 at X, ratio=4.200329190 E-472 at Y, witness=23.

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.