Primality Certificate for (460^4801-1)/459 | ||
| Andy Steward | 12,782 digits | 18 February 2010 |
|---|---|---|
| Originally by Alex Kruppa, Predrag Minovic & Larry Soule 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 26.607349% factorization of N-1:
| From | Factorisation |
|---|---|
| 460 | 2 · 2 · 5 · 23 |
| Φ2 | 461 |
| Φ3 | 3 · 70687 |
| Φ4 | 13 · 41 · 397 |
| Φ5 | 11 · 751 · 5431801 |
| Φ6 | 7 · 7 · 31 · 139 |
| Φ8 | 73 · 613350137 |
| Φ10 | 1231 · 36293611 |
| Φ12 | 3457 · 12951793 |
| Φ15 | 214021 · 9346760678499121 |
| Φ16 | 2609 · 54325457 · 14144421377 |
| Φ20 | 61 · 32864782769532431941 |
| Φ24 | 48017569 · 41750577234529 |
| Φ25 | 101 · 13176819445161053501 · p33 |
| Φ30 | 310081 · 6479337267115981 |
| Φ32 | 2657 · 35422360657729 · 42702790118708918884139617 |
| Φ40 | 281 · 7459201 · p34 |
| Φ48 | 97 · 241 · 2161 · p35 |
| Φ50 | 8782574759351 · 300774998624173301 · 68122887012557362259851 |
| Φ60 | 39212280169730341 · 102495609495982335735268861 |
| Φ64 | 193 · 785549057 · 1203173618645099009 · 9161094844650732673 · p37 |
| Φ75 | 107101 · p102 |
| Φ80 | 86739338371364187601 · 534972621793656697008401 · p42 |
| Φ96 | 35521 · 403252609 · 4954717391142554595943969 · p48 |
| Φ100 | 1455116007101 · 5790548533001 · p82 |
| Φ120 | 2521 · 616321 · p77 |
| Φ150 | 151 · 601 · 9001 · 33151 · 44851 · 246723688172251 · p75 |
| Φ160 | 602034721 · 17743993081062881 · 4998892185883246319015619443626840961 · p109 |
| Φ192 | 336961 · 212392356929095297 · 65539643064543161841799912533926891748712831458668353 · p95 |
| Φ200 | 2801 · 21401 · 844001 · 4633001 · 165353796980391601 · c176 |
| Φ240 | 1201 · 77521 · 789545761 · p154 |
| Φ300 | 6301 · 128504581079701 · 82014049263981301 · 435620510678688382427116639599601 · 23229793331224052317885417640349227312579061333212023967453957575591501 · p76 |
| Φ320 | 4329601 · 3179774119681 · c322 |
| Φ400 | 401 · 11569601 · 1758460032001 · 270478113948070801 · c387 |
| Φ480 | 4126794904568334853865761 · 30935471173888864042325951948355153601 · p279 |
| Φ600 | 19147752707318401 · 7805374908024879071464951996134601 · 125004466112479037405669130334300131723601 · c335 |
| Φ800 | 62401 · 3808001 · 431825276656001 · 13675374340572294401 · p807 |
| Φ960 | 6265087999962626881 · c663 |
| Φ1200 | 2210401 · 10582928849623201 · 148821246460799468460001 · 20544035613288130261210801 · c782 |
| Φ1600 | 1601 · 4801 · 208001 · 212801 · 43720960956394006824609601 · c1661 |
| Φ2400 | 24001 · 4757330220001 · 67523737642720037905596001 · c1662 |
| Φ4800 | 6334657670401 · c3396 |
We need the product F of all the prime factors from this partial factorization:
| 8617280 9333863514 1992152780 4634508013 0469515949 1425822969 9054406753 7582218596 1039207574 4453786002 2728232458 8463304287 0570900075 5042407933 5874999146 6840881449 6576141397 0000382024 0373340938 7715890767 2689283103 5062528628 4328164591 0004968027 9320664711 2143030014 0933118809 7997561581 1724809393 5984173549 6854453422 5880588118 3354729737 9146157308 4231426379 8457943297 1195128407 9024951955 7880740610 2308173582 5406276529 3347894413 3037437324 0180690169 3040554973 1214533206 6276271547 8581750808 6620375485 3184766235 6793582087 7963621138 3217779693 4578696729 7715650579 9435157688 6285642608 6055065478 3714499244 3152199238 2443950076 1906833518 9931712313 6256894828 9565063294 5224830409 5345671962 7180566517 8107863545 1275723171 1315159671 5754368040 9516277272 4362094777 3723630888 8763636667 4533477246 7484213708 3100064454 0577449565 1550059201 |
| 533252419 3630962115 4850442915 5769163875 1232899842 4951358668 7262500867 0214095485 9087482692 0298651637 4337001661 9752967074 2879734584 0225234704 5883005660 8984523049 2947449851 7858696592 4888828618 6503916548 1377119784 1845876389 0262037439 1203881404 5758840627 5501041793 6354856157 0342878241 |
| 3549 4539629107 6992394645 0794550299 5363667922 4229118210 9488033591 9777858316 7027329780 2780048626 3313975150 4301273564 7205567748 2356567451 1078869740 1997274721 |
| 488601233 5228900632 1609485061 6805542775 6335448728 8430232884 6224167537 3555933601 7133343027 9161269896 8748685441 |
| 30 2356800755 0388345050 8663345069 0461347921 5330281057 8482713235 0594593659 8626888404 7729199704 9321702901 |
| 55626 1026746078 3033587486 2751683755 1002590903 0701443146 1742152702 7553778989 3983628959 5348620801 |
| 38 4322617051 9102654401 5528697267 3534569967 5970912432 4441194294 3381715747 2018169901 |
| 1039610 8475319711 8014641849 2082355074 8016059496 2295922593 0462262041 0526608361 |
| 156047 3953718502 9133776986 2535063404 1905670885 1795298569 3032534673 6935961601 |
| 10806 6596493650 7341918566 2534689438 2564620354 4354574604 2703148781 3059035001 |
| 2 3229793331 2240523178 8541764034 9227312579 0613332120 2396745395 7575591501 |
| 655 3964306454 3161841799 9125339268 9174871283 1458668353 |
| 22759847 9365695521 6802236211 6619038808 2333574561 |
| 34 8099141267 1329317148 0504947237 1258964001 |
| 12 5004466112 4790374056 6913033430 0131723601 |
| 30935471 1738888640 4232595194 8355153601 |
| 9665944 8516487364 1492625706 2021024193 |
| 4998892 1858832463 1901561944 3626840961 |
| 79557 6164531154 1566475360 5034228033 |
| 7805 3749080248 7907146495 1996134601 |
| 1917 4616070971 6391146888 7241802921 |
| 435 6205106786 8838242711 6639599601 |
| 135 2149353280 2524997858 0708156401 |
| 1024956 0949598233 5735268861 |
| 675237 3764272003 7905596001 |
| 437209 6095639400 6824609601 |
| 427027 9011870891 8884139617 |
| 205440 3561328813 0261210801 |
| 49547 1739114255 4595943969 |
| 41267 9490456833 4853865761 |
| 5349 7262179365 6697008401 |
| 1488 2124646079 9468460001 |
| 681 2288701255 7362259851 |
| 8673933837 1364187601 |
| 3286478276 9532431941 |
| 1367537434 0572294401 |
| 1317681944 5161053501 |
| 916109484 4650732673 |
| 626508799 9962626881 |
| 120317361 8645099009 |
| 30077499 8624173301 |
| 27047811 3948070801 |
| 21239235 6929095297 |
| 16535379 6980391601 |
| 8201404 9263981301 |
| 3921228 0169730341 |
| 1914775 2707318401 |
| 1774399 3081062881 |
| 1058292 8849623201 |
| 934676 0678499121 |
| 647933 7267115981 |
| 43182 5276656001 |
| 24672 3688172251 |
| 12850 4581079701 |
| 4175 0577234529 |
| 3542 2360657729 |
| 878 2574759351 |
| 633 4657670401 |
| 579 0548533001 |
| 475 7330220001 |
| 317 9774119681 |
| 175 8460032001 |
| 145 5116007101 |
| 1 4144421377 |
| 789545761 |
| 785549057 |
| 613350137 |
| 602034721 |
| 403252609 |
| 54325457 |
| 48017569 |
| 36293611 |
| 12951793 |
| 11569601 |
| 7459201 |
| 5431801 |
| 4633001 |
| 4329601 |
| 3808001 |
| 2210401 |
| 844001 |
| 616321 |
| 336961 |
| 310081 |
| 214021 |
| 212801 |
| 208001 |
| 107101 |
| 77521 |
| 70687 |
| 62401 |
| 44851 |
| 35521 |
| 33151 |
| 24001 |
| 21401 |
| 9001 |
| 6301 |
| 4801 |
| 3457 |
| 2801 |
| 2657 |
| 2609 |
| 2521 |
| 2161 |
| 1601 |
| 1231 |
| 1201 |
| 751 |
| 601 |
| 461 |
| 401 |
| 397 |
| 281 |
| 241 |
| 193 |
| 151 |
| 139 |
| 101 |
| 97 |
| 73 |
| 61 |
| 41 |
| 31 |
| 23 |
| 13 |
| 11 |
| 72 |
| 5 |
| 3 |
| 22 |
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) = 26.607349%
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 = 2 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:
Testing a PRP called "Phi(4801,460)". LLL[1, 1] with [h, u]=[5, 1] has norm/bound=5.095032408 E-537 and witness=17. LLL[2, 1] with [h, u]=[5, 1] has norm/bound=0.3165698196 and witness=11. LLL[3, 1] with [h, u]=[4, 1] has norm/bound=5.272838352 E-102 and witness=7. LLL[4, 1] with [h, u]=[7, 2] has norm/bound=8.71731575 E-71 and witness=3. LLL[5, 1] with [h, u]=[7, 2] has norm/bound=0.2409504657 and witness=7. LLL[6, 1] with [h, u]=[7, 2] has norm/bound=0.3416087225 and witness=23. LLL[7, 1] with [h, u]=[7, 2] has norm/bound=0.2931353575 and witness=2. LLL[8, 1] with [h, u]=[7, 2] has norm/bound=0.3483163660 and witness=5. LLL[9, 1] with [h, u]=[9, 3] has norm/bound=1.836959485 E-35 and witness=37. LLL[10, 1] with [h, u]=[9, 3] has norm/bound=4.92076051 E-38 and witness=2. LLL[11, 1] with [h, u]=[9, 3] has norm/bound=0.000000702207046 and witness=43. LLL[12, 1] with [h, u]=[9, 3] has norm/bound=0.2129257549 and witness=7. LLL[13, 1] with [h, u]=[9, 3] has norm/bound=0.2426734828 and witness=3. LLL[14, 1] with [h, u]=[9, 3] has norm/bound=0.1794595898 and witness=7. LLL[15, 1] with [h, u]=[11, 4] has norm/bound=1.876281595 E-18 and witness=17. LLL[16, 1] with [h, u]=[11, 4] has norm/bound=4.414437476 E-22 and witness=41. LLL[17, 1] with [h, u]=[11, 4] has norm/bound=0.1563256826 and witness=41. LLL[18, 1] with [h, u]=[11, 4] has norm/bound=0.1778604679 and witness=2. LLL[19, 1] with [h, u]=[11, 4] has norm/bound=0.1766779201 and witness=37. LLL[20, 1] with [h, u]=[13, 5] has norm/bound=5.700324710 E-18 and witness=2. LLL[21, 1] with [h, u]=[13, 5] has norm/bound=0.1270356707 and witness=59. LLL[22, 1] with [h, u]=[13, 5] has norm/bound=0.1359766691 and witness=19. LLL[23, 1] with [h, u]=[13, 5] has norm/bound=0.1247848363 and witness=251. LLL[24, 1] with [h, u]=[13, 5] has norm/bound=0.1347671367 and witness=2. LLL[25, 1] with [h, u]=[13, 5] has norm/bound=0.1187477881 and witness=11. LLL[26, 1] with [h, u]=[13, 5] has norm/bound=0.1119903759 and witness=13. LLL[27, 1] with [h, u]=[13, 5] has norm/bound=0.1382732408 and witness=41. LLL[28, 1] with [h, u]=[15, 6] has norm/bound=0.1038682124 and witness=2. LLL[29, 1] with [h, u]=[15, 6] has norm/bound=0.0894885031 and witness=83. LLL[30, 1] with [h, u]=[15, 6] has norm/bound=0.1100845231 and witness=17. LLL[31, 1] with [h, u]=[15, 6] has norm/bound=0.1085770195 and witness=67. LLL[32, 1] with [h, u]=[15, 6] has norm/bound=0.0973802022 and witness=13. LLL[33, 1] with [h, u]=[15, 6] has norm/bound=0.0902767382 and witness=79. LLL[34, 1] with [h, u]=[15, 6] has norm/bound=0.1014441265 and witness=107. LLL[35, 1] with [h, u]=[16, 7] has norm/bound=0.06172331740 and witness=5. LLL[36, 1] with [h, u]=[16, 7] has norm/bound=0.006042214638 and witness=11. LLL[37, 1] with [h, u]=[16, 7] has norm/bound=1.000000000 and witness=79. LLL[38, 1] with [h, u]=[16, 7] has norm/bound=0.0896885671 and witness=107. LLL[39, 1] with [h, u]=[16, 7] has norm/bound=1.000000000 and witness=71. LLL[40, 1] with [h, u]=[16, 7] has norm/bound=1.000000000 and witness=19. LLL[41, 1] with [h, u]=[16, 7] has norm/bound=1.000000000 and witness=59. Validated in 313 sec.
The actual input file containing N and F and the output certificate are included in this file.