Primality Certificate for (5982^2381-1)/5981 | ||
| Andy Steward | 8,989 digits | 04 March 2007 |
|---|---|---|
| Originally by A.A.D.Steward 2007 | ||
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 29.782593% factorization of N-1:
| From | Factorisation |
|---|---|
| 5982 | 2 · 3 · 997 |
| Φ2 | 31 · 193 |
| Φ4 | 5 · 5 · 1431373 |
| Φ5 | 11 · 41 · 1130131 · 2512771 |
| Φ7 | 113 · 1305151 · 310750513171589 |
| Φ10 | 1280303818089151 |
| Φ14 | 883 · 1667 · 31125013940545463 |
| Φ17 | 103 · 6563 · 184043 · p50 |
| Φ20 | 5 · 1679501 · 48461461 · 4029252493641241 |
| Φ28 | 29 · 30955088186913409 · 2338981833416223506745018737 |
| Φ34 | 6257 · 1602799622630083 · 59173702310666307901 · 4529975111613815316521 |
| Φ35 | 71 · 25695251 · 37514401 · 5647263317960815867253973508691 · p44 |
| Φ68 | 182921 · 43806895537 · p105 |
| Φ70 | 281 · 15319571 · 4587430961 · 18915236904533217891928391 · p47 |
| Φ85 | 4931 · 645661 · 1492261 · 95576416891 · 2202139083735131 · 16659032236812621893469417901 · p172 |
| Φ119 | 19993 · 314399 · 122365397827 · c342 |
| Φ140 | 357328326461 · 12268561848061 · 126215948051286587201 · c137 |
| Φ170 | 1021 · 5441 · 70381 · 2920041110891 · 42555628909818106122330601 · p193 |
| Φ238 | 239 · 852476969 · c352 |
| Φ340 | c484 |
| Φ476 | 953 · 1429 · 1422461224047774269977060661 · c692 |
| Φ595 | 42841 · 117717536678701 · 6045937357180771 · p1416 |
| Φ1190 | 1459414811 · c1442 |
| Φ2380 | 2381 · 128521 · 4750890021641 · 43692517856401 · c2866 |
We need the product F of all the prime factors from this partial factorization:
| 668234 8740000786 9208445793 1183069283 9251700354 1811710084 1536962702 4391707645 1830308375 7006822227 7326814988 9111507592 8009508715 6693625143 8611216483 4545057306 6829134275 6120944326 7584906778 7750349324 7730244045 1719534962 4125284381 1822360544 3290484199 8219613821 3205337869 5349821872 1806619667 7766894159 3214840202 5691788629 0122359245 2053766102 2589152074 4676768582 6595942813 2615069958 5159368005 4865572781 6541457523 7202932106 5108765559 6169880601 9041077851 0271955545 8139688001 0969228678 6164801525 4874202101 0855236993 9059105991 9284661491 3680639937 7460607925 0772591071 6783058942 8255752301 0342860180 5215647118 5633943695 1744096132 4720870449 8552263612 0790324979 5746116486 4733325969 3346177836 5997838266 6470664671 2808663586 9179992138 3490400980 7422673298 2690641977 1078467100 1793725290 3205052987 4599037093 8715027595 1701055970 6750236059 4773849408 4089683579 4122161352 9751716049 0241727301 7990456308 6784888719 6612031650 5028890458 5400566960 0358541736 0388444522 0187890849 3155018694 0276876554 3176258148 8121128946 1939912208 8269340074 4945496365 4024711177 8986996993 0686233823 1891221956 6421828402 6706715237 2191949111 0653315019 7895483290 9014102979 8353672281 5356768172 4981443789 6968193403 6974154819 8144544702 1489783596 2982219257 2494332980 5213776763 0794281048 7478617628 6627763645 5932072055 3387677918 9643818756 5444434925 4868293611 8339503792 7132321087 2231962418 1909028871 4640916686 8982448620 4182195255 8849058701 7968504558 7203015930 9149208903 9816002341 |
| 107 5813204472 8182752587 4299062118 2599825288 7533439041 5743716497 5766542054 2412082811 7498973469 9607291943 8934736724 3987923575 9100202992 9051757430 6834764871 2506627511 6857713206 2948458884 3528109021 |
| 31 3666361266 8376331660 5183654000 8245804668 3550491515 1302653325 0768271289 2943908136 2160338330 5170603123 6541075225 1284779106 7296797998 8003028336 0744470880 6660442351 8176153181 |
| 90215 0557950513 4080772721 5348986803 0039557125 6833415349 1758964094 8765019945 0802100793 4436691061 4301389621 |
| 2161504841 1294257247 8487213009 6636979207 7516979613 |
| 1180462 3845396471 9976223037 0988752913 3553953051 |
| 1140 4964417202 4364755195 9416701858 6547455741 |
| 5 6472633179 6081586725 3973508691 |
| 166590322 3681262189 3469417901 |
| 23389818 3341622350 6745018737 |
| 14224612 2404777426 9977060661 |
| 425556 2890981810 6122330601 |
| 189152 3690453321 7891928391 |
| 45 2997511161 3815316521 |
| 1 2621594805 1286587201 |
| 5917370231 0666307901 |
| 3112501 3940545463 |
| 3095508 8186913409 |
| 604593 7357180771 |
| 402925 2493641241 |
| 220213 9083735131 |
| 160279 9622630083 |
| 128030 3818089151 |
| 31075 0513171589 |
| 11771 7536678701 |
| 4369 2517856401 |
| 1226 8561848061 |
| 475 0890021641 |
| 292 0041110891 |
| 35 7328326461 |
| 12 2365397827 |
| 9 5576416891 |
| 4 3806895537 |
| 4587430961 |
| 1459414811 |
| 852476969 |
| 48461461 |
| 37514401 |
| 25695251 |
| 15319571 |
| 2512771 |
| 1679501 |
| 1492261 |
| 1431373 |
| 1305151 |
| 1130131 |
| 645661 |
| 314399 |
| 184043 |
| 182921 |
| 128521 |
| 70381 |
| 42841 |
| 19993 |
| 6563 |
| 6257 |
| 5441 |
| 4931 |
| 2381 |
| 1667 |
| 1429 |
| 1021 |
| 997 |
| 953 |
| 883 |
| 281 |
| 239 |
| 193 |
| 113 |
| 103 |
| 71 |
| 41 |
| 31 |
| 29 |
| 11 |
| 53 |
| 3 |
| 2 |
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) = 29.782593%
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 = 6 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 ≡ 6 (mod 65) 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 = 2003 significant digits (2000 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\175E094D.cin
Certificate file is: IO\175E094D.chg
Found values of n, F and G.
Number to be tested has 8989 digits.
Modulus has 2678 digits.
Modulus is 29.78259309% 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 = 6, u = 2. Right endpoint has 958 digits.
Done! Time elapsed: 67203ms.
Running CHG with h = 5, u = 1. Right endpoint has 730 digits.
Done! Time elapsed: 4204ms.
Running CHG with h = 5, u = 1. Right endpoint has 567 digits.
Done! Time elapsed: 3359ms.
Running CHG with h = 5, u = 1. Right endpoint has 241 digits.
Done! Time elapsed: 37859ms.
A certificate has been saved to the file: IO\175E094D.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\175E094D.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=2.578845089 E-400 at X, ratio=8.45127402 E-640 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=4.95216504 E-327 at X, ratio=9.13195728 E-327 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=3.461083896 E-164 at X, ratio=4.078710795 E-164 at Y, witness=5.
Pol[4, 1] with [h, u]=[6, 2] has ratio=5.471964152 E-198 at X, ratio=1.881536356 E-457 at Y, witness=2.
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.