Primality Proof of (908215091-1)/9081

OpenPFGW

Primality testing (9082^15091-1)/9081 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Running N-1 test using base 5
Calling Brillhart-Lehmer-Selfridge with factored part 27.12%
(9082^15091-1)/9081 is PRP! (826.3181s+0.4382s)

CHG

   realprecision = 24005 significant digits (24000 digits displayed)

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

Input file is:  9082_15091.in
Certificate file is:  9082_15091.out
Found values of n, F and G.
    Number to be tested has 59729 digits.
    Modulus has 16199 digits.
Modulus is 27.120603843096306510% 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 11133 digits.
        Done!  Time elapsed:  1232870ms.
    Running CHG with h = 12, u = 5. Right endpoint has 10966 digits.
        Done!  Time elapsed:  1194690ms.
    Running CHG with h = 12, u = 5. Right endpoint has 10765 digits.
        Done!  Time elapsed:  5771100ms.
    Running CHG with h = 12, u = 5. Right endpoint has 10562 digits.
        Done!  Time elapsed:  5731300ms.
    Running CHG with h = 12, u = 5. Right endpoint has 10352 digits.
        Done!  Time elapsed:  10710740ms.
    Running CHG with h = 11, u = 4. Right endpoint has 10120 digits.
        Done!  Time elapsed:  1033720ms.
    Running CHG with h = 11, u = 4. Right endpoint has 10026 digits.
        Done!  Time elapsed:  1395860ms.
    Running CHG with h = 11, u = 4. Right endpoint has 9909 digits.
        Done!  Time elapsed:  1981890ms.
    Running CHG with h = 11, u = 4. Right endpoint has 9762 digits.
        Done!  Time elapsed:  1814880ms.
    Running CHG with h = 11, u = 4. Right endpoint has 9575 digits.
        Done!  Time elapsed:  3683950ms.
    Running CHG with h = 11, u = 4. Right endpoint has 9345 digits.
        Done!  Time elapsed:  3960540ms.
    Running CHG with h = 11, u = 4. Right endpoint has 9057 digits.
        Done!  Time elapsed:  18916260ms.
    Running CHG with h = 11, u = 4. Right endpoint has 8697 digits.
        Done!  Time elapsed:  19970550ms.
    Running CHG with h = 9, u = 3. Right endpoint has 8247 digits.
        Done!  Time elapsed:  564200ms.
    Running CHG with h = 9, u = 3. Right endpoint has 8070 digits.
        Done!  Time elapsed:  405180ms.
    Running CHG with h = 9, u = 3. Right endpoint has 7835 digits.
        Done!  Time elapsed:  287220ms.
    Running CHG with h = 9, u = 3. Right endpoint has 7520 digits.
        Done!  Time elapsed:  306680ms.
    Running CHG with h = 9, u = 3. Right endpoint has 7101 digits.
        Done!  Time elapsed:  2405370ms.
    Running CHG with h = 7, u = 2. Right endpoint has 6543 digits.
        Done!  Time elapsed:  548060ms.
    Running CHG with h = 7, u = 2. Right endpoint has 6394 digits.
        Done!  Time elapsed:  672070ms.
    Running CHG with h = 7, u = 2. Right endpoint has 6096 digits.
        Done!  Time elapsed:  44790ms.
    Running CHG with h = 7, u = 2. Right endpoint has 5695 digits.
        Done!  Time elapsed:  123470ms.
    Running CHG with h = 7, u = 2. Right endpoint has 4712 digits.
        Done!  Time elapsed:  183360ms.
    Running CHG with h = 5, u = 1. Right endpoint has 3588 digits.
        Done!  Time elapsed:  16310ms.
    Running CHG with h = 5, u = 1. Right endpoint has 1446 digits.
        Done!  Time elapsed:  40780ms.
A certificate has been saved to the file:  9082_15091.out

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

Testing a PRP called "9082_15091.in".

Pol[1, 1] with [h, u]=[5, 1] has ratio=2.8598921814885988334 E-2261 at X, ratio=2.503359212293993857 E-2811 at Y, witness=3.
Pol[2, 1] with [h, u]=[4, 1] has ratio=0.3985198549268837793 at X, ratio=2.0974201932765759114 E-2142 at Y, witness=23.
Pol[3, 1] with [h, u]=[7, 2] has ratio=9.767215860326297502 E-13 at X, ratio=7.190332131226196698 E-2249 at Y, witness=13.
Pol[4, 1] with [h, u]=[7, 2] has ratio=0.9999999999993286748 at X, ratio=1.4906755391344433729 E-1966 at Y, witness=3.
Pol[5, 1] with [h, u]=[7, 2] has ratio=0.7126291568689247449 at X, ratio=9.915035396793596977 E-803 at Y, witness=17.
Pol[6, 1] with [h, u]=[7, 2] has ratio=3.559804514083092834 E-381 at X, ratio=2.7430927985751780012 E-596 at Y, witness=3.
Pol[7, 1] with [h, u]=[7, 2] has ratio=2.7430927985751780012 E-596 at X, ratio=1.6562284862225918138 E-298 at Y, witness=3.
Pol[8, 1] with [h, u]=[9, 3] has ratio=0.05667185694747806676 at X, ratio=1.0947574748839064900 E-1676 at Y, witness=3.
Pol[9, 1] with [h, u]=[9, 3] has ratio=0.5284676885014765429 at X, ratio=1.3352840603983531846 E-1257 at Y, witness=11.
Pol[10, 1] with [h, u]=[9, 3] has ratio=0.10637803750357910010 at X, ratio=2.1955536605370562588 E-943 at Y, witness=5.
Pol[11, 1] with [h, u]=[9, 3] has ratio=0.12245267478358121479 at X, ratio=8.710662125225153131 E-708 at Y, witness=7.
Pol[12, 1] with [h, u]=[9, 3] has ratio=0.3390976382665094861 at X, ratio=5.184030645982408452 E-531 at Y, witness=2.
Pol[13, 1] with [h, u]=[11, 4] has ratio=0.14585331367970437011 at X, ratio=3.815072355612267404 E-1800 at Y, witness=2.
Pol[14, 1] with [h, u]=[11, 4] has ratio=0.11633046556273361902 at X, ratio=3.130571451766442157 E-1440 at Y, witness=3.
Pol[15, 1] with [h, u]=[11, 4] has ratio=0.4225150802326976844 at X, ratio=2.3912869086164155122 E-1152 at Y, witness=2.
Pol[16, 1] with [h, u]=[11, 4] has ratio=0.3840707375616814661 at X, ratio=4.773902473303361651 E-922 at Y, witness=3.
Pol[17, 1] with [h, u]=[11, 4] has ratio=6.596757259613828200 E-236 at X, ratio=7.911663944916507808 E-747 at Y, witness=5.
Pol[18, 1] with [h, u]=[11, 4] has ratio=0.09405395758322078881 at X, ratio=1.4629793976104511277 E-588 at Y, witness=11.
Pol[19, 1] with [h, u]=[11, 4] has ratio=0.23803150180847264332 at X, ratio=5.593942889984637266 E-471 at Y, witness=11.
Pol[20, 1] with [h, u]=[11, 4] has ratio=0.12373803928998745950 at X, ratio=5.684014534856131042 E-377 at Y, witness=3.
Pol[21, 1] with [h, u]=[12, 5] has ratio=0.5659805900880728071 at X, ratio=1.0783000041433717972 E-1157 at Y, witness=3.
Pol[22, 1] with [h, u]=[12, 5] has ratio=0.03369209106309316607 at X, ratio=1.4704931083397995351 E-1052 at Y, witness=2.
Pol[23, 1] with [h, u]=[12, 5] has ratio=0.011840735803376724403 at X, ratio=1.6666603493253789171 E-1018 at Y, witness=13.
Pol[24, 1] with [h, u]=[12, 5] has ratio=7.644153892406875987 E-165 at X, ratio=1.2473154825156209833 E-1003 at Y, witness=2.
Pol[25, 1] with [h, u]=[12, 5] has ratio=3.339708056926087461 E-168 at X, ratio=1.5632801326973244923 E-836 at Y, witness=5.

Validated in 11 sec.


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

Helper File

Based on factorization of N-1 and N+1:
Phi(7545,9082)/(4104481*65354791)
1128109789935491603657233
63366688090364823232661
75012651523631928888421
5972915865715749229141
6560100160366477601
5910969093317947
278512777344041
276385677561223
205220202481787
29493365651
14522133121
716913829
72227783
65354791
30449071
11781949
4104481
2169841
1140691
707219
362161
120721
40241
15091
6037
5051
4231
4021
3571
3019
821
541
293
281
239
97
67
31
19
11
7
3
2

Prime Factor Certification

Signed Primo certificate for Phi(7545,9082)/(4104481*65354791) (15882 digits) is included in: 9082_15091.zip.


Tom Wu
Last modified: Mon Oct 13 19:00:00 PDT 2014