Primality Certificate for (448^3613-1)/447 | ||
| Andy Steward | 9,577 digits | 08 March 2010 |
|---|---|---|
| Originally by A.A.D.Steward 2010 | ||
| A066180 #505 | ||
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.310856% factorization of N-1:
| From | Factorisation |
|---|---|
| 448 | 2 · 2 · 2 · 2 · 2 · 2 · 7 |
| Φ2 | 449 |
| Φ3 | 3 · 19 · 3529 |
| Φ4 | 5 · 137 · 293 |
| Φ6 | 200257 |
| Φ7 | 113 · 71706765217361 |
| Φ12 | 13 · 61 · 50796841 |
| Φ14 | 29 · 3509773 · 79254281 |
| Φ21 | 8317 · 14281 · 190825237 · 2877428566460281 |
| Φ28 | 709223033 · 983921177 · 93667917474097 |
| Φ42 | 43 · 211 · 4327 · 6091 · 129272683 · 2119196958943 |
| Φ43 | p112 |
| Φ84 | 9688728169 · p54 |
| Φ86 | 55012995385531 · 365221333329612271035664729243 · p69 |
| Φ129 | 125305956001 · p212 |
| Φ172 | 173 · 1033 · 2753 · c215 |
| Φ258 | p223 |
| Φ301 | c669 |
| Φ516 | 1734793 · c440 |
| Φ602 | 4817 · 10837 · 54181 · 2639934949 · 3226975249 · 22816177606307 · 1039063562011124693 · 62444157639352082413 · 3409971305014126460021724703 · 4055471492810719029160940563 · 9387841663688081676473594233219401499886815234627433739940856545121724318963112059540315210990445326786211328186172676530178499792930327159323709426914217984644277289193280498602063013095898506476098287414332391588724558561 · c308 |
| Φ903 | 3613 · 220333 · 8509873 · 234855853 · c1313 |
| Φ1204 | 379253889663483804683410537 · p1310 |
| Φ1806 | 43 · 5419 · 163751779901851 · 1074735422865427 · c1302 |
| Φ3612 | 14449 · 135803522116081 · 292430365533601 · 83369779616062297 · c2623 |
We need the product F of all the prime factors from this partial factorization:
| 4625846050 9221619121 0759256209 6038425601 2631990512 0593713158 0306344134 8687677801 4164346817 9596550394 9718111454 9484005101 2813791678 3176403824 9563709929 3539000841 1778369960 4051886374 5714821935 7155288000 7166702420 7022538939 7669258325 2551445035 7527890885 0187146610 0950724976 1899499926 2166488740 0431884523 5224311510 4292936842 0654280022 3488941619 8256355131 0854242764 9866596104 9128652996 8959069842 4391844692 3363484997 2744089994 5309750358 1901752675 2534571179 2509173798 0000507961 8450469115 4768443656 1749273226 7262715822 0335454524 5587713215 6121623867 9776040384 9508731863 7056542962 9301602098 0072082586 3996326154 3414577399 3014256266 1530987157 8991942597 4716131572 9940857237 2604310990 8973844809 7808405198 5705335419 2485000965 0677338330 6803295567 3669042756 7333760636 9139398214 4380020736 4411819966 9451705896 4640411695 4287271711 9061696374 9726548484 6606355772 5558495597 4199134886 2028275614 8201364214 1268579906 1239832561 3667130123 7917055508 0572913732 4686937087 5422281159 8444797764 9487229785 3529644986 1719029535 8840562138 0804630362 9062163309 4676679318 8342313277 3411405846 8192441062 4681142010 7533962148 6592603631 9038140887 3609671255 4157467588 3671755444 8466889346 0528926121 1734998166 7648551432 6426328659 9193360634 0256603639 8341576322 9657785939 3597798377 8430543818 0463197777 2498015750 4840224426 1607804338 7942580319 2388895241 3532111833 |
| 938 7841663688 0816764735 9423321940 1499886815 2346274337 3994085654 5121724318 9631120595 4031521099 0445326786 2113281861 7267653017 8499792930 3271593237 0942691421 7984644277 2891932804 9860206301 3095898506 4760982874 1433239158 8724558561 |
| 510 8830547690 5818140096 6902306998 1713603853 2446925667 5493388601 0594446334 5180156266 5314489231 9562933229 2299135418 1583117408 1828927286 8116955733 5438826353 5035397755 4417430125 3106125945 0617942162 7690224161 5072945916 7601623489 |
| 40 5892452332 5587465489 0551002726 7137577886 2077772329 7941583412 2274904490 9389214183 4496546678 5089178290 2559296592 1640870136 5569213657 9443502627 7487549593 5076034192 9769660744 3457998629 2096988848 5175508963 1993713569 |
| 22 6280473469 8667510475 4875304626 6700772972 5499877479 2123594318 6801460214 5078416691 6906008447 4968982866 0471599553 |
| 112120966 0173420767 0938198023 4850819534 0183642588 1005535942 6579507529 |
| 4409 6866362701 2391709708 0794168601 3446746133 2406107609 |
| 3652213333 2961227103 5664729243 |
| 40554714 9281071902 9160940563 |
| 34099713 0501412646 0021724703 |
| 3792538 8966348380 4683410537 |
| 6244415763 9352082413 |
| 103906356 2011124693 |
| 8336977 9616062297 |
| 287742 8566460281 |
| 107473 5422865427 |
| 29243 0365533601 |
| 16375 1779901851 |
| 13580 3522116081 |
| 9366 7917474097 |
| 7170 6765217361 |
| 5501 2995385531 |
| 2281 6177606307 |
| 211 9196958943 |
| 12 5305956001 |
| 9688728169 |
| 3226975249 |
| 2639934949 |
| 983921177 |
| 709223033 |
| 234855853 |
| 190825237 |
| 129272683 |
| 79254281 |
| 50796841 |
| 8509873 |
| 3509773 |
| 1734793 |
| 220333 |
| 200257 |
| 54181 |
| 14449 |
| 14281 |
| 10837 |
| 8317 |
| 6091 |
| 5419 |
| 4817 |
| 4327 |
| 3613 |
| 3529 |
| 2753 |
| 1033 |
| 449 |
| 293 |
| 211 |
| 173 |
| 137 |
| 113 |
| 61 |
| 432 |
| 29 |
| 19 |
| 13 |
| 7 |
| 5 |
| 3 |
| 26 |
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.310856%
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 = 187 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 ≡ 29 (mod 64) 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:
Welcome to the CHG primality prover!
------------------------------------
realprecision = 3506 significant digits (3500 digits displayed)
Input file is: IO\01C00E1D.cin
Certificate file is: IO\01C00E1D.chg
Found values of n, F and G.
Number to be tested has 9577 digits.
Modulus has 2712 digits.
Modulus is 28.31085618% 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 1444 digits.
Done! Time elapsed: 131360ms.
Running CHG with h = 8, u = 3. Right endpoint has 1356 digits.
Done! Time elapsed: 149265ms.
Running CHG with h = 7, u = 2. Right endpoint has 1252 digits.
Done! Time elapsed: 30735ms.
Running CHG with h = 7, u = 2. Right endpoint has 1209 digits.
Done! Time elapsed: 29953ms.
Running CHG with h = 7, u = 2. Right endpoint has 1145 digits.
Done! Time elapsed: 28062ms.
Running CHG with h = 6, u = 2. Right endpoint has 1048 digits.
Done! Time elapsed: 24360ms.
Running CHG with h = 6, u = 2. Right endpoint has 939 digits.
Done! Time elapsed: 22906ms.
Running CHG with h = 6, u = 2. Right endpoint has 830 digits.
Done! Time elapsed: 21938ms.
Running CHG with h = 5, u = 1. Right endpoint has 720 digits.
Done! Time elapsed: 6515ms.
Running CHG with h = 5, u = 1. Right endpoint has 537 digits.
Done! Time elapsed: 5156ms.
Running CHG with h = 5, u = 1. Right endpoint has 169 digits.
Done! Time elapsed: 11141ms.
A certificate has been saved to the file: IO\01C00E1D.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\01C00E1D.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=8.73489219 E-461 at X, ratio=9.21753060 E-628 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=3.080364082 E-166 at X, ratio=2.838563066 E-368 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=6.87147834 E-185 at X, ratio=2.136840562 E-184 at Y, witness=7.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.520534606 at X, ratio=5.937547426 E-220 at Y, witness=2.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.0806302847 at X, ratio=3.255821568 E-219 at Y, witness=3.
Pol[6, 1] with [h, u]=[6, 2] has ratio=0.2617982103 at X, ratio=4.436751282 E-219 at Y, witness=5.
Pol[7, 1] with [h, u]=[6, 2] has ratio=4.252504809 E-98 at X, ratio=4.904154976 E-194 at Y, witness=2.
Pol[8, 1] with [h, u]=[6, 2] has ratio=2.515528294 E-66 at X, ratio=1.396731690 E-129 at Y, witness=7.
Pol[9, 1] with [h, u]=[6, 2] has ratio=5.81881931 E-44 at X, ratio=1.140555297 E-86 at Y, witness=2.
Pol[10, 1] with [h, u]=[8, 3] has ratio=0.2345904083 at X, ratio=6.747402416 E-313 at Y, witness=2.
Pol[11, 1] with [h, u]=[8, 3] has ratio=6.49010056 E-89 at X, ratio=1.342042858 E-262 at Y, witness=7.
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.