# Primality Proof of phi(16111,40734)

## OpenPFGW

```Primality testing (40734^16111-1)/40733 [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.46%
(40734^16111-1)/40733 is PRP! (1323.9008s+0.1005s)
```

## CHG

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

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

Input file is:  40734_16111.in
Certificate file is:  40734_16111.out
Found values of n, F and G.
Number to be tested has 74267 digits.
Modulus has 20393 digits.
Modulus is 27.458193287113304548% 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 = 10, u = 4. Right endpoint has 13091 digits.
Done!  Time elapsed:  592100ms.
Running CHG with h = 10, u = 4. Right endpoint has 12880 digits.
Done!  Time elapsed:  673780ms.
Running CHG with h = 10, u = 4. Right endpoint has 12618 digits.
Done!  Time elapsed:  659020ms.
Running CHG with h = 10, u = 4. Right endpoint has 12289 digits.
Done!  Time elapsed:  771860ms.
Running CHG with h = 10, u = 4. Right endpoint has 11960 digits.
Done!  Time elapsed:  1865550ms.
Running CHG with h = 10, u = 4. Right endpoint has 11630 digits.
Done!  Time elapsed:  5255770ms.
Running CHG with h = 9, u = 3. Right endpoint has 11258 digits.
Done!  Time elapsed:  634360ms.
Running CHG with h = 9, u = 3. Right endpoint has 11102 digits.
Done!  Time elapsed:  853630ms.
Running CHG with h = 9, u = 3. Right endpoint has 10914 digits.
Done!  Time elapsed:  281610ms.
Running CHG with h = 9, u = 3. Right endpoint has 10663 digits.
Done!  Time elapsed:  405790ms.
Running CHG with h = 9, u = 3. Right endpoint has 10329 digits.
Done!  Time elapsed:  1651230ms.
Running CHG with h = 9, u = 3. Right endpoint has 9883 digits.
Done!  Time elapsed:  1614750ms.
Running CHG with h = 8, u = 3. Right endpoint has 9289 digits.
Done!  Time elapsed:  720360ms.
Running CHG with h = 8, u = 3. Right endpoint has 9010 digits.
Done!  Time elapsed:  1177930ms.
Running CHG with h = 7, u = 2. Right endpoint has 8686 digits.
Done!  Time elapsed:  85540ms.
Running CHG with h = 7, u = 2. Right endpoint has 8535 digits.
Done!  Time elapsed:  104910ms.
Running CHG with h = 7, u = 2. Right endpoint has 8324 digits.
Done!  Time elapsed:  170890ms.
Running CHG with h = 7, u = 2. Right endpoint has 8008 digits.
Done!  Time elapsed:  358530ms.
Running CHG with h = 7, u = 2. Right endpoint has 7534 digits.
Done!  Time elapsed:  806910ms.
Running CHG with h = 7, u = 2. Right endpoint has 6823 digits.
Done!  Time elapsed:  947480ms.
Running CHG with h = 6, u = 2. Right endpoint has 5608 digits.
Done!  Time elapsed:  154440ms.
Running CHG with h = 5, u = 1. Right endpoint has 4971 digits.
Done!  Time elapsed:  31840ms.
Running CHG with h = 5, u = 1. Right endpoint has 3047 digits.
Done!  Time elapsed:  39830ms.
Running CHG with h = 5, u = 1. Right endpoint has 529 digits.
Done!  Time elapsed:  223850ms.
A certificate has been saved to the file:  40734_16111.out

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

Testing a PRP called "40734_16111.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.0746195682849381998 E-4482 at X, ratio=1.4484183768135900227 E-5010 at Y, witness=5.
Pol[2, 1] with [h, u]=[4, 1] has ratio=4.591687671079424225 E-1161 at X, ratio=1.2755188475695062339 E-2518 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=5.506741126339485269 E-1823 at X, ratio=1.0579520703598122952 E-1924 at Y, witness=13.
Pol[4, 1] with [h, u]=[5, 2] has ratio=2.314516811416860462 E-1911 at X, ratio=1.7497401595520280675 E-1274 at Y, witness=2.
Pol[5, 1] with [h, u]=[7, 2] has ratio=1.0000000000000000000 at X, ratio=1.4319336959782028663 E-2430 at Y, witness=3.
Pol[6, 1] with [h, u]=[7, 2] has ratio=0.5652943240065485511 at X, ratio=8.364105476713622745 E-1423 at Y, witness=13.
Pol[7, 1] with [h, u]=[7, 2] has ratio=0.3353808250481924084 at X, ratio=7.142421923927273892 E-949 at Y, witness=5.
Pol[8, 1] with [h, u]=[7, 2] has ratio=0.4371925050335361950 at X, ratio=9.072674004701774330 E-633 at Y, witness=5.
Pol[9, 1] with [h, u]=[7, 2] has ratio=0.0014807794216913852564 at X, ratio=4.407852517592814796 E-422 at Y, witness=3.
Pol[10, 1] with [h, u]=[6, 2] has ratio=0.9347633297377322032 at X, ratio=1.3785961457417234957 E-303 at Y, witness=2.
Pol[11, 1] with [h, u]=[8, 3] has ratio=0.4201233404700105697 at X, ratio=1.8654613905301410282 E-972 at Y, witness=23.
Pol[12, 1] with [h, u]=[8, 3] has ratio=0.22795242036132283456 at X, ratio=3.3354574628906667948 E-838 at Y, witness=2.
Pol[13, 1] with [h, u]=[9, 3] has ratio=0.11098635948967987873 at X, ratio=4.677490592923544206 E-1783 at Y, witness=19.
Pol[14, 1] with [h, u]=[9, 3] has ratio=0.7787344651397194336 at X, ratio=1.6220872762141191679 E-1337 at Y, witness=5.
Pol[15, 1] with [h, u]=[9, 3] has ratio=0.2591273689466199122 at X, ratio=2.457135208626778580 E-1003 at Y, witness=2.
Pol[16, 1] with [h, u]=[9, 3] has ratio=0.4017637310723480101 at X, ratio=1.0296365623857662819 E-752 at Y, witness=7.
Pol[17, 1] with [h, u]=[9, 3] has ratio=0.22923288146357907292 at X, ratio=9.805773527177072068 E-565 at Y, witness=5.
Pol[18, 1] with [h, u]=[9, 3] has ratio=0.3032833456851888286 at X, ratio=3.421814039303733669 E-468 at Y, witness=19.
Pol[19, 1] with [h, u]=[10, 4] has ratio=0.2872655742473887473 at X, ratio=3.102710796668019221 E-1488 at Y, witness=2.
Pol[20, 1] with [h, u]=[10, 4] has ratio=0.2688928533831372457 at X, ratio=6.627217051203346624 E-1323 at Y, witness=5.
Pol[21, 1] with [h, u]=[10, 4] has ratio=0.07067740238314248717 at X, ratio=1.1143207571236829754 E-1316 at Y, witness=3.
Pol[22, 1] with [h, u]=[10, 4] has ratio=3.502582289983299087 E-19 at X, ratio=1.1323071900759473903 E-1314 at Y, witness=17.
Pol[23, 1] with [h, u]=[10, 4] has ratio=9.724979830186461757 E-264 at X, ratio=7.217920593318674778 E-1052 at Y, witness=7.
Pol[24, 1] with [h, u]=[10, 4] has ratio=9.772157898137144142 E-212 at X, ratio=1.1345480125835036934 E-841 at Y, witness=5.

Validated in 8 sec.

Congratulations! n is prime!
Goodbye!
```
A copy of the CHG certificate `40734_16111.out` (11MB) is included in: `40734_16111.zip`.

## Helper File

Based on factorization of N-1 and N+1:
```Phi(8055,40734)/(612181*117892981*182332981*1923646771*174457892355841*21784054190313871)
2811033774607246336365480082165575915224299264411
1207516010376979080728377199319057419775421
49330477241424404503326038105933736781
4252906173088834257432032703513777373
2303802130437710703688308075181
40390816058452520269338213901
4568171019917945660378778313
695241852090706899848924713
475520466017929869269017687
91006397651881040963922091
120326038192017717890641
1627438593338485872391
1411882745182585251883
748888966107662666491
132368787963638991781
23381441824265929
21784054190313871
174457892355841
33676248367103
7940113978351
6905789865251
6685287754837
6550964325457
6377669507611
970272421141
142238678711
45081675187
5703087001
1923646771
500643721
476691121
182332981
117892981
35258347
6764411
5771677
3172501
612181
398681
356261
231331
132151
58741
26959
16111
8677
8147
2011
1171
1009
631
571
523
359
271
181
73
61
37
31
19
5
5
3
3
2
```

## Prime Factor Certification

Signed Primo certificate for `Phi(8055,40734)/(612181*117892981*182332981*1923646771*174457892355841*21784054190313871)` (19632 digits): `ecpp19632.7z`

Tom Wu