Primality Certificate for (2963^3821-1)/2962

Andy Steward13,263 digits06 May 2008
Originally by Tom Wu 2005

This certificate uses a theorem of Coppersmith and Howgrave-Graham to prove an integer N prime by making use of a partial prime factorization of N-1.

Factorizing N-1

As N is a Generalized Repunit, we make use of the algebraic factorization of N-1 to arrive at the following 26.670920% factorization of N-1:

From Factorisation
29632963
Φ22 · 2 · 3 · 13 · 19
Φ42 · 5 · 877937
Φ511 · 281 · 1571 · 2131 · 7451
Φ101061 · 72621409561
Φ205 · 6136901 · 193612788851406863161
Φ1912293 · 4516387 · 172797319 · 119521520205062967009183017131 · p613
Φ382383 · 120331 · 2385209 · 69204649 · c638
Φ764107091547813 · 2542666085081 · 1116727839570819035825540099417 · c1266
Φ9553821 · 331996201 · 164295302531 · 30669353495491 · 62820518941231 · 195669265541951 · 111227212252446296592331 · c2551
Φ1910p2639
Φ38201642601 · c5271

We need the product F of all the prime factors from this partial factorization:

328247685 6042860196 1869564801 9928610644 1324820840 8858360265 5073673229 1800224899 2312302165 1082974599 0066466174 1101746865 1697834490 0695062020 5357584110 6982763570 1382821983 6632829897 8915282605 5720626438 9508464441 4537503469 1376822466 5372575452 5002269241 3093573193 1605920236 2364272236 1885684842 0647120765 0659115718 2821161606 4593379660 4770902669 5441735474 5853961219 3655377971 3371950868 4977607186 7138292785 9155251503 8224331856 5268159324 2148345959 9262254339 4941722107 5864205827 9134921602 1692117127 3650407939 1132454357 4887190258 2307971404 0035174763 9284430505 6761189163 3871446524 9241199731 5483534880 5498475850 5458881994 7176505813 8810511563 2165490862 6248273925 2753437084 4413413985 5422066987 7967513813 9486454390 0315114232 8095982723 6282748880 4513491606 6050005846 2199545512 9128029712 4741482742 6142737374 9450245014 1778465154 0128791168 4703743298 9864079248 2621196000 2644786233 8245290838 1909301020 9590326693 8309817930 6046859167 1982534034 1916402748 7477500294 2195275883 6654972503 6150091544 2367456295 7846914340 9127413141 3128347329 6153853638 1291252261 6532732492 8836621108 7688249452 3155295283 4471824736 9781962180 0292788760 3730543829 6208554950 9644885175 8917451606 8099690063 0483811144 1500470823 8781706609 7131121630 6707326421 4112697417 7353239250 6278076889 7367112498 5945765160 5865480461 1035077675 8556092568 7431778496 8650263468 5834463593 3667177249 5139884480 0486859774 7497761941 5986866314 2744375037 7094170468 6922652515 3858319280 3122174936 3917309993 0868432612 4362513495 2209363462 6372493150 3478925870 1098706564 4531348666 9424644677 5513032416 4260402650 9878954607 1357337600 2508445682 9222598436 4538079288 5362792289 4917870062 6683339782 4072212148 0207434215 0195947043 7716244452 3251623112 7052138571 5648362834 2995590565 1629620530 2857875695 7391583007 9959731483 2348588670 9533068685 3882635162 1534914839 1033044636 6850634249 6242891211 1552559818 8255517291 6729698761 0965929312 3786065159 0890859554 6836092696 9477461368 5553511523 7781074648 2407162814 0938367768 6898516127 5935726058 1687544291 1182600873 7635743433 5033605688 7999038684 1627521350 2183821333 7966419386 2343405058 5127853234 8311243849 0740990822 0902118970 2260314210 9491505997 1284026656 3949696702 9242309306 5246132274 9372849729 7023882263 2882411960 4637229534 7378546968 7016317270 3598126053 6454613721 4253733670 4353917362 2101089424 1739282479 4108974229 1416258661 5434928785 2058977178 5937010417 1875057503 5609693340 1799426224 9307507329 6826590822 8006198718 4866057311 6493454522 2531809738 9310293839 1537172028 3244288912 4844928767 7505817618 1825402424 7565385597 0058206995 8552645729 2051437452 2715168528 5376299588 9715852288 0494165076 6986395874 1227975866 8497139120 9422617919 2590267576 0014130278 0552838583 7147249894 8708655246 1726298517 8328802610 6137614321
199 0591140318 8072611436 1634783304 6614731637 1829849553 5360466023 4793464046 1711332610 4634126207 5710636225 6878256380 7767332583 2700529838 8638168038 2932021777 5417721090 8885386003 6268918891 9620622078 2764490979 7465459365 5071450643 0541130234 0627924500 3389815119 4747456579 0551648805 5162058196 6859397427 8627904834 8437349389 7059378359 0636808142 9585818103 4578619317 9082836266 3205060962 2669085442 3174449467 1932500345 4046061810 4265207089 4982067612 6114790108 6775658904 1849068633 5166307591 1501399352 1458086946 3734888998 1209879269 2511455507 1239062460 6757269425 2082315407 6653227333 2098783356 0225576402 2219384419 2560292487 0247849447
1 1167278395 7081903582 5540099417
1195215202 0506296700 9183017131
1112 2721225244 6296592331
1 9361278885 1406863161
19566 9265541951
6282 0518941231
3066 9353495491
254 2666085081
16 4295302531
10 7091547813
7 2621409561
331996201
172797319
69204649
6136901
4516387
2385209
1642601
877937
120331
7451
3821
2963
2293
2131
1571
1061
383
281
19
13
11
52
3
23

Note that all prime factors listed above have been proven. As primes of under 250 decimal digits can be verified in a few seconds, proof of their primality is not included here, in order to save space. Larger prime factors can take from hours to months to prove; certificates for all such factors have been PKZIPped into this file.

We set R = (N-1)/F. Note that GCD(F,R)=1 and Log(F)/Log(N) = 26.670920%

Finding a Witness to Primality

Next, we find an integer witness w such that for each prime factor p of N-1, w(N-1) ≡ 1 mod N and GCD(w(N-1)/p-1,N) = 1. In this case, w = 6601 suffices.

Given such a witness, Pocklington's Theorem shows that every prime factor of N ≡ 1 (mod F). As F4>N, N can have no more than three prime factors.

Express N in base F

As F2 < N < F3 and N ≡ 1 (mod F), we can let N = c2·F2 + c1·F + 1.

Brillhart, Lehmer and Selfridge

Brillhart, Lehmer and Selfridge's Theorem shows that N has exactly two prime factors if and only if c12-4·c2 is a perfect square.

Here, c12-4·c2 is ≡ 61 (mod 64) and therefore cannot be a square and this stage of the proof is passed.

Coppersmith and Howgrave-Graham

We are left with two possibilities for N: either it has exactly three prime factors or it is prime. The non-existence of exactly three factors is demonstrated by the Theorem of Coppersmith and Howgrave-Graham, here performed by a Pari/GP script written by John Renze and David Broadhurst. Here is the stdout:

parisize = 64000000, primelimit = 500000

Testing a PRP called "Phi_3821_2963".

LLL[1, 1] with [h, u]=[5, 1] has norm/bound=4.436400008 E-688 and witness=5.
LLL[2, 1] with [h, u]=[5, 1] has norm/bound=0.3729775135 and witness=7.
LLL[3, 1] with [h, u]=[4, 1] has norm/bound=1.057259594 E-99 and witness=3.
LLL[4, 1] with [h, u]=[7, 2] has norm/bound=3.839587174 E-66 and witness=47.
LLL[5, 1] with [h, u]=[7, 2] has norm/bound=0.2931494234 and witness=2.
LLL[6, 1] with [h, u]=[7, 2] has norm/bound=0.2780876639 and witness=7.
LLL[7, 1] with [h, u]=[7, 2] has norm/bound=0.2907265962 and witness=3.
LLL[8, 1] with [h, u]=[7, 2] has norm/bound=0.3190416871 and witness=3.
LLL[9, 1] with [h, u]=[7, 2] has norm/bound=0.2562215346 and witness=5.
LLL[10, 1] with [h, u]=[9, 3] has norm/bound=1.535379507 E-55 and witness=29.
LLL[11, 1] with [h, u]=[9, 3] has norm/bound=4.934553068 E-14 and witness=11.
LLL[12, 1] with [h, u]=[9, 3] has norm/bound=0.2141565823 and witness=37.
LLL[13, 1] with [h, u]=[9, 3] has norm/bound=0.2258375512 and witness=2.
LLL[14, 1] with [h, u]=[9, 3] has norm/bound=0.2160944726 and witness=61.
LLL[15, 1] with [h, u]=[9, 3] has norm/bound=0.1779331924 and witness=5.
LLL[16, 1] with [h, u]=[9, 3] has norm/bound=0.2458638097 and witness=13.
LLL[17, 1] with [h, u]=[11, 4] has norm/bound=3.951949925 E-24 and witness=2.
LLL[18, 1] with [h, u]=[11, 4] has norm/bound=0.1879600406 and witness=11.
LLL[19, 1] with [h, u]=[11, 4] has norm/bound=0.2106108764 and witness=13.
LLL[20, 1] with [h, u]=[11, 4] has norm/bound=0.1761235534 and witness=101.
LLL[21, 1] with [h, u]=[11, 4] has norm/bound=0.1929548615 and witness=83.
LLL[22, 1] with [h, u]=[11, 4] has norm/bound=0.1707713333 and witness=31.
LLL[23, 1] with [h, u]=[11, 4] has norm/bound=0.1928274294 and witness=71.
LLL[24, 1] with [h, u]=[11, 4] has norm/bound=0.1568574031 and witness=17.
LLL[25, 1] with [h, u]=[13, 5] has norm/bound=0.1266733356 and witness=61.
LLL[26, 1] with [h, u]=[13, 5] has norm/bound=0.1193527275 and witness=47.
LLL[27, 1] with [h, u]=[13, 5] has norm/bound=0.1420230977 and witness=79.
LLL[28, 1] with [h, u]=[13, 5] has norm/bound=0.1150697941 and witness=59.
LLL[29, 1] with [h, u]=[13, 5] has norm/bound=0.1266531634 and witness=101.
LLL[30, 1] with [h, u]=[13, 5] has norm/bound=0.1074611888 and witness=47.
LLL[31, 1] with [h, u]=[13, 5] has norm/bound=0.1172410057 and witness=3.
LLL[32, 1] with [h, u]=[13, 5] has norm/bound=0.1195326339 and witness=23.
LLL[33, 1] with [h, u]=[13, 5] has norm/bound=0.1334955721 and witness=7.
LLL[34, 1] with [h, u]=[13, 5] has norm/bound=0.1248777288 and witness=349.
LLL[35, 1] with [h, u]=[13, 5] has norm/bound=0.1276266609 and witness=3.
LLL[36, 1] with [h, u]=[13, 5] has norm/bound=0.1252424612 and witness=3.
LLL[37, 1] with [h, u]=[15, 6] has norm/bound=0.1006357336 and witness=2.
LLL[38, 1] with [h, u]=[15, 6] has norm/bound=0.0946684291 and witness=2.
LLL[39, 1] with [h, u]=[15, 6] has norm/bound=0.1040232139 and witness=107.
LLL[40, 1] with [h, u]=[15, 6] has norm/bound=0.0993742563 and witness=37.
LLL[41, 1] with [h, u]=[15, 6] has norm/bound=0.0970848877 and witness=2.
LLL[42, 1] with [h, u]=[15, 6] has norm/bound=0.1022023459 and witness=43.
LLL[43, 1] with [h, u]=[15, 6] has norm/bound=0.0920833767 and witness=47.
LLL[44, 1] with [h, u]=[16, 7] has norm/bound=0.0777008415 and witness=3.
LLL[45, 1] with [h, u]=[16, 7] has norm/bound=0.0807295906 and witness=31.
LLL[46, 1] with [h, u]=[16, 7] has norm/bound=7.41270031 E-16 and witness=41.

Validated in 33 sec.

Goodbye!

The actual input file containing N and F and the output certificate are included in this file.