Primality Certificate for (6583^2357-1)/6582 | ||
| Andy Steward | 8,997 digits | 29 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 28.582211% factorization of N-1:
| From | Factorisation |
|---|---|
| 6583 | 29 · 227 |
| Φ2 | 2 · 2 · 2 · 823 |
| Φ4 | 2 · 5 · 13 · 17 · 19609 |
| Φ19 | 457 · 23333 · 24688860464934056239 · p43 |
| Φ31 | c115 |
| Φ38 | 281429 · 24481381669 · p53 |
| Φ62 | 262819 · 381284749 · p101 |
| Φ76 | 741913 · 2201417 · 1114122533 · 537059119361 · 195086262288751999541 · 766795151059515353311792667179946453 · p49 |
| Φ124 | 5209 · 198277 · 28382609 · 29491417 · 245171870352161 · 2044159835388718212160499857 · c164 |
| Φ589 | 913311647 · 103649841112639 · p2039 |
| Φ1178 | 1640184094915783 · c2047 |
| Φ2356 | 2357 · 120157 · 1194493 · 1706231693 · c4101 |
We need the product F of all the prime factors from this partial factorization:
| 938919018 0104935106 4599047459 4669398377 6074716646 4374872340 4524922686 2146484556 4306573334 9602902480 8250395879 2902871536 5219301552 5479834334 0816930739 9011089113 0374536248 3959406633 1234728472 1019409634 3670189122 8356580699 2396969005 4662830783 8011351424 3203794836 2167404288 2775209768 2681948529 0053310489 9319730083 6745964139 8587133086 5166619675 0394132208 8460773357 1800776430 0751055638 2673002527 7667417702 0899501160 9075133826 9905783068 0449479059 4894558532 6560246778 6683195529 7615517003 4359129711 5194132435 7287478156 6045117765 5111384899 5477269043 6492000615 5339714837 3533935754 5258993156 5174939226 3017870373 6798963324 4130240170 1529711813 5797619729 5815742622 1488245008 6542107711 4296805712 7522036375 0727081918 3693053437 1516906509 1077340017 3988307360 5355958460 6370857759 6531649237 5234334738 7505187187 9098519433 2404297843 1699823359 0157761964 1873540165 2464095561 4034021284 9226607776 0258090396 1684730271 5068714152 9992572983 4964520974 3028602674 5295229761 9464245778 3044888903 5685331747 5528043089 2325147528 5279271036 6553166248 7096637037 8292956682 5014025647 6052542975 5101627451 0818123322 2114547262 6675820641 5008069726 9859287968 1912012341 7407771487 9185525893 9614837012 7180469018 4544578426 6122963403 6980872650 9507221514 6914573879 4627565616 3100483907 7675020038 9367315279 6649796276 4144248650 6090936321 4665697481 2179527358 8518882893 4809263224 8460456118 8998800794 5853145379 7533270188 5270709476 1385733248 4159433696 6881675583 2141107963 0987938266 9754386776 3108927397 1584598260 4742383531 1069412114 4719075787 8157306069 3333433959 5527568197 2817564747 5569261931 9925981545 7574408195 8149854041 5819757667 3916612735 1330574769 4455218570 2600064322 8676437519 8214818920 8807844608 6980363904 2424379788 0629157238 4338108239 7735971231 4892686707 2429942083 7945366196 0854755256 0071570599 7514460296 2515145993 3166596899 1232574074 1365685617 9579363276 0809441526 5346880905 9936307697 8383778368 5625817622 0756077587 7488486800 4515294075 2747327977 3864934774 8678735433 2199467166 8990288630 4773775396 8279235145 9235501250 8313694317 3626438053 7818354580 6005243059 8551235182 5259217644 6897899554 3453777553 |
| 3 5624066501 5897054119 9592210758 8348155873 3656108850 5128296178 5340848368 4600756591 3834476270 9479882017 |
| 782 2735609865 2418395259 4547042112 4503607363 5158390547 |
| 198766127 7998813003 5924403173 9691650534 3228641701 |
| 204 7894324987 9831491596 2960810398 0830020067 |
| 766795 1510595153 5331179266 7179946453 |
| 20441598 3538871821 2160499857 |
| 1 9508626228 8751999541 |
| 2468886046 4934056239 |
| 164018 4094915783 |
| 24517 1870352161 |
| 10364 9841112639 |
| 53 7059119361 |
| 2 4481381669 |
| 1706231693 |
| 1114122533 |
| 913311647 |
| 381284749 |
| 29491417 |
| 28382609 |
| 2201417 |
| 1194493 |
| 741913 |
| 281429 |
| 262819 |
| 198277 |
| 120157 |
| 23333 |
| 19609 |
| 5209 |
| 2357 |
| 823 |
| 457 |
| 227 |
| 29 |
| 17 |
| 13 |
| 5 |
| 24 |
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.582211%
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 = 33 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 ≡ 31 (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 = 4007 significant digits (4000 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\19B70935.cin
Certificate file is: IO\19B70935.chg
Found values of n, F and G.
Number to be tested has 8997 digits.
Modulus has 2572 digits.
Modulus is 28.58221050% 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 = 8, u = 3. Right endpoint has 1283 digits.
Done! Time elapsed: 461938ms.
Running CHG with h = 6, u = 2. Right endpoint has 1160 digits.
Done! Time elapsed: 67891ms.
Running CHG with h = 6, u = 2. Right endpoint has 1096 digits.
Done! Time elapsed: 69421ms.
Running CHG with h = 6, u = 2. Right endpoint has 1001 digits.
Done! Time elapsed: 77000ms.
Running CHG with h = 6, u = 2. Right endpoint has 872 digits.
Done! Time elapsed: 83641ms.
Running CHG with h = 5, u = 1. Right endpoint has 742 digits.
Done! Time elapsed: 7406ms.
Running CHG with h = 5, u = 1. Right endpoint has 627 digits.
Done! Time elapsed: 5875ms.
Running CHG with h = 5, u = 1. Right endpoint has 397 digits.
Done! Time elapsed: 33375ms.
A certificate has been saved to the file: IO\19B70935.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\19B70935.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=2.182652850 E-53 at X, ratio=2.861419265 E-449 at Y, witness=37.
Pol[2, 1] with [h, u]=[4, 1] has ratio=3.686213272 E-231 at X, ratio=4.889475764 E-231 at Y, witness=7.
Pol[3, 1] with [h, u]=[4, 1] has ratio=3.637197112 E-116 at X, ratio=5.97376074 E-116 at Y, witness=2.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.2367254006 at X, ratio=1.360764684 E-259 at Y, witness=3.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.790269829 at X, ratio=5.856032484 E-260 at Y, witness=5.
Pol[6, 1] with [h, u]=[6, 2] has ratio=1.869168650 E-96 at X, ratio=5.550517328 E-191 at Y, witness=11.
Pol[7, 1] with [h, u]=[6, 2] has ratio=2.806450085 E-64 at X, ratio=1.495313455 E-127 at Y, witness=3.
Pol[8, 1] with [h, u]=[8, 3] has ratio=0.2136972054 at X, ratio=1.526412442 E-370 at Y, witness=23.
Validated in 3 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.