# Primality Proof of phi(21961,102936)

## OpenPFGW

```Primality testing (102936^21961-1)/102935 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 17
Running N-1 test using base 23
Calling Brillhart-Lehmer-Selfridge with factored part 28.90%
(102936^21961-1)/102935 is PRP! (2000.8867s+0.0380s)
```

## CHG

```                     GP/PARI CALCULATOR Version 2.3.5 (released)
amd64 running linux (x86-64/GMP-5.1.3 kernel) 64-bit version
compiled: Jun 19 2015, gcc-4.8.3 (Gentoo 4.8.3 p1.1, pie-0.5.9)
(readline v6.3 enabled [was v6.2 in Configure], extended help not available)

Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
realprecision = 38011 significant digits (38000 digits displayed)

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

Input file is:  102936_21961.in
Certificate file is:  102936_21961.out
Found values of n, F and G.
Number to be tested has 110076 digits.
Modulus has 31817 digits.
Modulus is 28.904227166050317198% 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 14627 digits.
Done!  Time elapsed:  759360ms.
Running CHG with h = 6, u = 2. Right endpoint has 13858 digits.
Done!  Time elapsed:  781710ms.
Running CHG with h = 6, u = 2. Right endpoint has 12704 digits.
Done!  Time elapsed:  821240ms.
Running CHG with h = 6, u = 2. Right endpoint has 10974 digits.
Done!  Time elapsed:  918760ms.
Running CHG with h = 5, u = 1. Right endpoint has 8999 digits.
Done!  Time elapsed:  34670ms.
Running CHG with h = 5, u = 1. Right endpoint has 7391 digits.
Done!  Time elapsed:  486560ms.
Running CHG with h = 5, u = 1. Right endpoint has 4177 digits.
Done!  Time elapsed:  303750ms.
A certificate has been saved to the file:  102936_21961.out

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

Testing a PRP called "102936_21961.in".

Pol[1, 1] with [h, u]=[4, 1] has ratio=1.1023637980326456758 E-1554 at X, ratio=6.265057096261096300 E-5731 at Y, witness=19.
Pol[2, 1] with [h, u]=[4, 1] has ratio=2.497234539872269720 E-3215 at X, ratio=3.505358743852506737 E-3215 at Y, witness=2.
Pol[3, 1] with [h, u]=[4, 1] has ratio=1.5379572383820345602 E-1608 at X, ratio=4.329144573047502087 E-1608 at Y, witness=3.
Pol[4, 1] with [h, u]=[6, 2] has ratio=0.4804094507487863077 at X, ratio=2.780774057569179522 E-3951 at Y, witness=3.
Pol[5, 1] with [h, u]=[6, 2] has ratio=2.3725026694980425190 E-1731 at X, ratio=2.694719119456704628 E-3461 at Y, witness=17.
Pol[6, 1] with [h, u]=[6, 2] has ratio=1.7545751712564503972 E-1154 at X, ratio=9.001557466551037667 E-2308 at Y, witness=7.
Pol[7, 1] with [h, u]=[6, 2] has ratio=2.932290412794266239 E-770 at X, ratio=6.852746947886734428 E-1539 at Y, witness=5.

Validated in 2 sec.

Congratulations! n is prime!
Goodbye!
```
A copy of the CHG certificate `102936_21961.out` (1.7MB) is included in: `102936_21961.zip`.

## Helper File

Based on factorization of N-1 and N+1:
```Phi(21960,102936)/(3357280321261926309361*1494555848158024189441)
Phi(305,102936)/(2441*294619434695081*105002619170569168076681)
1746926500175853803172466268390550012229545298574931771208826735092717641331478531791560586667231193061
913921220468141932684727188987588647655565223524063459440593401
372228939485557291826049987103436809853087658000514452697
26171092894768527919935534343571037779606884767121
257203691979950270650934609764779680538841
72269991852694245558696904980591736756441
248154232431854059768335819588040796581
27581768151829607390228716026996283513
1727910203816794028663374480333636217
1437329357634875940551372161181715361
2738184982059203646739233943489561
2490427667530124358647679956922841
614147252947905209885708941835161
20071151513672834849647925509231
3096057572716003963132854654721
1768669964536199423951224290691
445119073157193763129723217521
207524719043495453637773159033
852345939903752289214057081
759947890803296327121354943
15614081636820771088269991
1180394763661588791052651
128938200008407234074793
105002619170569168076681
32196167766910351174921
3357280321261926309361
2458643396497349169169
1618048849704719241961
1494555848158024189441
1129365854573311214317
958394476452837392201
553998990080430384289
534940813689142769791
497916969633314793091
382930511592262545361
2935847080898971661
1832198363138822311
1691875535336556319
1261476443896600553
99209000186596243
13749536178393481
4240177030667041
4230298243578691
743665576969921
294619434695081
205580972831833
42117847051807
3300534820831
1999653498901
554061446299
144274302379
111822401413
78344192593
58681934921
46305141481
10595923033
10595820097
6307702561
5734662949
4079580139
3601260661
1467205741
913832461
526296313
345936301
294615361
266969641
246412027
242236369
128070721
108844741
89731489
73835987
24271921
4158961
3613789
3225191
1807129
1367987
1542221
1089217
703441
343381
334891
221797
193201
178609
174637
172981
72103
65881
63361
49411
47581
47441
45361
38431
34039
30181
21961
18217
15373
13591
13421
7321
5857
4637
4289
2441
2341
2161
1831
1303
1291
977
733
457
367
281
271
241
181
151
101
89
79
73
71
61
61
43
41
37
31
19
13
11
5
3
2
2
2
```

## Prime Factor Certification

Primo-format certificates for `Phi(21960,102936)/(3357280321261926309361*1494555848158024189441)` (28830 digits) and `Phi(305,102936)/(2441*294619434695081*105002619170569168076681)` (1163 digits) generated by CM-ECPP are included in: `102936_21961.zip`

Tom Wu