Primality Proof of phi(11311,34120)

OpenPFGW

Primality testing Phi(11311,34120) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 13
Calling Brillhart-Lehmer-Selfridge with factored part 29.61%
Phi(11311,34120) is PRP! (537.6329s+0.0025s)

CHG

   realprecision = 15008 significant digits (15000 digits displayed)

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

Input file is:  34120_11311.in
Certificate file is:  34120_11311.out
Found values of n, F and G.
    Number to be tested has 51269 digits.
    Modulus has 15179 digits.
Modulus is 29.605163401524163474% 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 5735 digits.
        Done!  Time elapsed:  55090ms.
    Running CHG with h = 5, u = 1. Right endpoint has 4622 digits.
        Done!  Time elapsed:  80840ms.
    Running CHG with h = 5, u = 1. Right endpoint has 4185 digits.
        Done!  Time elapsed:  92250ms.
    Running CHG with h = 5, u = 1. Right endpoint has 3310 digits.
        Done!  Time elapsed:  110290ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1559 digits.
        Done!  Time elapsed:  68540ms.
A certificate has been saved to the file:  34120_11311.out

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

Testing a PRP called "34120_11311.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=4.921144313427970055 E-1807 at X, ratio=6.199740085418355361 E-3366 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=4.025428835039836397 E-1751 at X, ratio=7.652071350319689225 E-1751 at Y, witness=3.
Pol[3, 1] with [h, u]=[4, 1] has ratio=7.702229459930194027 E-877 at X, ratio=9.987716197571524824 E-876 at Y, witness=2.
Pol[4, 1] with [h, u]=[4, 1] has ratio=4.729639853553320582 E-439 at X, ratio=1.9305969379067560316 E-438 at Y, witness=2.
Pol[5, 1] with [h, u]=[6, 2] has ratio=7.441555830303143575 E-1114 at X, ratio=5.292272831258085682 E-2226 at Y, witness=3.

Validated in 1 sec.


Congratulations! n is prime!
Goodbye!
A copy of the CHG certificate 34120_11311.out (408KB) is included in: 34120_11311.zip.

Helper File

Based on factorization of N-1 and N+1:
Phi(5655,34120)/(64772371*35066801243156348783521)
Phi(754,34120)/(40476229*76657481993)
13111237714623039055598945415936113569653787852446204688499016378095929634420033710017111288162694710763651623958204649341211
6297131741816286069027949660382125980801990956288362888954560936146922520489118223633800805673231
240821405045380491175252783892663368909077926365489143155241075402938113260527904252301
230668168238644757882054029993254133530231854036834566418507062449296885942341
763673376852376820831610782874133378058514623353
1670088404706346259316373001492083271792060731
18036823752679876058367097735380769100894443
9263909741218150451647068186072335899611971
599732773805621530122332798219267808132203
3517227586497767202387463399227629800981
951814244171111214718568232177464422921
643729226746409540963566185430157476843
49609911043486429751856453968711
1875306340968860090563161811121
95713587268695127634184399811
3550139552121071026231794983
263564292773427885970655471
53530263294556262988031121
46402984519487068133819581
3932905040401139075914603
128865435328616367439813
35066801243156348783521
9331336536602492369563
4427402236540256070061
49041046342807430731
2984973975240934111
1355262313148972281
452801143630932721
364594658771035681
276268779713887747
160133747525936861
123212886946372411
3031362319597
522970180981
426564165301
76657481993
58533796933
6268834963
5033888731
1380145729
1375205261
1374830731
562147021
151756711
85544317
64772371
55438501
40476229
22496011
6498727
5387201
5259151
5231717
950041
641713
483757
278981
214351
174929
102061
92221
92041
66301
63337
52201
41761
41263
33931
30161
22741
21841
21577
18329
13921
12511
11311
5743
5431
4003
853
811
523
521
313
233
229
157
149
131
79
59
31
11
7
5
3
2
2
2

Prime Factor Certification

Signed Primo certificate for Phi(5655,34120)/(64772371*35066801243156348783521) (12155 digits): ecpp12155.zip

A signed Primo certificate for Phi(754,34120)/(40476229*76657481993) (1505 digits) is included in: 34120_11311.zip.


Tom Wu
Last modified: Fri Apr 22 19:00:00 PDT 2011