Primality testing Phi(24691,7176) [N-1, Brillhart-Lehmer-Selfridge] Running N-1 test using base 17 Running N-1 test using base 29 Running N-1 test using base 37 Calling Brillhart-Lehmer-Selfridge with factored part 27.02% Phi(24691,7176) is PRP! (1823.7342s+0.0014s)

parisize = 8000000, primelimit = 500000 realprecision = 38011 significant digits (38000 digits displayed) Welcome to the CHG primality prover! ------------------------------------ Input file is: 7176_24691.in Certificate file is: 7176_24691.out Found values of n, F and G. Number to be tested has 95202 digits. Modulus has 25721 digits. Modulus is 27.017160175493079358% 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 18040 digits. Done! Time elapsed: 4270800ms. Running CHG with h = 12, u = 5. Right endpoint has 17913 digits. Done! Time elapsed: 3076560ms. Running CHG with h = 13, u = 5. Right endpoint has 17761 digits. Done! Time elapsed: 4273530ms. Running CHG with h = 12, u = 5. Right endpoint has 17558 digits. Done! Time elapsed: 10909510ms. Running CHG with h = 13, u = 5. Right endpoint has 17335 digits. Done! Time elapsed: 8614760ms. Running CHG with h = 12, u = 5. Right endpoint has 17051 digits. Done! Time elapsed: 13067180ms. Running CHG with h = 12, u = 5. Right endpoint has 16819 digits. Done! Time elapsed: 25482580ms. Running CHG with h = 12, u = 5. Right endpoint has 16581 digits. Done! Time elapsed: 8616260ms. Running CHG with h = 12, u = 5. Right endpoint has 16318 digits. Done! Time elapsed: 21450800ms. Running CHG with h = 12, u = 5. Right endpoint has 16030 digits. Done! Time elapsed: 6250510ms. Running CHG with h = 11, u = 4. Right endpoint has 15712 digits. Done! Time elapsed: 3241120ms. Running CHG with h = 11, u = 4. Right endpoint has 15534 digits. Done! Time elapsed: 3472190ms. Running CHG with h = 11, u = 4. Right endpoint has 15245 digits. Done! Time elapsed: 6200680ms. Running CHG with h = 11, u = 4. Right endpoint has 14972 digits. Done! Time elapsed: 7434670ms. Running CHG with h = 11, u = 4. Right endpoint has 14632 digits. Done! Time elapsed: 21452800ms. Running CHG with h = 11, u = 4. Right endpoint has 14205 digits. Done! Time elapsed: 27942120ms. Running CHG with h = 11, u = 4. Right endpoint has 13673 digits. Done! Time elapsed: 35284890ms. Running CHG with h = 9, u = 3. Right endpoint has 13007 digits. Done! Time elapsed: 517880ms. Running CHG with h = 9, u = 3. Right endpoint has 12746 digits. Done! Time elapsed: 933790ms. Running CHG with h = 9, u = 3. Right endpoint has 12376 digits. Done! Time elapsed: 1206830ms. Running CHG with h = 9, u = 3. Right endpoint has 11936 digits. Done! Time elapsed: 1244820ms. Running CHG with h = 9, u = 3. Right endpoint has 11290 digits. Done! Time elapsed: 1372640ms. Running CHG with h = 7, u = 2. Right endpoint has 10471 digits. Done! Time elapsed: 79250ms. Running CHG with h = 7, u = 2. Right endpoint has 10173 digits. Done! Time elapsed: 74900ms. Running CHG with h = 7, u = 2. Right endpoint has 9686 digits. Done! Time elapsed: 92740ms. Running CHG with h = 7, u = 2. Right endpoint has 9063 digits. Done! Time elapsed: 264920ms. Running CHG with h = 7, u = 2. Right endpoint has 7606 digits. Done! Time elapsed: 447600ms. Running CHG with h = 5, u = 1. Right endpoint has 5860 digits. Done! Time elapsed: 29150ms. Running CHG with h = 5, u = 1. Right endpoint has 2491 digits. Done! Time elapsed: 79630ms. A certificate has been saved to the file: 7176_24691.out Running David Broadhurst's verifier on the saved certificate... Testing a PRP called "7176_24691.in". Pol[1, 1] with [h, u]=[5, 1] has ratio=4.597595982772995048 E-3506 at X, ratio=3.801828163677429171 E-4218 at Y, witness=2. Pol[2, 1] with [h, u]=[4, 1] has ratio=0.8076550619027120551 at X, ratio=5.798602554199357743 E-3369 at Y, witness=2. Pol[3, 1] with [h, u]=[7, 2] has ratio=3.217169801397180630 E-13 at X, ratio=4.402750607303828036 E-3493 at Y, witness=11. Pol[4, 1] with [h, u]=[7, 2] has ratio=1.0000000000000000000 at X, ratio=2.0842962631052741796 E-2914 at Y, witness=2. Pol[5, 1] with [h, u]=[7, 2] has ratio=0.9490155606269143670 at X, ratio=1.9099332320044321008 E-1247 at Y, witness=2. Pol[6, 1] with [h, u]=[7, 2] has ratio=4.900545321013125885 E-488 at X, ratio=2.4015344443303641034 E-975 at Y, witness=2. Pol[7, 1] with [h, u]=[7, 2] has ratio=2.4015344443303641034 E-975 at X, ratio=9.264723012859239110 E-596 at Y, witness=2. Pol[8, 1] with [h, u]=[9, 3] has ratio=7.432704068703845780 E-955 at X, ratio=4.709306477033762143 E-2457 at Y, witness=2. Pol[9, 1] with [h, u]=[9, 3] has ratio=0.03485288983087276693 at X, ratio=1.4912796152199036330 E-1939 at Y, witness=2. Pol[10, 1] with [h, u]=[9, 3] has ratio=0.4798736611128196743 at X, ratio=8.312213958948559530 E-1320 at Y, witness=3. Pol[11, 1] with [h, u]=[9, 3] has ratio=1.0000000000000000000 at X, ratio=4.937589721111078568 E-1112 at Y, witness=5. Pol[12, 1] with [h, u]=[9, 3] has ratio=1.1168055224793939179 E-523 at X, ratio=1.0501017405996336266 E-782 at Y, witness=13. Pol[13, 1] with [h, u]=[11, 4] has ratio=0.5056377836401818539 at X, ratio=3.0570627788653768758 E-2664 at Y, witness=11. Pol[14, 1] with [h, u]=[11, 4] has ratio=0.18538850554550597892 at X, ratio=1.5021109555506145503 E-2131 at Y, witness=7. Pol[15, 1] with [h, u]=[11, 4] has ratio=0.3117737228454022066 at X, ratio=1.984546565661947591 E-1705 at Y, witness=19. Pol[16, 1] with [h, u]=[11, 4] has ratio=0.2826538580527206811 at X, ratio=1.9021090257026318712 E-1364 at Y, witness=2. Pol[17, 1] with [h, u]=[11, 4] has ratio=0.028147659024124845166 at X, ratio=9.268546666420088546 E-1092 at Y, witness=31. Pol[18, 1] with [h, u]=[11, 4] has ratio=0.00003188535853697225243 at X, ratio=8.662826235599488434 E-1158 at Y, witness=3. Pol[19, 1] with [h, u]=[11, 4] has ratio=1.4178215413457083242 E-535 at X, ratio=9.441995651801124555 E-713 at Y, witness=13. Pol[20, 1] with [h, u]=[12, 5] has ratio=0.05583901374348878402 at X, ratio=2.052870434304672199 E-1587 at Y, witness=7. Pol[21, 1] with [h, u]=[12, 5] has ratio=0.06680660130173295265 at X, ratio=3.894486481221340852 E-1443 at Y, witness=3. Pol[22, 1] with [h, u]=[12, 5] has ratio=0.05558051941472609334 at X, ratio=4.803965426101829123 E-1312 at Y, witness=2. Pol[23, 1] with [h, u]=[12, 5] has ratio=0.09817415991403734273 at X, ratio=9.187976121653162405 E-1193 at Y, witness=19. Pol[24, 1] with [h, u]=[12, 5] has ratio=1.0000000000000000000 at X, ratio=4.348184146383216996 E-1159 at Y, witness=2. Pol[25, 1] with [h, u]=[13, 5] has ratio=0.07649480316987622405 at X, ratio=1.1274710699531456660 E-1421 at Y, witness=41. Pol[26, 1] with [h, u]=[12, 5] has ratio=9.992553673211072144 E-56 at X, ratio=3.798012464019754052 E-1117 at Y, witness=13. Pol[27, 1] with [h, u]=[13, 5] has ratio=0.5170735828700391153 at X, ratio=2.5605104201289975006 E-1015 at Y, witness=7. Pol[28, 1] with [h, u]=[12, 5] has ratio=1.0367767222203293471 E-153 at X, ratio=7.334069858782291885 E-762 at Y, witness=5. Pol[29, 1] with [h, u]=[12, 5] has ratio=1.1856375901542335636 E-128 at X, ratio=4.807780291249966153 E-635 at Y, witness=3. Validated in 21 sec. Congratulations! n is prime! Goodbye!A copy of the CHG certificate

`7176_24691.out`

(26MB) is
included in:
`7176_24691.zip`

.
Phi(12345,7176)/31531760245313526865033921 1710039954019813790328995355095197 13992615389518459838028557122061 38843677594731274083592650421 31531760245313526865033921 7405823342795276789951861 383282379904735348808347 1315218009709159755371 634498606574107566217 175938577521188962981 105571878699423974581 67160260659356971 85527841186471 10217232786721 34437225191 5797681111 3555787831 4531321 414793 82301 74071 49003 24691 8231 7177 1051 619 373 241 223 191 181 71 61 31 23 13 11 5 3 2 2 2

`Phi(12345,7176)/31531760245313526865033921`

(25331 digits): `ecpp25331.zip`

Tom Wu Last modified: Thu Jun 1 10:00:00 PDT 2017