Primality Certificate for (127^5281-1)/126 | ||
| Andy Steward | 11,109 digits | 17 February 2010 |
|---|---|---|
| Originally by Predrag Minovic & Larry Soule 2005 | ||
| A066180 #701 | ||
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 27.044011% factorization of N-1:
| From | Factorisation |
|---|---|
| 127 | 127 |
| Φ2 | 2 · 2 · 2 · 2 · 2 · 2 · 2 |
| Φ3 | 3 · 5419 |
| Φ4 | 2 · 5 · 1613 |
| Φ5 | 262209281 |
| Φ6 | 13 · 1231 |
| Φ8 | 2 · 17 · 137 · 55849 |
| Φ10 | 11 · 41 · 572311 |
| Φ11 | 23 · 47834644354838156839 |
| Φ12 | 457 · 569209 |
| Φ15 | 12354871 · 5434487431 |
| Φ16 | 2 · 14369 · 21713 · 108455953 |
| Φ20 | 5 · 6121 · 2211110558021 |
| Φ22 | 20681 · 383791 · 136447203773 |
| Φ24 | 4900321 · 13810367521 |
| Φ30 | 31 · 61 · 10321 · 3494801371 |
| Φ32 | 2 · 97 · 449 · 577 · 1307345761 · 69701991721291841 |
| Φ33 | 67 · 8311112557368919 · 2122792226459166188463373 |
| Φ40 | 24121 · 197161 · 81959617841 · 11750146678961 |
| Φ44 | 4973 · 32336393 · 118965659297 · 62275302280475873117 |
| Φ48 | 14696641 · 180980257 · 1721909210407886113 |
| Φ55 | p85 |
| Φ60 | 6481 · p30 |
| Φ66 | 444181 · p37 |
| Φ80 | 3041 · 355441 · p59 |
| Φ88 | 89 · 887911000010233 · 13448835367392450257 · p49 |
| Φ96 | 2515603719612228063460334260624417 · p34 |
| Φ110 | 11 · 2311 · 3851 · 4572981370647096705264191969354381 · p43 |
| Φ120 | 19136240073622081 · p52 |
| Φ132 | 34586389786428217 · 8046971367072948674519487817 · p40 |
| Φ160 | 212986024536641 · p121 |
| Φ165 | 331 · 3631 · 4951 · 7171749158971 · 245611713047994194157316283127023456410261 · p105 |
| Φ176 | 353 · 44594385645083231314087926038209432529 · p129 |
| Φ220 | 148299255609984405961 · 3145089071651425360481052801750540661283593906021 · p100 |
| Φ240 | 241 · 122401 · 537841 · 14239840081 · 1654916491681 · 10045038748805420182303844296353947753247131918881 · p51 |
| Φ264 | 1321 · 2113 · 16763701681 · 4738553694283764169 · 25437828193494205950913 · 37219634638919811896238194401 · 539574269847249553732795938167089 · p50 |
| Φ330 | 661 · 1280435096491 · 2873225092981 · 51111882130090945192261 · 153634732962277800922120895395167930091 · p81 |
| Φ352 | 165089 · 4639178088182177 · c316 |
| Φ440 | 11938961 · 43182481 · 544408642801 · c311 |
| Φ480 | 27361 · 588714871784161 · c251 |
| Φ528 | 3697 · 5281 · 13510353121 · 1902136354801 · c307 |
| Φ660 | 11507349563821 · 20295528491031276781 · c305 |
| Φ880 | 881 · 1224035671034695201 · p653 |
| Φ1056 | 1343233 · 397117249 · 56433468163458449337105217 · c633 |
| Φ1320 | 19801 · 3004321 · 199739271601 · c652 |
| Φ1760 | 123668207346245761 · c1330 |
| Φ2640 | 63361 · 427681 · c1337 |
| Φ5280 | 842698042561 · 18440982626881 · c2668 |
We need the product F of all the prime factors from this partial factorization:
| 152 9046606446 4633373213 9742801558 3894199228 7960463515 3725988500 9981084960 3538190367 5772661398 9722247855 5445109054 9484819594 3347456494 8426254406 9980204247 3316852056 1901926508 4351161837 1183279398 3230249600 6984277234 9649959573 7083230433 0230810222 3841690599 0771355818 2404875370 3554905299 5280634645 2426461485 4232846640 5319924987 3488380639 5145834732 3249424309 2441438153 1485996907 3544083255 1102436196 3482125181 1894956146 5163246399 0044216032 6063442664 0625571933 8500016012 0327790935 1324170355 2326667168 7019206248 3591376534 5256071640 8265640065 1053656490 8264883550 8145089530 5866818949 6002240295 5717327775 1496800994 3841275088 5801853735 2737172919 2541954054 5879191921 |
| 128009672 3134651595 8965246071 5812489656 2320083844 2130958207 3604004112 7354928240 9914039898 5148349597 3989015064 6908371559 8361745873 |
| 2 0657941052 3285943371 8612764018 5679822386 6569996737 7628097586 7800247750 3744298305 0254424141 5647538507 4956193461 7943954881 |
| 19378 0158122753 6483438459 9910296952 2850389571 7585485047 8283335632 0936120504 3829359801 7724431218 8807057341 |
| 4320685757 4433364638 5230476425 5402550839 0523959401 6109485244 1356921584 9860700219 1414212725 5224543621 |
| 14083 6642283192 0706260356 0305519796 7419117423 4859541004 4236866545 8211718644 6345991681 |
| 1 0470120419 5447889889 3870297869 5476768930 8949943058 5557041497 9616253877 6915375741 |
| 194059598 4347068340 0081283838 7411318717 6623960163 9241864881 |
| 10 9613100289 2040829522 6630278948 0937718477 4703302081 |
| 1 1715192109 0415958514 2381497899 6723247846 0483804401 |
| 1779001304 2766078248 5998090651 6399224879 7958858769 |
| 1004503874 8805420182 3038442963 5394775324 7131918881 |
| 314508907 1651425360 4810528017 5054066128 3593906021 |
| 133568705 3071403868 2611145063 8171294285 9159536289 |
| 319 5872947246 5863433927 0344056987 0013283371 |
| 24 5611713047 9941941573 1628312702 3456410261 |
| 5100797424 1156931512 6021180124 7879081409 |
| 153634732 9622778009 2212089539 5167930091 |
| 44594385 6450832313 1408792603 8209432529 |
| 2703463 2997371052 0315988266 2986604349 |
| 8338 2870598093 2050620987 4036056033 |
| 4572 9813706470 9670526419 1969354381 |
| 2515 6037196122 2806346033 4260624417 |
| 539 5742698472 4955373279 5938167089 |
| 7067152115 8124208014 9799111601 |
| 372196346 3891981189 6238194401 |
| 80469713 6707294867 4519487817 |
| 564334 6816345844 9337105217 |
| 21227 9222645916 6188463373 |
| 511 1188213009 0945192261 |
| 254 3782819349 4205950913 |
| 1 4829925560 9984405961 |
| 6227530228 0475873117 |
| 4783464435 4838156839 |
| 2029552849 1031276781 |
| 1344883536 7392450257 |
| 473855369 4283764169 |
| 172190921 0407886113 |
| 122403567 1034695201 |
| 12366820 7346245761 |
| 6970199 1721291841 |
| 3458638 9786428217 |
| 1913624 0073622081 |
| 831111 2557368919 |
| 463917 8088182177 |
| 88791 1000010233 |
| 58871 4871784161 |
| 21298 6024536641 |
| 1844 0982626881 |
| 1175 0146678961 |
| 1150 7349563821 |
| 717 1749158971 |
| 287 3225092981 |
| 221 1110558021 |
| 190 2136354801 |
| 165 4916491681 |
| 128 0435096491 |
| 84 2698042561 |
| 54 4408642801 |
| 19 9739271601 |
| 13 6447203773 |
| 11 8965659297 |
| 8 1959617841 |
| 1 6763701681 |
| 1 4239840081 |
| 1 3810367521 |
| 1 3510353121 |
| 5434487431 |
| 3494801371 |
| 1307345761 |
| 397117249 |
| 262209281 |
| 180980257 |
| 108455953 |
| 43182481 |
| 32336393 |
| 14696641 |
| 12354871 |
| 11938961 |
| 4900321 |
| 3004321 |
| 1343233 |
| 572311 |
| 569209 |
| 537841 |
| 444181 |
| 427681 |
| 383791 |
| 355441 |
| 197161 |
| 165089 |
| 122401 |
| 63361 |
| 55849 |
| 27361 |
| 24121 |
| 21713 |
| 20681 |
| 19801 |
| 14369 |
| 10321 |
| 6481 |
| 6121 |
| 5419 |
| 5281 |
| 4973 |
| 4951 |
| 3851 |
| 3697 |
| 3631 |
| 3041 |
| 2311 |
| 2113 |
| 1613 |
| 1321 |
| 1231 |
| 881 |
| 661 |
| 577 |
| 457 |
| 449 |
| 353 |
| 331 |
| 241 |
| 137 |
| 127 |
| 97 |
| 89 |
| 67 |
| 61 |
| 41 |
| 31 |
| 23 |
| 17 |
| 13 |
| 112 |
| 52 |
| 3 |
| 211 |
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) = 27.044011%
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 = 7 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 ≡ 17 (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 = 4508 significant digits (4500 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\007F14A1.cin
Certificate file is: IO\007F14A1.chg
Found values of n, F and G.
Number to be tested has 11109 digits.
Modulus has 3005 digits.
Modulus is 27.04401150% 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 = 12, u = 5. Right endpoint has 2097 digits.
Done! Time elapsed: 6395860ms.
Running CHG with h = 12, u = 5. Right endpoint has 2078 digits.
Done! Time elapsed: 6606515ms.
Running CHG with h = 12, u = 5. Right endpoint has 2055 digits.
Done! Time elapsed: 6914938ms.
Running CHG with h = 12, u = 5. Right endpoint has 2028 digits.
Done! Time elapsed: 6710078ms.
Running CHG with h = 12, u = 5. Right endpoint has 1999 digits.
Done! Time elapsed: 10193219ms.
Running CHG with h = 12, u = 5. Right endpoint has 1970 digits.
Done! Time elapsed: 11918359ms.
Running CHG with h = 12, u = 5. Right endpoint has 1940 digits.
Done! Time elapsed: 13567062ms.
Running CHG with h = 12, u = 5. Right endpoint has 1907 digits.
Done! Time elapsed: 6149157ms.
Running CHG with h = 11, u = 4. Right endpoint has 1870 digits.
Done! Time elapsed: 2709812ms.
Running CHG with h = 11, u = 4. Right endpoint has 1858 digits.
Done! Time elapsed: 2976563ms.
Running CHG with h = 11, u = 4. Right endpoint has 1844 digits.
Done! Time elapsed: 3211609ms.
Running CHG with h = 11, u = 4. Right endpoint has 1825 digits.
Done! Time elapsed: 3569797ms.
Running CHG with h = 11, u = 4. Right endpoint has 1802 digits.
Done! Time elapsed: 3945000ms.
Running CHG with h = 11, u = 4. Right endpoint has 1773 digits.
Done! Time elapsed: 4034594ms.
Running CHG with h = 11, u = 4. Right endpoint has 1736 digits.
Done! Time elapsed: 4324531ms.
Running CHG with h = 11, u = 4. Right endpoint has 1691 digits.
Done! Time elapsed: 11073141ms.
Running CHG with h = 11, u = 4. Right endpoint has 1634 digits.
Done! Time elapsed: 12722921ms.
Running CHG with h = 9, u = 3. Right endpoint has 1563 digits.
Done! Time elapsed: 1068000ms.
Running CHG with h = 9, u = 3. Right endpoint has 1549 digits.
Done! Time elapsed: 1102907ms.
Running CHG with h = 9, u = 3. Right endpoint has 1529 digits.
Done! Time elapsed: 1164203ms.
Running CHG with h = 9, u = 3. Right endpoint has 1504 digits.
Done! Time elapsed: 1117781ms.
Running CHG with h = 9, u = 3. Right endpoint has 1469 digits.
Done! Time elapsed: 1153766ms.
Running CHG with h = 9, u = 3. Right endpoint has 1423 digits.
Done! Time elapsed: 477297ms.
Running CHG with h = 9, u = 3. Right endpoint has 1362 digits.
Done! Time elapsed: 1544062ms.
Running CHG with h = 9, u = 3. Right endpoint has 1280 digits.
Done! Time elapsed: 2236641ms.
Running CHG with h = 7, u = 2. Right endpoint has 1172 digits.
Done! Time elapsed: 294390ms.
Running CHG with h = 7, u = 2. Right endpoint has 1133 digits.
Done! Time elapsed: 304188ms.
Running CHG with h = 7, u = 2. Right endpoint has 1076 digits.
Done! Time elapsed: 255906ms.
Running CHG with h = 7, u = 2. Right endpoint has 990 digits.
Done! Time elapsed: 216344ms.
Running CHG with h = 7, u = 2. Right endpoint has 862 digits.
Done! Time elapsed: 230109ms.
Running CHG with h = 5, u = 1. Right endpoint has 669 digits.
Done! Time elapsed: 26781ms.
Running CHG with h = 5, u = 1. Right endpoint has 366 digits.
Done! Time elapsed: 38485ms.
A certificate has been saved to the file: IO\007F14A1.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\007F14A1.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=2.080511667 E-51 at X, ratio=3.909099908 E-417 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.693215570 at X, ratio=2.570156750 E-303 at Y, witness=2.
Pol[3, 1] with [h, u]=[7, 2] has ratio=0.02777961680 at X, ratio=1.081172263 E-386 at Y, witness=3.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.517450944 at X, ratio=4.955438962 E-258 at Y, witness=3.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.1331863340 at X, ratio=3.697788539 E-172 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.4317702626 at X, ratio=4.656506330 E-115 at Y, witness=3.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.4973328526 at X, ratio=5.287347554 E-77 at Y, witness=7.
Pol[8, 1] with [h, u]=[9, 3] has ratio=0.0690953585 at X, ratio=2.698074536 E-327 at Y, witness=2.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.02876056491 at X, ratio=1.331863508 E-245 at Y, witness=3.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.548357342 at X, ratio=2.195116385 E-184 at Y, witness=3.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.574470913 at X, ratio=1.810151562 E-138 at Y, witness=11.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.1426110360 at X, ratio=4.721178010 E-104 at Y, witness=7.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.01944795394 at X, ratio=2.997295570 E-78 at Y, witness=2.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.01591322046 at X, ratio=7.770262628 E-59 at Y, witness=2.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.818908900 at X, ratio=2.692570718 E-44 at Y, witness=3.
Pol[16, 1] with [h, u]=[11, 4] has ratio=0.1422162408 at X, ratio=1.611390599 E-284 at Y, witness=5.
Pol[17, 1] with [h, u]=[11, 4] has ratio=0.2175129094 at X, ratio=1.084909089 E-227 at Y, witness=2.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.02714128704 at X, ratio=2.286719888 E-182 at Y, witness=7.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.0858793104 at X, ratio=4.390356546 E-146 at Y, witness=13.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.3576625523 at X, ratio=6.53572152 E-117 at Y, witness=3.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.1132456328 at X, ratio=9.96286497 E-94 at Y, witness=3.
Pol[22, 1] with [h, u]=[11, 4] has ratio=0.2649731978 at X, ratio=4.251030198 E-75 at Y, witness=3.
Pol[23, 1] with [h, u]=[11, 4] has ratio=0.1488892450 at X, ratio=3.136276423 E-60 at Y, witness=31.
Pol[24, 1] with [h, u]=[11, 4] has ratio=0.1041856110 at X, ratio=2.527595070 E-48 at Y, witness=3.
Pol[25, 1] with [h, u]=[12, 5] has ratio=0.4482649094 at X, ratio=2.746942746 E-182 at Y, witness=3.
Pol[26, 1] with [h, u]=[12, 5] has ratio=0.0634233285 at X, ratio=7.95989126 E-166 at Y, witness=2.
Pol[27, 1] with [h, u]=[12, 5] has ratio=0.2277968643 at X, ratio=8.78779439 E-151 at Y, witness=3.
Pol[28, 1] with [h, u]=[12, 5] has ratio=0.2105933065 at X, ratio=2.876106068 E-146 at Y, witness=2.
Pol[29, 1] with [h, u]=[12, 5] has ratio=0.4877534494 at X, ratio=2.898022793 E-146 at Y, witness=2.
Pol[30, 1] with [h, u]=[12, 5] has ratio=2.062340396 E-28 at X, ratio=1.152713068 E-136 at Y, witness=19.
Pol[31, 1] with [h, u]=[12, 5] has ratio=4.534435218 E-24 at X, ratio=5.803035422 E-114 at Y, witness=19.
Pol[32, 1] with [h, u]=[12, 5] has ratio=1.149618374 E-20 at X, ratio=3.919546663 E-95 at Y, witness=11.
Validated in 77 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.