# Primality Proof of phi(3821,2963)

## OpenPFGW

```Primality testing Phi(3821,2963) [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Running N-1 test using base 23
Running N-1 test using base 41
Calling Brillhart-Lehmer-Selfridge with factored part 26.67%
Phi(3821,2963) is PRP! (1904.7080s+0.0905s)
```

## CHG

```                   GP/PARI CALCULATOR Version 2.2.10 (alpha)
i686 running linux (ix86/GMP-4.1.4 kernel) 32-bit version
compiled: Sep 15 2005, gcc-3.3.2 20031022 (Red Hat Linux 3.3.2-1)
(readline v4.3 enabled, extended help not available)

Copyright (C) 2000-2005 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 = 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!
```
A copy of the self-verifying CHG certificate `Phi_3821_2963.gp` (7288kb) is included in: `2963_3821.zip`.

## Helper File

Based on factorization of N-1:
```(2963^764-2963^573+2963^382-2963^191+1)/77051315544221
(2963^191-1)/(2962*2293*4516387*172797319*119521520205062967009183017131)
1116727839570819035825540099417
119521520205062967009183017131
111227212252446296592331
193612788851406863161
195669265541951
62820518941231
30669353495491
2542666085081
164295302531
107091547813
72621409561
331996201
172797319
69204649
6136901
4516387
2385209
1642601
877937
120331
7451
3821
2963
2293
2131
1571
1061
383
281
19
13
11
5
5
3
2
2
2
```

## Prime Factor Certification

Signed Primo certificates for `(2963^764-2963^573+2963^382-2963^191+1)/77051315544221` (2639 digits) and `(2963^191-1)/(2962*2293*4516387*172797319*119521520205062967009183017131)` (613 digits) are included in: `2963_3821.zip`

Tom Wu