Primality Certificate for (4233^2131-1)/4232 | ||
| Andy Steward | 7,725 digits | 30 December 2006 |
|---|---|---|
| Originally by A.A.D.Steward 2006 | ||
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.
As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 29.212169% factorization of N-1:
| From | Factorisation |
|---|---|
| 4233 | 3 · 17 · 83 |
| Φ2 | 2 · 29 · 73 |
| Φ3 | 1201 · 14923 |
| Φ5 | 11 · 41 · 1831 · 388893601 |
| Φ6 | 7 · 7 · 97 · 3769 |
| Φ10 | 9461 · 33927623981 |
| Φ15 | 13483741 · 502700881 · 15204197071621 |
| Φ30 | 31 · 12315552511 · 270068006589293761 |
| Φ71 | 12497 · 55807 · c246 |
| Φ142 | 3650092393 · c245 |
| Φ213 | 13633 · 451855352025139 · c489 |
| Φ355 | 2131 · 6431891 · 5793373237361 · c993 |
| Φ426 | 113560502224779064082809 · c485 |
| Φ710 | 27691 · 387516097201 · c1000 |
| Φ1065 | 2802682841235181 · p2016 |
| Φ2130 | 77483011 · 5987227651 · c2014 |
We need the product F of all the prime factors from this partial factorization:
| 298922 7715019262 2422705061 8110322562 1292628393 8276228477 6548375228 2523225563 5196124170 2551941517 2483407244 4027479520 4660636307 4705603491 4560102783 5992269405 5986203150 4093130300 9091424638 9018295247 1246962283 7123061988 7310180695 2018263913 6447667519 1708708341 2954966228 7858082081 6844927880 8904752648 3911596520 0008517626 1560539750 5589423795 3335691544 6597756923 0085303341 7042675988 1697806434 6107692995 8369618145 7667524398 8614028224 5849834328 7524327268 5712533519 8738112387 9280180679 3074029722 3620163355 4248967733 4158250827 4520381182 0499979886 9150697347 3675196883 4106233515 3767271502 7800691214 6866191982 1237594881 1598866577 5519356917 1102342207 3645100055 1544105823 7787913340 3719417551 2768920768 2493040183 7677528995 1584328752 2343486437 8429575335 8390055993 9266653761 1644603285 6170995319 8697233991 0174327343 2006719548 3437108171 2464337750 5396716329 4242908085 0217317699 5532584909 8547417980 6475802912 2854620335 3798725786 7062559555 1485101632 7490177752 5704699975 7151606315 4209940140 0211219305 6514310183 9939027952 5203716322 7771946451 6711448097 4620723875 7174868686 2139292451 9094465481 8036912835 7684731458 2471485247 2267515444 0005184226 3242706591 7646706996 4106754720 5215184531 9472678454 2056688029 0622428941 8096007145 0463209556 7801196162 2877825791 4407958844 0051597021 3317743535 0144396697 9770595887 1897135551 6707862067 8479244927 0678060424 6859610318 5484085267 8711723881 1696101985 2882691869 6646220456 8361570083 1063377353 1763759105 3777340723 2715375534 8604288058 8790733178 8829219837 4145573744 1677238980 6387181187 3973039336 0780326480 8788510473 0111854994 3172623451 0556802384 3222426720 4804837229 0664417053 3597398656 7206205072 6056416735 0363837356 1552767724 2204771814 2973391671 3762790282 3406518201 7826931097 2441131236 6229544041 7752996765 7628387938 2478776590 6990442307 7979886712 3632381689 8575940215 4661037995 8664100900 8915544092 1628769823 6743887940 2854655017 7968845028 9088988388 9544987293 7222113738 7438173215 7530469667 7593178879 4939606071 8856664303 6168574788 6249990080 6767795106 3173543789 5206156337 9533033068 4910158965 7815035947 7194682745 1376822181 |
| 1135 6050222477 9064082809 |
| 27006800 6589293761 |
| 280268 2841235181 |
| 45185 5352025139 |
| 1520 4197071621 |
| 579 3373237361 |
| 38 7516097201 |
| 3 3927623981 |
| 1 2315552511 |
| 5987227651 |
| 3650092393 |
| 502700881 |
| 388893601 |
| 77483011 |
| 13483741 |
| 6431891 |
| 55807 |
| 27691 |
| 14923 |
| 13633 |
| 12497 |
| 9461 |
| 3769 |
| 2131 |
| 1831 |
| 1201 |
| 97 |
| 83 |
| 73 |
| 41 |
| 31 |
| 29 |
| 17 |
| 11 |
| 72 |
| 3 |
| 2 |
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.212169%
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 = 6 suffices.
Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F4>N, N can have no more than three prime factors.
As F2 < N < F3 and N ≡ 1 (mod F), we can let N = c2·F2 + c1·F + 1.
Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c12-4·c2 is a perfect square.
Here, c12-4·c2 is ≡ 51 (mod 63) and therefore cannot be a square and this stage of the proof is passed.
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\10890853.cin
Certificate file is: IO\10890853.chg
Found values of n, F and G.
Number to be tested has 7725 digits.
Modulus has 2257 digits.
Modulus is 29.21216901% 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 956 digits.
Done! Time elapsed: 22719ms.
Running CHG with h = 6, u = 2. Right endpoint has 852 digits.
Done! Time elapsed: 22078ms.
Running CHG with h = 5, u = 1. Right endpoint has 697 digits.
Done! Time elapsed: 13109ms.
Running CHG with h = 5, u = 1. Right endpoint has 641 digits.
Done! Time elapsed: 13813ms.
Running CHG with h = 5, u = 1. Right endpoint has 529 digits.
Done! Time elapsed: 15781ms.
Running CHG with h = 5, u = 1. Right endpoint has 306 digits.
Done! Time elapsed: 7594ms.
A certificate has been saved to the file: IO\10890853.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\10890853.cin".
Pol[1, 1] with [h, u]=[4, 1] has ratio=6.14941379 E-129 at X, ratio=2.217693562 E-434 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=4.043857305 E-224 at X, ratio=7.11778416 E-224 at Y, witness=11.
Pol[3, 1] with [h, u]=[4, 1] has ratio=8.41856456 E-113 at X, ratio=2.023665136 E-112 at Y, witness=17.
Pol[4, 1] with [h, u]=[4, 1] has ratio=5.90703654 E-57 at X, ratio=1.635238360 E-56 at Y, witness=3.
Pol[5, 1] with [h, u]=[6, 2] has ratio=4.749557068 E-94 at X, ratio=1.230718473 E-311 at Y, witness=7.
Pol[6, 1] with [h, u]=[6, 2] has ratio=6.842199916 E-105 at X, ratio=4.736106852 E-208 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.