# Primality Proof of phi(9151,13117)

## OpenPFGW

```Primality testing (13117^9151-1)/13116 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 29.63%
(13117^9151-1)/13116 is PRP! (115.3047s+0.0012s)
```

## CHG

```   realprecision = 10018 significant digits (10000 digits displayed)

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

Input file is:  13117_9151.in
Certificate file is:  13117_9151.out
Found values of n, F and G.
Number to be tested has 37679 digits.
Modulus has 11166 digits.
Modulus is 29.634095778965868862% 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 4182 digits.
Done!  Time elapsed:  43520ms.
Running CHG with h = 5, u = 1. Right endpoint has 3342 digits.
Done!  Time elapsed:  20330ms.
Running CHG with h = 5, u = 1. Right endpoint has 2961 digits.
Done!  Time elapsed:  25840ms.
Running CHG with h = 5, u = 1. Right endpoint has 2105 digits.
Done!  Time elapsed:  32240ms.
Running CHG with h = 5, u = 1. Right endpoint has 488 digits.
Done!  Time elapsed:  27370ms.
A certificate has been saved to the file:  13117_9151.out

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

Testing a PRP called "13117_9151.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=5.358859357070458499 E-2656 at X, ratio=3.866583952329853871 E-3143 at Y, witness=13.
Pol[2, 1] with [h, u]=[4, 1] has ratio=2.2471341023966250040 E-1618 at X, ratio=4.370762972034567292 E-1618 at Y, witness=11.
Pol[3, 1] with [h, u]=[5, 1] has ratio=0.07904323746801880062 at X, ratio=1.4455000008714257753 E-856 at Y, witness=11.
Pol[4, 1] with [h, u]=[4, 1] has ratio=2.2059668080930449452 E-381 at X, ratio=2.2249896383119031638 E-381 at Y, witness=11.
Pol[5, 1] with [h, u]=[6, 2] has ratio=1.0875863470447360695 E-841 at X, ratio=7.042634925429985100 E-1682 at Y, witness=2.

Validated in 1 sec.

Congratulations! n is prime!
Goodbye!
```
A copy of the CHG certificate `13117_9151.out` (5MB) is included in: `13117_9151.zip`.

## Helper File

Based on factorization of N-1 and N+1:
```Phi(4575,13117)/(18301*202425451*3298012754602867624201)
Phi(61,13117)/(536923*875930477)
66588391935055415770064522768125739150761852824869155218090020812163901511697322634031725438859212271396551
8077458632589958405750524879682688205550156155936627395015194169768142042253500961801
225096632082012785072419904838087410245149515275911799771955416304311652379144601
1323829692008386144567258119627481506062791
945809283662098476256081169854254168277
693529892556880192642520943613145169601
480039449608721898362811177895914001
4177418263561126795188298808706601
18630061069807433557489051
1824629218052394624529801
46140414426134931540151
35166018204130007159701
3902471271055368093151
3298012754602867624201
2406854939170653028201
243827303962766334691
180481060021764970051
79173504567283368161
35497733915382568831
6544463180390908601
5198955439221151
122122081261151
49994704326631
28126208866351
2795826653101
1337984167951
1252103443561
334546928701
41294117351
40921211941
27121518661
25602891511
10511644441
2527126951
975051991
875930477
202425451
147659651
88532351
50453101
8439961
6021601
2775991
1619551
1294621
1085801
840601
536923
494101
122611
81421
68443
65881
49411
25321
18301
13537
9151
6833
4027
3391
2851
2551
2113
1831
1009
937
733
367
281
223
151
31
19
13
11
7
3
2
```

## Prime Factor Certification

A signed Primo certificate for `Phi(4575,13117)/(18301*202425451*3298012754602867624201)` (9849 digits) is included in: `13117_9151.zip`.

Tom Wu