3^1681130 + 3^445781 + 1 is prime.

By: | Comments: No Comments

Posted in categories: Fun Stuffs, Prime Search

Proof file:

HERE Record page here.

3^1681130+3^445781+1 has 802,104 digits

factor of p-1:

3^1681130+3^445781 = 3^445781*(3^1235349+1)

for 3^1235349+1:

Divisor of 1235349: {1, 3, 9, 317, 433, 951, 1299, 2853, 3897, 137261, 411783, 1235349}

for which Cyclotomic[2x,3] divides 3^1235349+1, 3^1235349+1=Product of Phi[2m,3], m is in the above divisor list.

Phi: Cyclotomic function in Mathematica.

Phi[2,3] = 4 = 2^2

Phi[6,3] = 7

Phi[18,3] = 703 = 19*37

Phi[634,3] = 4419546979734297356356282440566337101076156046659615868982274149497888767412192670918210853094818317044028461371947192040491503227984348283966155849541 = 76824655095930309016347566008213507 *
57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863

Phi[866,3] = 98049030167138868235272337490364772443278341679136020523778017973332584069900487425071613559614188734321215787769494533118401761096043098454024530209394531738061292786842020371958081509924820005117783644881 = 5197 * 25981 * 10986786121 * 2545641110123181683038777028652229 * 4078872265954752990198205964113561121059 * 48719802170502964448205757292294067215837963275487416471 * 130653562236213178463808841348368553389712956028240802263033

Phi[1902,3] = 454579 * 36324397 * 4242031875148351 * 110636908354198084399 * 549512115983126575855924649876601277813687417 * cp_1681130_+3_445781_c1_+1_P1902_c209[ecm50]

Phi[2598,3] = 49363 * 69183924850105534244247847 * 590120330956087803199 * 24518336107758964004567688595327267 * 72294725439409852600619119163684989 *
cp_1681130_+3_445781_c1_+1_P2598_c292[ecm40]

Phi[5706,3] = 958609 * 1061317 * 105429763 * 65641802577791850271 * 466581320825998331248111 * 161770166547973894056628560367 * 4121313630402929050856881 * 35041165225208415265755372540106879 * 145166850946125723698625301282936985977 *
cp_1681130_+3_445781_c1_+1_P5706_c715[ecm40]

Phi[7794,3] = 2369645352847 * 18271583019418565050835779232047 *
cp_1681130_+3_445781_c1_+1_P7794_c1194[ecm40]

Phi[274522,3] = cp_1681130_+3_445781_c1_+1_P274522_c65133[ecm30 – done 20220828]
Phi[823566,3] = 48031581409153 * cp_1681130_+3_445781_c1_+1_P823566_c130252[ecm20]

Phi[2470698,3] = 59296753 * 2841667923519757 * cp_1681130_+3_445781_c1_+1_P2470698_c390774[ecmpm]

Factors of p-1:
2^2
3^445781
7
19
37
5197
25981
49363
454579
958609
1061317
36324397
59296753
105429763
10986786121
2369645352847
48031581409153
2841667923519757
4242031875148351
65641802577791850271

110636908354198084399
590120330956087803199
466581320825998331248111
4121313630402929050856881
69183924850105534244247847
161770166547973894056628560367
18271583019418565050835779232047
2545641110123181683038777028652229
24518336107758964004567688595327267
35041165225208415265755372540106879
72294725439409852600619119163684989
76824655095930309016347566008213507
145166850946125723698625301282936985977
4078872265954752990198205964113561121059
549512115983126575855924649876601277813687417
48719802170502964448205757292294067215837963275487416471
130653562236213178463808841348368553389712956028240802263033
57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863

Factors of p-1: [2^23^445781*7*19*37*5197*25981*49363*454579*958609*1061317*36324397*59296753*105429763*10986786121*2369645352847*48031581409153*2841667923519757*4242031875148351*65641802577791850271*110636908354198084399*590120330956087803199*466581320825998331248111*4121313630402929050856881*69183924850105534244247847*161770166547973894056628560367*18271583019418565050835779232047*2545641110123181683038777028652229*24518336107758964004567688595327267*35041165225208415265755372540106879*72294725439409852600619119163684989*76824655095930309016347566008213507*145166850946125723698625301282936985977*4078872265954752990198205964113561121059*549512115983126575855924649876601277813687417*48719802170502964448205757292294067215837963275487416471*130653562236213178463808841348368553389712956028240802263033*57527716515168805301518081894378217354338616431161859310399702927298973147371258119477233264821539853770687247299863]

$ ./pfgw -tc -k -h”cp_1681130_+3_445781_c1_+1.helper” cp_1681130_+3_445781_c1_+1
Primality testing 3^1681130+3^445781+1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Reading factors from helper file cp_1681130_+3_445781_c1_+1.helper
Running N-1 test using base 2
Running N+1 test using discriminant 5, base 5+sqrt(5)
3^1681130+3^445781+1 is Fermat and Lucas PRP! (72918.0430s+0.0527s)

$ gp
Reading GPRC: /etc/gprc …Done.

                                                                                      GP/PARI CALCULATOR Version 2.11.3 (released)
                                                                              amd64 running linux (x86-64/GMP-6.1.2 kernel) 64-bit version
                                                                        compiled: Apr  6 2020, gcc version 8.3.1 20190507 (Red Hat 8.3.1-4) (GCC)
                                                                                                threading engine: single
                                                                                     (readline v7.0 enabled, extended help enabled)

                                                                                         Copyright (C) 2000-2018 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 ?17 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
? \r CHG.GP
*** Warning: new stack size = 17179869184 (16384.000 Mbytes).
realprecision = 350003 significant digits (350000 digits displayed)

Welcome to the CHG primality prover!

Input file is: cp_1681130_+3_445781_c1_+1.in
Certificate file is: cp_1681130_+3_445781_c1_+1.out
Found values of n, F and G.
Number to be tested has 802103 digits.
Modulus has 213408 digits.
Modulus is 26.605944113118165830% 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 = 16, u = 7. Right endpoint has 161883 digits.
Done! Time elapsed: 810732137ms.
Running CHG with h = 16, u = 7. Right endpoint has 155873 digits.
Done! Time elapsed: 825907227ms.
Running CHG with h = 15, u = 6. Right endpoint has 149984 digits.
Done! Time elapsed: 367063741ms.
Running CHG with h = 15, u = 6. Right endpoint has 141864 digits.
Done! Time elapsed: 403218994ms.
Running CHG with h = 13, u = 5. Right endpoint has 135499 digits.
Done! Time elapsed: 167649019ms.
Running CHG with h = 13, u = 5. Right endpoint has 126589 digits.
Done! Time elapsed: 166344631ms.
Running CHG with h = 11, u = 4. Right endpoint has 115818 digits.
Done! Time elapsed: 62966916ms.
Running CHG with h = 9, u = 3. Right endpoint has 102257 digits.
Done! Time elapsed: 21474045ms.
Running CHG with h = 9, u = 3. Right endpoint has 86036 digits.
Done! Time elapsed: 18674057ms.
Running CHG with h = 7, u = 2. Right endpoint has 57119 digits.
Done! Time elapsed: 4457878ms.
A certificate has been saved to the file: cp_1681130_+3_445781_c1_+1.out

Running David Broadhurst’s verifier on the saved certificate…

Testing a PRP called “cp_1681130_+3_445781_c1_+1.in”.

Pol[1, 1] with [h, u]=[7, 2] has ratio=3.292364120998444652 E-98758 at X, ratio=3.718585580771175970 E-194048 at Y, witness=2.
Pol[2, 1] with [h, u]=[9, 3] has ratio=6.126565950304076461 E-9475 at X, ratio=1.1209288730275909543 E-86752 at Y, witness=2.
Pol[3, 1] with [h, u]=[9, 3] has ratio=4.686378714776338379 E-48664 at X, ratio=4.686378714776338379 E-48664 at Y, witness=2.
Pol[4, 1] with [h, u]=[11, 4] has ratio=1.1328882856917741933 E-83833 at X, ratio=4.446338007106078208 E-54243 at Y, witness=2.
Pol[5, 1] with [h, u]=[10, 5] has ratio=1.3491587713343525002 E-21542 at X, ratio=2.1142563956459774573 E-53855 at Y, witness=2.
Pol[6, 1] with [h, u]=[10, 5] has ratio=2.1142563956459774573 E-53855 at X, ratio=7.365995469140945291 E-44554 at Y, witness=2.
Pol[7, 1] with [h, u]=[15, 6] has ratio=2.101399014710577216 E-89107 at X, ratio=2.654191320795251087 E-38189 at Y, witness=2.
Pol[8, 1] with [h, u]=[13, 6] has ratio=3.530699982729085833 E-8120 at X, ratio=1.9371573230603122010 E-48717 at Y, witness=2.
Pol[9, 1] with [h, u]=[16, 7] has ratio=5.410890206996781797 E-22058 at X, ratio=1.0071182035514125678 E-41222 at Y, witness=2.
Pol[10, 1] with [h, u]=[16, 7] has ratio=5.814090534021862076 E-14617 at X, ratio=8.275867222128713413 E-42071 at Y, witness=2.

Validated in 116 sec.

Congratulations! n is prime!
Goodbye!

Be the first to comment!

Leave a Reply