Primality Certificate for (4029^2731-1)/4028 | ||
| Andy Steward | 9,843 digits | 03 June 2009 |
|---|---|---|
| Originally by A.A.D.Steward 2009 | ||
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 28.612762% factorization of N-1:
| From | Factorisation |
|---|---|
| 4029 | 3 · 17 · 79 |
| Φ2 | 2 · 5 · 13 · 31 |
| Φ3 | 7 · 2319553 |
| Φ5 | 11 · 491 · 601 · 81198541 |
| Φ6 | 16228813 |
| Φ7 | 286721 · 14922167381835491 |
| Φ10 | 5 · 61 · 863736855881 |
| Φ13 | 131 · 131 · p40 |
| Φ14 | 511001 · 1448833 · 5776113869 |
| Φ15 | 6151 · 11285598785100187322128231 |
| Φ21 | 7 · 65471926213 · p32 |
| Φ26 | 13 · 168191711689 · 847317062099 · 9873372800100990311 |
| Φ30 | 421 · 164969562258881813519068861 |
| Φ35 | 701 · 766394418968424611 · p66 |
| Φ39 | 2494903073209 · 553765392137803 · p60 |
| Φ42 | 43 · 46327 · 10180591 · p30 |
| Φ65 | 35186427064514866118159007971 · c145 |
| Φ70 | 71 · 2591 · 1062671 · 400631981 · 204997810571 · p56 |
| Φ78 | 2731 · 205063 · 23470357 · 1625071506250999 · 31378403472251130347599 · p33 |
| Φ91 | 197149344142236881669 · p240 |
| Φ105 | 211 · 1507591 · 162625546112947845481 · p145 |
| Φ130 | 70981 · 254021 · 214586321 · 7264709401 · 1711395762920611 · 302983018868091937592054551764385202141 · 678614615006982943153665768889899672384691 · p50 |
| Φ182 | 1093 · 484871843 · 207415086061 · 667097251913 · 903105623296128071 · 3770264941431278805811843 · p183 |
| Φ195 | 1171 · c344 |
| Φ210 | 15331 · 830551 · 5645011 · 259590451 · 647994691 · 1094633076811 · 8361885664496987962871878921 · 54716832858540681551252855431 · p71 |
| Φ273 | 4302481 · c513 |
| Φ390 | c347 |
| Φ455 | 911 · 8191 · 2482833791621 · 635953322260621 · 227741365574880431 · p987 |
| Φ546 | 547 · c517 |
| Φ910 | 519611 · 416447313101 · c1021 |
| Φ1365 | c2077 |
| Φ2730 | 35491 · 1228501 · c2066 |
We need the product F of all the prime factors from this partial factorization:
| 7383303 1774474821 8543473324 6636854502 4356493361 4054380932 0701688926 6910499314 6963751557 1991015788 4961112489 4132009523 9802299805 7683643897 4324255600 7690470299 5438060755 0087220864 5132579646 3563604712 2048050123 1418847815 7820983864 8429265212 4303550078 9892366200 5855302192 9197765225 4217766443 2575102675 6227015939 2998768610 9244842005 9107886932 6351505426 0706999092 8087771415 7157492050 7492925445 6741365765 8510006023 1313743817 0744110194 6751929595 0083529192 0281479357 8631307981 3184605414 7383931054 6191083591 0751500791 5936499754 4047742153 8556413745 5454836869 6912936510 0938683628 4921385334 3707811117 2007967173 8132311903 3079433950 9540625467 1969257292 4526390079 8903319974 4148023974 0666290128 3769089059 5911523523 6119624169 1892519385 9702324049 3749295254 2645007868 2241542885 3241536997 4173009846 8924993156 7251821080 2718074570 0886774677 3996585675 1380342497 7575768107 5012938469 5581426296 8764623685 8726362382 3475225551 3408741311 3626194883 6000900096 8625868295 2778983040 4682266332 3274092093 4834022863 4681118911 |
| 1902392432 9833286917 4078544935 3777596452 0623344774 8357376773 6826872517 2528540305 6280539765 5535690616 2209695821 7800327928 4113429304 9347079908 1837052346 6823685508 7254521257 6294490970 5021167578 1745710501 2505292821 7343876518 5666826584 1573858909 |
| 150 2878927342 8490771710 9697128689 8289548311 8715221812 7732898009 5067140034 4462084157 4395944771 3834267812 7532032914 7717253444 8103169909 2474270018 0852312651 3069145910 7795695072 4118047351 |
| 21668 1523626793 2077028686 0170832665 2277175184 1387166875 8247459575 2701866781 3827600202 1941081440 3723041847 7581060684 2974954357 8579354966 5728851301 |
| 1 8501441633 3459667219 5154908368 9409847767 4389837158 1238717940 3663565691 |
| 622954 4039192271 9153856741 3596375974 2513470563 1899232122 4313911031 |
| 2422407057 1727496454 1122589821 8482491639 2310648890 3515367883 |
| 208556 0381848106 2536245553 9165912198 8473413749 4671911961 |
| 1133320249 0470891574 5972137828 6886927384 7768740221 |
| 67 8614615006 9829431536 6576888989 9672384691 |
| 1066430169 5189849801 2071482717 2058792461 |
| 302983018 8680919375 9205455176 4385202141 |
| 499 5859029664 2947691066 8082171721 |
| 39 9122530927 3497362069 8541997331 |
| 9024005765 3280739414 8658687171 |
| 547168328 5854068155 1252855431 |
| 351864270 6451486611 8159007971 |
| 83618856 6449698796 2871878921 |
| 1649695 6225888181 3519068861 |
| 112855 9878510018 7322128231 |
| 37702 6494143127 8805811843 |
| 313 7840347225 1130347599 |
| 1 9714934414 2236881669 |
| 1 6262554611 2947845481 |
| 987337280 0100990311 |
| 90310562 3296128071 |
| 76639441 8968424611 |
| 22774136 5574880431 |
| 1492216 7381835491 |
| 171139 5762920611 |
| 162507 1506250999 |
| 63595 3322260621 |
| 55376 5392137803 |
| 249 4903073209 |
| 248 2833791621 |
| 109 4633076811 |
| 86 3736855881 |
| 84 7317062099 |
| 66 7097251913 |
| 41 6447313101 |
| 20 7415086061 |
| 20 4997810571 |
| 16 8191711689 |
| 6 5471926213 |
| 7264709401 |
| 5776113869 |
| 647994691 |
| 484871843 |
| 400631981 |
| 259590451 |
| 214586321 |
| 81198541 |
| 23470357 |
| 16228813 |
| 10180591 |
| 5645011 |
| 4302481 |
| 2319553 |
| 1507591 |
| 1448833 |
| 1228501 |
| 1062671 |
| 830551 |
| 519611 |
| 511001 |
| 286721 |
| 254021 |
| 205063 |
| 70981 |
| 46327 |
| 35491 |
| 15331 |
| 8191 |
| 6151 |
| 2731 |
| 2591 |
| 1171 |
| 1093 |
| 911 |
| 701 |
| 601 |
| 547 |
| 491 |
| 421 |
| 211 |
| 1312 |
| 79 |
| 71 |
| 61 |
| 43 |
| 31 |
| 17 |
| 132 |
| 11 |
| 72 |
| 52 |
| 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) = 28.612762%
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 = 3 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 ≡ 2 (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 = 3506 significant digits (3500 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\0FBD0AAB.cin
Certificate file is: IO\0FBD0AAB.chg
Found values of n, F and G.
Number to be tested has 9843 digits.
Modulus has 2817 digits.
Modulus is 28.61276198% 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 1395 digits.
Done! Time elapsed: 76344ms.
Running CHG with h = 6, u = 2. Right endpoint has 1386 digits.
Done! Time elapsed: 73062ms.
Running CHG with h = 6, u = 2. Right endpoint has 1374 digits.
Done! Time elapsed: 73610ms.
Running CHG with h = 6, u = 2. Right endpoint has 1355 digits.
Done! Time elapsed: 74250ms.
Running CHG with h = 6, u = 2. Right endpoint has 1327 digits.
Done! Time elapsed: 74937ms.
Running CHG with h = 6, u = 2. Right endpoint has 1286 digits.
Done! Time elapsed: 76750ms.
Running CHG with h = 6, u = 2. Right endpoint has 1223 digits.
Done! Time elapsed: 80047ms.
Running CHG with h = 6, u = 2. Right endpoint has 1129 digits.
Done! Time elapsed: 84109ms.
Running CHG with h = 6, u = 2. Right endpoint has 987 digits.
Done! Time elapsed: 95157ms.
Running CHG with h = 5, u = 1. Right endpoint has 842 digits.
Done! Time elapsed: 6797ms.
Running CHG with h = 5, u = 1. Right endpoint has 746 digits.
Done! Time elapsed: 6125ms.
Running CHG with h = 5, u = 1. Right endpoint has 552 digits.
Done! Time elapsed: 37625ms.
Running CHG with h = 5, u = 1. Right endpoint has 166 digits.
Done! Time elapsed: 45562ms.
A certificate has been saved to the file: IO\0FBD0AAB.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\0FBD0AAB.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=5.070482872 E-518 at X, ratio=6.018633324 E-683 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=8.95990845 E-263 at X, ratio=2.299220667 E-387 at Y, witness=13.
Pol[3, 1] with [h, u]=[4, 1] has ratio=3.637902206 E-196 at X, ratio=4.336931226 E-194 at Y, witness=3.
Pol[4, 1] with [h, u]=[4, 1] has ratio=6.45317406 E-98 at X, ratio=2.204381076 E-97 at Y, witness=3.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.1952008985 at X, ratio=1.579613917 E-290 at Y, witness=2.
Pol[6, 1] with [h, u]=[6, 2] has ratio=1.356199559 E-37 at X, ratio=3.268657470 E-283 at Y, witness=11.
Pol[7, 1] with [h, u]=[6, 2] has ratio=1.421414975 E-95 at X, ratio=2.494140177 E-189 at Y, witness=5.
Pol[8, 1] with [h, u]=[6, 2] has ratio=7.43873951 E-64 at X, ratio=1.803494432 E-126 at Y, witness=11.
Pol[9, 1] with [h, u]=[6, 2] has ratio=5.094583662 E-43 at X, ratio=2.829570425 E-84 at Y, witness=3.
Pol[10, 1] with [h, u]=[6, 2] has ratio=3.017217692 E-29 at X, ratio=2.127248430 E-56 at Y, witness=3.
Pol[11, 1] with [h, u]=[6, 2] has ratio=1.679270444 E-20 at X, ratio=5.69473305 E-38 at Y, witness=7.
Pol[12, 1] with [h, u]=[6, 2] has ratio=3.543095748 E-13 at X, ratio=1.455638781 E-25 at Y, witness=3.
Pol[13, 1] with [h, u]=[6, 2] has ratio=0.000000001899176911 at X, ratio=3.114985401 E-17 at Y, witness=29.
Validated in 5 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.