Primality Certificate for (11191^2377-1)/11190 | ||
| Andy Steward | 9,621 digits | 11 February 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 27.990966% factorization of N-1:
| From | Factorisation |
|---|---|
| 11191 | 19 · 19 · 31 |
| Φ2 | 2 · 2 · 2 · 1399 |
| Φ3 | 3 · 41749891 |
| Φ4 | 2 · 62619241 |
| Φ6 | 7 · 7 · 97 · 26347 |
| Φ8 | 2 · 73 · 107429295364297 |
| Φ9 | 3 · 654775045961612171293171 |
| Φ11 | 23 · 17117 · p35 |
| Φ12 | 13 · 23593 · 51138626509 |
| Φ18 | 307 · 8353 · 251773453 · 3042443917 |
| Φ22 | p41 |
| Φ24 | 54443497 · 4518613057839340023019513 |
| Φ27 | 3 · 109 · 6481 · 6616189 · 256180761349129 · 715958559479798876503 · 2947189415036485118631013 |
| Φ33 | 6007 · 9426807791851652533 · p59 |
| Φ36 | 37 · 1288984347008071735537 · 80905376146083643663462189 |
| Φ44 | 116689 · 584881434242557 · p62 |
| Φ54 | 789350511619 · 27312051213883 · 2419207146307253929303 · 145325843935678243360827181 |
| Φ66 | 67 · 18078589 · p72 |
| Φ72 | 577 · 2017 · 2647627612729723289856316966993 · p61 |
| Φ88 | 89 · 381965722172505338020956793 · p134 |
| Φ99 | 199 · 397 · 2171399361290213690593 · c217 |
| Φ108 | 18117973 · 2916786889 · 5318242445557 · 72691843260563324029 · 135905414379489256609 · p77 |
| Φ132 | 12431911244804491010058114164032969 · p128 |
| Φ198 | 27127 · 2417983996168675846297 · c218 |
| Φ216 | 2377 · 1593688177 · p279 |
| Φ264 | 167113 · c319 |
| Φ297 | 2971 · 783487 · 13495598029 · 725193321499952119 · c692 |
| Φ396 | 36037 · 217209812293 · 5211110386721053 · c455 |
| Φ594 | 490899645795585968422867 · c706 |
| Φ792 | 3169 · 2305435177 · p959 |
| Φ1188 | c1458 |
| Φ2376 | 201961 · 63491473 · 160791083641 · 318921536737 · 8087184380881 · c2867 |
We need the product F of all the prime factors from this partial factorization:
| 732588037 7982467802 5974458374 1196171602 3760164989 0032868148 3613307444 3760752822 7864633439 8825928944 2907541348 0785917139 4559109171 2948506117 4895376364 1458792922 9311229426 5842917223 3889500614 1547438636 8042856406 8829745187 8778346809 4539390429 4816079740 2148257093 4886602508 4121861106 2614312545 3597736006 5937579431 7785117426 7012666433 2354948382 1036283110 1325011548 0429967563 8369077426 3991116602 6821190270 0815315299 0268569603 8408371938 1129362586 4868490695 1564948420 9055510659 1627095238 0431997300 3865707640 0261604349 0513747357 8609829127 7192111482 6868674604 6262513218 9703107633 8867895899 2473157307 7561793023 4020161079 1052567510 1270777454 6841067267 7733082724 0483105510 6495532103 8733140119 5439623554 0141050407 5348982962 8430628811 8358286515 6974079450 3865495507 0390416423 2219793406 3808938521 6009190556 4084070225 8226291043 8068532581 3967873671 5170222230 9709012500 6074499825 5317400424 0438547307 3271990432 3567422713 0495060579 4023260741 1942080897 2582560860 4969437983 4498611577 |
| 871220248 9669240152 1081310680 9704596628 3142149127 5023176266 9898364666 1845345402 5576702345 3854209297 4845547685 0645929140 1789752906 0273771847 0659071737 1102140319 3500221255 6098027878 9582139011 3291389902 8277287741 3986795004 3146162694 1146808255 4178617621 2738501911 2619414035 1407074729 |
| 2650 5831459793 5902335439 4040956969 1796949693 2327753773 6371528335 0474573699 1130284357 1105246885 0823919973 0649392594 4042919341 2872784913 |
| 72479957 8580554515 7457190139 5342935682 4501982209 8414689922 5858299050 1001625367 3831923671 5208944387 0337101422 6072641103 1334066329 |
| 2069070 8725137967 9618280051 8617770868 7207181437 6803246666 7046871401 6848059109 |
| 78 3749697560 6540726430 4382031916 8999129011 3800402885 9642909226 4372574327 |
| 13 9084955985 5097078402 0122428383 5683160615 8363164946 2166623637 |
| 4 8318660323 4755765280 1470775443 0183885040 9441733018 8521689713 |
| 167616520 6930652991 9018690453 0767553287 3137943200 2995328571 |
| 3 0807052710 8508180914 3536999861 2120288451 |
| 78265 8452606021 4947573940 2002368971 |
| 12431 9112448044 9101005811 4164032969 |
| 2 6476276127 2972328985 6316966993 |
| 3819657 2217250533 8020956793 |
| 1453258 4393567824 3360827181 |
| 809053 7614608364 3663462189 |
| 45186 1305783934 0023019513 |
| 29471 8941503648 5118631013 |
| 6547 7504596161 2171293171 |
| 4908 9964579558 5968422867 |
| 24 1920714630 7253929303 |
| 24 1798399616 8675846297 |
| 21 7139936129 0213690593 |
| 12 8898434700 8071735537 |
| 7 1595855947 9798876503 |
| 1 3590541437 9489256609 |
| 7269184326 0563324029 |
| 942680779 1851652533 |
| 72519332 1499952119 |
| 521111 0386721053 |
| 58488 1434242557 |
| 25618 0761349129 |
| 10742 9295364297 |
| 2731 2051213883 |
| 808 7184380881 |
| 531 8242445557 |
| 78 9350511619 |
| 31 8921536737 |
| 21 7209812293 |
| 16 0791083641 |
| 5 1138626509 |
| 1 3495598029 |
| 3042443917 |
| 2916786889 |
| 2305435177 |
| 1593688177 |
| 251773453 |
| 63491473 |
| 62619241 |
| 54443497 |
| 41749891 |
| 18117973 |
| 18078589 |
| 6616189 |
| 783487 |
| 201961 |
| 167113 |
| 116689 |
| 36037 |
| 27127 |
| 26347 |
| 23593 |
| 17117 |
| 8353 |
| 6481 |
| 6007 |
| 3169 |
| 2971 |
| 2377 |
| 2017 |
| 1399 |
| 577 |
| 397 |
| 307 |
| 199 |
| 109 |
| 97 |
| 89 |
| 73 |
| 67 |
| 37 |
| 31 |
| 23 |
| 192 |
| 13 |
| 72 |
| 33 |
| 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.990966%
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 = 85 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 ≡ 5 (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 = 3506 significant digits (3500 digits displayed)
Welcome to the CHG primality prover!
------------------------------------
Input file is: IO\2BB70949.cin
Certificate file is: IO\2BB70949.chg
Found values of n, F and G.
Number to be tested has 9621 digits.
Modulus has 2693 digits.
Modulus is 27.99096555% 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 1543 digits.
Done! Time elapsed: 382375ms.
Running CHG with h = 8, u = 3. Right endpoint has 1508 digits.
Done! Time elapsed: 337188ms.
Running CHG with h = 8, u = 3. Right endpoint has 1461 digits.
Done! Time elapsed: 560828ms.
Running CHG with h = 8, u = 3. Right endpoint has 1399 digits.
Done! Time elapsed: 425234ms.
Running CHG with h = 8, u = 3. Right endpoint has 1327 digits.
Done! Time elapsed: 609735ms.
Running CHG with h = 8, u = 3. Right endpoint has 1254 digits.
Done! Time elapsed: 1167328ms.
Running CHG with h = 7, u = 2. Right endpoint has 1176 digits.
Done! Time elapsed: 40734ms.
Running CHG with h = 7, u = 2. Right endpoint has 1110 digits.
Done! Time elapsed: 31703ms.
Running CHG with h = 7, u = 2. Right endpoint has 1034 digits.
Done! Time elapsed: 40453ms.
Running CHG with h = 6, u = 2. Right endpoint has 919 digits.
Done! Time elapsed: 17703ms.
Running CHG with h = 6, u = 2. Right endpoint has 843 digits.
Done! Time elapsed: 17079ms.
Running CHG with h = 6, u = 2. Right endpoint has 766 digits.
Done! Time elapsed: 76593ms.
Running CHG with h = 5, u = 1. Right endpoint has 670 digits.
Done! Time elapsed: 6219ms.
Running CHG with h = 5, u = 1. Right endpoint has 442 digits.
Done! Time elapsed: 4844ms.
Running CHG with h = 5, u = 1. Right endpoint has 58 digits.
Done! Time elapsed: 26515ms.
A certificate has been saved to the file: IO\2BB70949.chg
Running David Broadhurst's verifier on the saved certificate...
Testing a PRP called "IO\2BB70949.cin".
Pol[1, 1] with [h, u]=[5, 1] has ratio=1.635646752 E-654 at X, ratio=1.236561146 E-711 at Y, witness=7.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.2750596240 at X, ratio=2.396228230 E-384 at Y, witness=11.
Pol[3, 1] with [h, u]=[4, 1] has ratio=2.157207116 E-229 at X, ratio=1.046000847 E-228 at Y, witness=5.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.549274557 at X, ratio=3.068739907 E-193 at Y, witness=7.
Pol[5, 1] with [h, u]=[6, 2] has ratio=0.731860202 at X, ratio=1.164715197 E-154 at Y, witness=11.
Pol[6, 1] with [h, u]=[6, 2] has ratio=0.4614296392 at X, ratio=1.893349150 E-152 at Y, witness=13.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.607516728 at X, ratio=4.494258254 E-230 at Y, witness=2.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.0677999050 at X, ratio=1.919047721 E-153 at Y, witness=3.
Pol[9, 1] with [h, u]=[6, 2] has ratio=1.247583768 E-67 at X, ratio=2.174556550 E-132 at Y, witness=7.
Pol[10, 1] with [h, u]=[8, 3] has ratio=0.0758823102 at X, ratio=1.458040103 E-236 at Y, witness=3.
Pol[11, 1] with [h, u]=[8, 3] has ratio=0.3132385279 at X, ratio=1.756894086 E-217 at Y, witness=5.
Pol[12, 1] with [h, u]=[8, 3] has ratio=0.3059698273 at X, ratio=1.170890965 E-217 at Y, witness=2.
Pol[13, 1] with [h, u]=[8, 3] has ratio=1.303542962 E-63 at X, ratio=4.77551131 E-187 at Y, witness=17.
Pol[14, 1] with [h, u]=[8, 3] has ratio=1.001484573 E-47 at X, ratio=1.712461926 E-140 at Y, witness=13.
Pol[15, 1] with [h, u]=[8, 3] has ratio=4.046382023 E-36 at X, ratio=1.443339295 E-105 at Y, witness=41.
Validated in 10 sec.
Congratulations! n is prime!
The actual input file containing N and F and the output certificate are included in this file.