# Primality Proof of phi(15091,58729)

## OpenPFGW

```Primality testing Phi(15091,58729) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N-1 test using base 3
Calling Brillhart-Lehmer-Selfridge with factored part 27.11%
Phi(15091,58729) is PRP! (708.1480s+0.0008s)
```

## CHG

```   realprecision = 28012 significant digits (28000 digits displayed)

Welcome to the CHG primality prover!
------------------------------------

Input file is:  58729_15091.in
Certificate file is:  58729_15091.out
Found values of n, F and G.
Number to be tested has 71962 digits.
Modulus has 19510 digits.
Modulus is 27.110156929573823956% 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 13436 digits.
Done!  Time elapsed:  4225491ms.
Running CHG with h = 12, u = 5. Right endpoint has 13245 digits.
Done!  Time elapsed:  4930893ms.
Running CHG with h = 12, u = 5. Right endpoint has 13016 digits.
Done!  Time elapsed:  4527312ms.
Running CHG with h = 12, u = 5. Right endpoint has 12778 digits.
Done!  Time elapsed:  21197217ms.
Running CHG with h = 12, u = 5. Right endpoint has 12538 digits.
Done!  Time elapsed:  30390084ms.
Running CHG with h = 11, u = 4. Right endpoint has 12273 digits.
Done!  Time elapsed:  557686ms.
Running CHG with h = 11, u = 4. Right endpoint has 12184 digits.
Done!  Time elapsed:  677815ms.
Running CHG with h = 11, u = 4. Right endpoint has 12076 digits.
Done!  Time elapsed:  582520ms.
Running CHG with h = 11, u = 4. Right endpoint has 11941 digits.
Done!  Time elapsed:  1576079ms.
Running CHG with h = 11, u = 4. Right endpoint has 11772 digits.
Done!  Time elapsed:  660918ms.
Running CHG with h = 11, u = 4. Right endpoint has 11555 digits.
Done!  Time elapsed:  2282888ms.
Running CHG with h = 11, u = 4. Right endpoint has 11290 digits.
Done!  Time elapsed:  4610192ms.
Running CHG with h = 11, u = 4. Right endpoint has 10959 digits.
Done!  Time elapsed:  25951851ms.
Running CHG with h = 11, u = 4. Right endpoint has 10544 digits.
Done!  Time elapsed:  6946961ms.
Running CHG with h = 9, u = 3. Right endpoint has 10027 digits.
Done!  Time elapsed:  1021963ms.
Running CHG with h = 9, u = 3. Right endpoint has 9851 digits.
Done!  Time elapsed:  1185731ms.
Running CHG with h = 9, u = 3. Right endpoint has 9618 digits.
Done!  Time elapsed:  2959500ms.
Running CHG with h = 9, u = 3. Right endpoint has 9306 digits.
Done!  Time elapsed:  1529306ms.
Running CHG with h = 9, u = 3. Right endpoint has 8890 digits.
Done!  Time elapsed:  2471625ms.
Running CHG with h = 9, u = 3. Right endpoint has 8336 digits.
Done!  Time elapsed:  3313780ms.
Running CHG with h = 7, u = 2. Right endpoint has 7598 digits.
Done!  Time elapsed:  109873ms.
Running CHG with h = 7, u = 2. Right endpoint has 7245 digits.
Done!  Time elapsed:  164172ms.
Running CHG with h = 7, u = 2. Right endpoint has 6750 digits.
Done!  Time elapsed:  212677ms.
Running CHG with h = 7, u = 2. Right endpoint has 5684 digits.
Done!  Time elapsed:  418734ms.
Running CHG with h = 5, u = 1. Right endpoint has 4333 digits.
Done!  Time elapsed:  29826ms.
Running CHG with h = 5, u = 1. Right endpoint has 1813 digits.
Done!  Time elapsed:  46447ms.
A certificate has been saved to the file:  58729_15091.out

Running David Broadhurst's verifier on the saved certificate...

Testing a PRP called "58729_15091.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=1.0134288945207137034 E-1492 at X, ratio=1.9336739991304621642 E-3304 at Y, witness=2.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.9905223921630433171 at X, ratio=2.628753592120217809 E-2520 at Y, witness=17.
Pol[3, 1] with [h, u]=[7, 2] has ratio=4.918323052208643000 E-14 at X, ratio=9.546243236195060029 E-2704 at Y, witness=11.
Pol[4, 1] with [h, u]=[7, 2] has ratio=1.0000000000000000000 at X, ratio=1.0555632480974689792 E-2131 at Y, witness=2.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.22996920903704090786 at X, ratio=2.167302784231128993 E-991 at Y, witness=7.
Pol[6, 1] with [h, u]=[7, 2] has ratio=1.9425517191319906974 E-353 at X, ratio=3.773507181502652473 E-706 at Y, witness=2.
Pol[7, 1] with [h, u]=[9, 3] has ratio=0.3132381427483303126 at X, ratio=8.968748868560502876 E-2217 at Y, witness=5.
Pol[8, 1] with [h, u]=[9, 3] has ratio=0.2628395406272610382 at X, ratio=9.496915232904930856 E-1663 at Y, witness=23.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.14443748489151425192 at X, ratio=2.6984045950437693532 E-1247 at Y, witness=5.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.024056063875887052616 at X, ratio=1.1220907851245453900 E-935 at Y, witness=2.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.3052823612612857144 at X, ratio=7.384724839947875764 E-702 at Y, witness=5.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.19029304720902164672 at X, ratio=1.3459586941579866787 E-526 at Y, witness=2.
Pol[13, 1] with [h, u]=[11, 4] has ratio=0.7988632455445099680 at X, ratio=2.705106191577981777 E-2072 at Y, witness=3.
Pol[14, 1] with [h, u]=[11, 4] has ratio=0.5879683733948107924 at X, ratio=5.729182302094451322 E-1658 at Y, witness=7.
Pol[15, 1] with [h, u]=[11, 4] has ratio=0.20157952745575956748 at X, ratio=1.5662164538413438264 E-1326 at Y, witness=3.
Pol[16, 1] with [h, u]=[11, 4] has ratio=0.03799087820589632892 at X, ratio=2.4037707347372343734 E-1061 at Y, witness=5.
Pol[17, 1] with [h, u]=[11, 4] has ratio=6.805870978374302317 E-294 at X, ratio=5.834854748410778662 E-866 at Y, witness=7.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.3855146123056651324 at X, ratio=3.531470981941500048 E-676 at Y, witness=3.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.09645573635074524173 at X, ratio=3.946236461991331100 E-541 at Y, witness=11.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.13115773044762876517 at X, ratio=4.269430608888790155 E-433 at Y, witness=2.
Pol[21, 1] with [h, u]=[11, 4] has ratio=0.021979810579158670382 at X, ratio=1.5671279474018330450 E-358 at Y, witness=5.
Pol[22, 1] with [h, u]=[12, 5] has ratio=0.11311345155551398115 at X, ratio=4.612269058078487522 E-1324 at Y, witness=2.
Pol[23, 1] with [h, u]=[12, 5] has ratio=0.15487399087798378634 at X, ratio=1.0309235804377548964 E-1203 at Y, witness=7.
Pol[24, 1] with [h, u]=[12, 5] has ratio=0.04822323993144247014 at X, ratio=7.638143747645795296 E-1189 at Y, witness=5.
Pol[25, 1] with [h, u]=[12, 5] has ratio=2.918519001546996623 E-230 at X, ratio=2.4379408198280995110 E-1145 at Y, witness=7.
Pol[26, 1] with [h, u]=[12, 5] has ratio=2.5170225595087714496 E-192 at X, ratio=1.4571031045286548121 E-954 at Y, witness=19.

Validated in 15 sec.

Congratulations! n is prime!
Goodbye!
```
A copy of the CHG certificate `58729_15091.out` (15MB) is included in: `58729_15091.zip`.

## Helper File

Based on factorization of N-1 and N+1:
```Phi(7545,58729)/(15091*181081)
141518577057991884353412556550774050081
54944547510003975367411457
38969436819363236265199
31309680237291504724127
854537546718984134581
759623187152078440421
39068769655181209291
1174992195772806667
93812539342031
68994834745423
5976689212201
145207292471
417769669
299561651
116657773
61718101
30089461
21803081
606091
241441
214399
181081
138829
125221
28111
16087
15091
12073
7603
3019
839
601
281
211
67
61
37
31
19
11
7
5
5
3
2
```

## Prime Factor Certification

Signed Primo certificate for `Phi(7545,58729)/(15091*181081)` (19143 digits): `ecpp19143.zip`

Tom Wu
Last modified: Sat Feb 4 10:00:00 PDT 2017