Primality Certificate for (5024^4201-1)/5023 | ||
| Andy Steward | 15,545 digits | 30 December 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 27.410713% factorization of N-1:
| From | Factorisation |
|---|---|
| 5024 | 2 · 2 · 2 · 2 · 2 · 157 |
| Φ2 | 3 · 5 · 5 · 67 |
| Φ3 | 43 · 587107 |
| Φ4 | 4129 · 6113 |
| Φ5 | 31 · 71 · 289510909001 |
| Φ6 | 3 · 7 · 19 · 63247 |
| Φ7 | 29 · 211 · 192238817 · 13672964887 |
| Φ8 | 17 · 521041 · 71924641 |
| Φ10 | 5 · 11 · 11581088970791 |
| Φ12 | 13 · 37 · 178933 · 7402237 |
| Φ14 | 36947 · 435143167189505531 |
| Φ15 | 61 · 61 · 9297931 · 3175002151 · 3694201501 |
| Φ20 | 15241 · 397928843981 · 66923422868381 |
| Φ21 | 84211 · 365502481 · 314249499901 · 26728548018032954311 |
| Φ24 | p30 |
| Φ25 | 251 · 601 · 241707948551 · 11863249648478583125097101 · p33 |
| Φ28 | 281 · 66221 · 199174347653 · 69768613676092772660671817 |
| Φ30 | p30 |
| Φ35 | 491 · 911 · 83791 · 594756961 · p70 |
| Φ40 | 41 · 32704670418257057058721 · p36 |
| Φ42 | 7 · 51326040727224703441 · 719856946481038048350823 |
| Φ50 | 5 · 151 · 3251 · 22527151 · 106333023588869101 · p44 |
| Φ56 | 113 · 5657 · p84 |
| Φ60 | 62701 · p55 |
| Φ70 | 701 · 197179501 · p78 |
| Φ75 | 5101 · 4762801 · 3502944001 · 1544302794824498851 · p110 |
| Φ84 | 3697 · 1187819221 · 590896627558400773 · p59 |
| Φ100 | 101 · 97960849801 · 219110351121001 · p121 |
| Φ105 | 1067221 · 1607131 · 1681891 · 4999681 · 5141489447632861 · 211679683754109271 · 993621944389343591808147748171 · p90 |
| Φ120 | 190458768723841 · 292672058490401600039564281 · 54687868670625050342411006041 · p49 |
| Φ140 | 102481 · 31878421 · 7960689135494577267619261 · p141 |
| Φ150 | 459984901 · 240994726351 · 1058989956151 · p116 |
| Φ168 | 8233 · 3356641 · 328957381954321 · 277065571922974655857 · 4755903799504950082033 · 1112571264990107407663417 · 1919080824134026223755750205960036677369 · p48 |
| Φ175 | 2536596068651 · c432 |
| Φ200 | c297 |
| Φ210 | 421 · 252001 · 24180661 · 460554870065344111 · 10818868328650416257982151 · p120 |
| Φ280 | 8695121 · 2625147364532199013081 · 303395838091019638453441 · 424715962400432042875875033381241 · c271 |
| Φ300 | 263101 · c291 |
| Φ350 | 1051 · 6301 · c438 |
| Φ420 | 2521 · c352 |
| Φ525 | 10501 · 109696651 · 1645675501 · p867 |
| Φ600 | 4282834773417601 · 4351612537653001 · 6263531800844045362801 · c540 |
| Φ700 | 5811316581718201 · 70424878382331197201 · c853 |
| Φ840 | 4201 · 677041 · 1258961761 · 899092674414481 · 9355720069458575614952424121 · 651818097911033610328467250801 · p620 |
| Φ1050 | 22051 · 4085546851 · 2958346815714105901 · 5914807898907370553577901 · c832 |
| Φ1400 | 2801 · 36174601 · 17734243801 · 43434445601 · 459321167069801 · 443842351203360606001 · c1710 |
| Φ2100 | 56093101 · 245164957801 · 64934589686401 · 387463575484023045999601 · c1720 |
| Φ4200 | c3554 |
We need the product F of all the prime factors from this partial factorization:
| 9422000 9502623430 9051106922 7843303455 2682360368 3943435812 9582398316 2163109828 9444834414 6491892954 3137344072 5161452249 9798304614 9543031240 2372061393 1423670975 8377171706 1342730239 3296649939 3947156746 1245019273 3629008659 8574142767 4197362582 6830128064 7554584958 7053126035 0775196017 4177140468 0847394412 3070792273 9196152189 0346642689 4199985340 9414106513 6724810114 7729611187 8349465374 2515740759 3738981635 7351148764 3120035865 1754360566 6935135286 4858451052 9963847308 4437791013 8336650861 6346813643 0831427484 2147713311 2716526896 6019910464 8807940526 2479730506 2410139256 7874016978 1991602309 3945148741 8827721493 8805538163 1861310162 6961166975 5900593456 8079191235 9586590973 6299761963 8901235445 6294982737 9657525756 9912315526 6059098995 8914965456 9110807873 5200659894 5046813473 2591462174 3974443262 4724667280 9048041414 0131473959 1857005737 9736139424 0493166939 7932298108 1998753458 3446486851 |
| 2034889436 0215513006 0571767591 9918566075 7164208630 1230277211 5466873661 6869337528 6956561444 5256040821 3735664090 7547500047 0081595987 9058455925 6613917254 6338231478 4525257478 1847511504 9740163916 5948299745 1766444883 6558187694 8942082514 9719012333 4157621025 2706378369 6717670813 2514815743 6256373443 3792615682 1817964790 5067465797 0698060328 4457108557 1406170956 7296715251 7431599231 6497707492 9373270685 5987366168 8087310504 5463370118 1625061406 8338261755 0484345922 7119518428 0623870326 6085773040 4147428588 1030124288 9342058394 9849055036 7231866053 9634635561 4184424568 4160031213 2784986640 3700240207 7592552262 9506391948 5851806464 0894877201 |
| 1 7190617246 9409872173 9515475904 8357642669 8938804322 4229794433 9339208095 6633926697 6583864818 7567099458 0227371494 6290247111 8866825700 2361320241 |
| 5 0809908947 3685985067 2253454580 1096171974 5985137320 0774562568 3623638417 2573020815 8163110593 6872532891 8568540408 8960271101 |
| 3496874908 4924483106 9314528751 6156629582 8624063632 3735032971 0814312816 8626304872 6911144177 6735005116 9378308068 9243454161 |
| 938301 2021880271 9978831818 0395075471 7044922573 0018217414 1911102732 6469740890 1063626476 3338206400 9490290772 7420602101 |
| 8381115340 8129186684 4087748868 9207015216 0011953685 3801175034 5203621662 9379019105 4870817815 3469341256 4826143751 |
| 2867039283 2522108072 5506768946 3187998124 0459846179 2110938004 3746934155 0131939744 7613218981 |
| 1045 9875499009 4972677895 4278296233 5538998554 7693670127 3644153180 9071640144 8716213561 |
| 48383556 8417290726 5963072208 6139931794 8186220871 4579078986 0883559337 9273937001 |
| 2998940909 6465798373 1821358692 4886796599 5256475103 4311515467 4092753251 |
| 257679485 1980821053 2395223922 3802848486 6552070298 6261538601 |
| 26273 6034967614 5663496496 6267929616 6182682902 1878992101 |
| 890256084 7429045893 5808216419 1370198976 1748781041 |
| 17480059 1525969577 6674391541 2303456797 4920080729 |
| 1785 0659258571 0847311098 7460966263 2558388851 |
| 1919080824 1340262237 5575020596 0036677369 |
| 122857 1561063814 1463305394 2120126841 |
| 424 7159624004 3204287587 5033381241 |
| 242 6329726035 9538511412 1501102001 |
| 9936219443 8934359180 8147748171 |
| 6518180979 1103361032 8467250801 |
| 4059602218 7172667004 5135082401 |
| 4058794337 7107168656 5455462401 |
| 546878686 7062505034 2411006041 |
| 93557200 6945857561 4952424121 |
| 2926720 5849040160 0039564281 |
| 697686 1367609277 2660671817 |
| 118632 4964847858 3125097101 |
| 108188 6832865041 6257982151 |
| 79606 8913549457 7267619261 |
| 59148 0789890737 0553577901 |
| 11125 7126499010 7407663417 |
| 7198 5694648103 8048350823 |
| 3874 6357548402 3045999601 |
| 3033 9583809101 9638453441 |
| 327 0467041825 7057058721 |
| 62 6353180084 4045362801 |
| 47 5590379950 4950082033 |
| 26 2514736453 2199013081 |
| 4 4384235120 3360606001 |
| 2 7706557192 2974655857 |
| 7042487838 2331197201 |
| 5132604072 7224703441 |
| 2672854801 8032954311 |
| 295834681 5714105901 |
| 154430279 4824498851 |
| 59089662 7558400773 |
| 46055487 0065344111 |
| 43514316 7189505531 |
| 21167968 3754109271 |
| 10633302 3588869101 |
| 581131 6581718201 |
| 514148 9447632861 |
| 435161 2537653001 |
| 428283 4773417601 |
| 89909 2674414481 |
| 45932 1167069801 |
| 32895 7381954321 |
| 21911 0351121001 |
| 19045 8768723841 |
| 6692 3422868381 |
| 6493 4589686401 |
| 1158 1088970791 |
| 253 6596068651 |
| 105 8989956151 |
| 39 7928843981 |
| 31 4249499901 |
| 28 9510909001 |
| 24 5164957801 |
| 24 1707948551 |
| 24 0994726351 |
| 19 9174347653 |
| 9 7960849801 |
| 4 3434445601 |
| 1 7734243801 |
| 1 3672964887 |
| 4085546851 |
| 3694201501 |
| 3502944001 |
| 3175002151 |
| 1645675501 |
| 1258961761 |
| 1187819221 |
| 594756961 |
| 459984901 |
| 365502481 |
| 197179501 |
| 192238817 |
| 109696651 |
| 71924641 |
| 56093101 |
| 36174601 |
| 31878421 |
| 24180661 |
| 22527151 |
| 9297931 |
| 8695121 |
| 7402237 |
| 4999681 |
| 4762801 |
| 3356641 |
| 1681891 |
| 1607131 |
| 1067221 |
| 677041 |
| 587107 |
| 521041 |
| 263101 |
| 252001 |
| 178933 |
| 102481 |
| 84211 |
| 83791 |
| 66221 |
| 63247 |
| 62701 |
| 36947 |
| 22051 |
| 15241 |
| 10501 |
| 8233 |
| 6301 |
| 6113 |
| 5657 |
| 5101 |
| 4201 |
| 4129 |
| 3697 |
| 3251 |
| 2801 |
| 2521 |
| 1051 |
| 911 |
| 701 |
| 601 |
| 491 |
| 421 |
| 281 |
| 251 |
| 211 |
| 157 |
| 151 |
| 113 |
| 101 |
| 71 |
| 67 |
| 612 |
| 43 |
| 41 |
| 37 |
| 31 |
| 29 |
| 19 |
| 17 |
| 13 |
| 11 |
| 72 |
| 54 |
| 32 |
| 25 |
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.410713%
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 = 4661 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 ≡ 37 (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:
realprecision = 6001 significant digits (6000 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\13A01069.cin
Certificate file is: IO\13A01069.chg
Found values of n, F and G.
Number to be tested has 15545 digits.
Modulus has 4261 digits.
Modulus is 27.41071325% 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 = 10, u = 4. Right endpoint has 2763 digits.
Done! Time elapsed: 7474922ms.
Running CHG with h = 10, u = 4. Right endpoint has 2730 digits.
Done! Time elapsed: 4760235ms.
Running CHG with h = 10, u = 4. Right endpoint has 2689 digits.
Done! Time elapsed: 4884422ms.
Running CHG with h = 10, u = 4. Right endpoint has 2638 digits.
Done! Time elapsed: 5458234ms.
Running CHG with h = 10, u = 4. Right endpoint has 2577 digits.
Done! Time elapsed: 8000656ms.
Running CHG with h = 10, u = 4. Right endpoint has 2516 digits.
Done! Time elapsed: 10411156ms.
Running CHG with h = 10, u = 4. Right endpoint has 2455 digits.
Done! Time elapsed: 12093844ms.
Running CHG with h = 9, u = 3. Right endpoint has 2387 digits.
Done! Time elapsed: 1845875ms.
Running CHG with h = 9, u = 3. Right endpoint has 2365 digits.
Done! Time elapsed: 1973203ms.
Running CHG with h = 9, u = 3. Right endpoint has 2342 digits.
Done! Time elapsed: 2078875ms.
Running CHG with h = 9, u = 3. Right endpoint has 2317 digits.
Done! Time elapsed: 2705469ms.
Running CHG with h = 9, u = 3. Right endpoint has 2282 digits.
Done! Time elapsed: 1983297ms.
Running CHG with h = 9, u = 3. Right endpoint has 2237 digits.
Done! Time elapsed: 2337578ms.
Running CHG with h = 9, u = 3. Right endpoint has 2176 digits.
Done! Time elapsed: 2784672ms.
Running CHG with h = 9, u = 3. Right endpoint has 2094 digits.
Done! Time elapsed: 3558109ms.
Running CHG with h = 9, u = 3. Right endpoint has 1986 digits.
Done! Time elapsed: 3092391ms.
Running CHG with h = 7, u = 2. Right endpoint has 1842 digits.
Done! Time elapsed: 105266ms.
Running CHG with h = 7, u = 2. Right endpoint has 1818 digits.
Done! Time elapsed: 102968ms.
Running CHG with h = 7, u = 2. Right endpoint has 1795 digits.
Done! Time elapsed: 104719ms.
Running CHG with h = 7, u = 2. Right endpoint has 1762 digits.
Done! Time elapsed: 113922ms.
Running CHG with h = 7, u = 2. Right endpoint has 1713 digits.
Done! Time elapsed: 125516ms.
Running CHG with h = 7, u = 2. Right endpoint has 1639 digits.
Done! Time elapsed: 145421ms.
Running CHG with h = 7, u = 2. Right endpoint has 1529 digits.
Done! Time elapsed: 137469ms.
Running CHG with h = 7, u = 2. Right endpoint has 1363 digits.
Done! Time elapsed: 375688ms.
Running CHG with h = 5, u = 1. Right endpoint has 1115 digits.
Done! Time elapsed: 41781ms.
Running CHG with h = 5, u = 1. Right endpoint has 809 digits.
Done! Time elapsed: 41078ms.
Running CHG with h = 5, u = 1. Right endpoint has 309 digits.
Done! Time elapsed: 95156ms.
A certificate has been saved to the file: IO\13A01069.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\13A01069.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=1.426752014 E-535 at X, ratio=7.23082081 E-844 at Y, witness=5.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.4327136668 at X, ratio=3.634224559 E-500 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.088263870 E-307 at X, ratio=8.90851200 E-307 at Y, witness=2.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.2258593921 at X, ratio=1.332980736 E-497 at Y, witness=3.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.849937688 at X, ratio=5.421406676 E-332 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.0705897561 at X, ratio=1.492997997 E-221 at Y, witness=5.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.4182092735 at X, ratio=5.145546968 E-148 at Y, witness=2.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.05760628852 at X, ratio=7.61908798 E-99 at Y, witness=3.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.1050068983 at X, ratio=3.117993832 E-66 at Y, witness=3.
Pol[10, 1] with [h, u]=[6, 2] has ratio=0.4553723672 at X, ratio=8.21075333 E-48 at Y, witness=2.
Pol[11, 1] with [h, u]=[6, 2] has ratio=0.512038943 at X, ratio=1.345969822 E-47 at Y, witness=3.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.1640701153 at X, ratio=3.114301809 E-434 at Y, witness=7.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.2268593482 at X, ratio=6.418801836 E-326 at Y, witness=3.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.2102377167 at X, ratio=1.117385794 E-244 at Y, witness=3.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.2024156509 at X, ratio=1.178138936 E-183 at Y, witness=7.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.640601849 at X, ratio=7.32102061 E-138 at Y, witness=3.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.1335505454 at X, ratio=1.456026121 E-103 at Y, witness=2.
Pol[18, 1] with [h, u]=[9, 3] has ratio=0.004308710320 at X, ratio=6.31366269 E-78 at Y, witness=2.
Pol[19, 1] with [h, u]=[8, 3] has ratio=0.4142998223 at X, ratio=8.93540820 E-68 at Y, witness=2.
Pol[20, 1] with [h, u]=[8, 3] has ratio=0.4972938424 at X, ratio=1.018336875 E-67 at Y, witness=7.
Pol[21, 1] with [h, u]=[10, 4] has ratio=0.0821438760 at X, ratio=5.673434266 E-272 at Y, witness=5.
Pol[22, 1] with [h, u]=[10, 4] has ratio=0.1978265080 at X, ratio=1.935209560 E-245 at Y, witness=3.
Pol[23, 1] with [h, u]=[10, 4] has ratio=0.3021109177 at X, ratio=1.817781046 E-245 at Y, witness=2.
Pol[24, 1] with [h, u]=[10, 4] has ratio=0.0775913285 at X, ratio=1.862512316 E-245 at Y, witness=3.
Pol[25, 1] with [h, u]=[10, 4] has ratio=8.38299814 E-52 at X, ratio=2.352713125 E-204 at Y, witness=2.
Pol[26, 1] with [h, u]=[10, 4] has ratio=1.188215659 E-41 at X, ratio=1.332625092 E-163 at Y, witness=7.
Pol[27, 1] with [h, u]=[10, 4] has ratio=1.259912849 E-34 at X, ratio=4.385987356 E-131 at Y, witness=2.
Validated in 80 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.