Finding 𝐶₃-strong pseudoprimes
Authors: Zhang Zhenxiang 
Published: January 2005

Let

q
1

>

q
2

>

q
3

q_1>q_2>q_3

be odd primes and

N
=

q
1

q
2

q
3

N=q_1q_2q_3

. Put
\[

d
=
gcd
(

q
1

−
1
,

q
2

−
1
,

q
3

−
1
)
 and 

h
i

=

q
i

−
1

d

,

i
=
1
,
2
,
3.

d=\gcd (q_1-1,q_2-1,q_3-1) \text { and } h_i=\tfrac {q_i-1}d, \;i=1,2,3.

\]
Then we call

d
d

the kernel, the triple

(

h
1

,

h
2

,

h
3

)

(h_1,h_2,h_3)

the signature, and

H
=

h
1

h
2

h
3

H=h_1h_2h_3

the height of

N
N

, respectively. We call

N
N

a

C
3

C_3

-number if it is a Carmichael number with each prime factor

q
i

≡
3

mod

4

q_i\equiv 3\mod 4

. If

N
N

is a

C
3

C_3

-number and a strong pseudoprime to the

t
t

bases

b
i

b_i

for

1
≤
i
≤
t

1\leq i\leq t

, we call

N
N

a

C
3

C_3

-spsp

(

b
1

,

b
2

,
…
,

b
t

)

(b_1, b_2,\dots ,b_t)

. Since

C
3

C_3

-numbers have probability of error

1

/

4

1/4

(the upper bound of that for the Rabin-Miller test), they often serve as the exact values or upper bounds of

ψ
m

\psi _m

(the smallest strong pseudoprime to all the first

m
m

prime bases). If we know the exact value of

ψ
m

\psi _m

, we will have, for integers

n
>

ψ
m

n>\psi _m

, a deterministic efficient primality testing algorithm which is easy to implement. In this paper, we first describe an algorithm for finding

C
3

C_3

-spsp(2)’s, to a given limit, with heights bounded. There are in total

21978
21978

C
3

C_3

-spsp

(
2
)

(2)

’s

>

10

24

>10^{24}

with heights

>

10
9

>10^9

. We then give an overview of the 21978

C
3

C_3

- spsp(2)’s and tabulate

54
54

of them, which are

C
3

C_3

-spsp’s to the first

8
8

prime bases up to

19
19

; three numbers are spsp’s to the first 11 prime bases up to 31. No

C
3

C_3

-spsp’s

>

10

24

>10^{24}

to the first

12
12

prime bases with heights

>

10
9

>10^9

were found. We conjecture that there exist no

C
3

C_3

-spsp’s

>

10

24

>10^{24}

to the first

12
12

prime bases with heights

≥

10
9

\geq 10^9

and so that
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartLayout 1st Row 1st Column psi 12 2nd Column a m p semicolon equals 3186 65857 83403 11511 67461 left-parenthesis 24 digits right-parenthesis 2nd Row 1st Column Blank 2nd Column a m p semicolon equals 399165290221 dot 798330580441 comma EndLayout">

ψ

12

a
m
p
;
=
3186

65857

83403

11511

67461

(24 digits)

a
m
p
;
=
399165290221
⋅
798330580441
,

\begin{equation*} \begin {split} \psi _{12}&= 3186\; 65857\; 83403\; 11511\; 67461\; \text {(24 digits)} \\ &=399165290221\cdot 798330580441, \end{split}\end{equation*}

which was found by the author in an earlier paper. We give reasons to support the conjecture. The main idea of our method for finding those

21978
21978

C
3

C_3

-spsp

(
2
)

(2)

’s is that we loop on candidates of signatures and kernels with heights bounded, subject those candidates

N
=

q
1

q
2

q
3

N=q_1q_2q_3

of

C
3

C_3

-spsp

(
2
)

(2)

’s and their prime factors

q
1

,

q
2

,

q
3

q_1,q_2,q_3

to Miller’s tests, and obtain the desired numbers. At last we speed our algorithm for finding larger

C
3

C_3

-spsp’s, say up to

10

50

10^{50}

, with a given signature to more prime bases. Comparisons of effectiveness with Arnault’s and our previous methods for finding

C
3

C_3

-strong pseudoprimes to the first several prime bases are given.