# Primality Proof of phi(24691,7176)

## OpenPFGW

```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)
```

## CHG

```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`.

## Helper File

Based on factorization of N-1 and N+1:
```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
```

## Prime Factor Certification

Signed Primo certificate for `Phi(12345,7176)/31531760245313526865033921` (25331 digits): `ecpp25331.zip`

Tom Wu