Conjectures on strong psp
Back Ground
Define ψm
to be the smallest strong pseudoprime to all
the first m prime bases. If n < ψm, then only m Miller tests are needed to find out whether n is prime or not. This
means that if we know the exact value of ψm, then for integers n < ψm we will have a deterministic primality testing algorithm which is not only easier to
implement but also faster than either the Jacobi sum test or the elliptic curve
test. In 1980, Pomerance et al. found the exact value
of ψm for 1 ≤m ≤4:
Ψ1 = 23 * 89 = 2047,
Ψ2 =829 * 1657 = 1373653,
Ψ3 =2251 * 11251 =
25326001,
Ψ4 =151* 751* 28351 = 3215031751.
In 1993, Jaeschke found the exact value of ψm for 5 ≤m ≤8:
Ψ5 =6763* 10627* 29947 =
2152302898747,
Ψ6 =1303* 16927* 157543
= 3474749660383,
Ψ7 =Ψ8 =
10670053 * 32010157 =341550071728321;
and upbounds of ψ9 , ψ10 and ψ11:
ψ9 ≤ M9 = 4540612081 * 9081224161 = 41234
31613 57056 89041 (20 digits),
ψ10 ≤M10 = 22754930352733 *
68264791058197 = 155 33605 66073 14320 55410 02401 (28 digits),
ψ11 ≤M11 =
137716125329053 * 413148375987157 = 5689 71935 26942 02437 03269 72321 (29 digits)
In
2001, we [ZZX2001a]
lowered the upbounds of ψ10 and ψ11:
ψ10 ≤N’10 =
31265776261 * 62531552521 = 19 55097 53037 45565 03981 (22
digits),
ψ11 ≤N’11 = 60807114061 * 121614228121 = 73 95010
24079 41207 09381 (22 digits);
and obtained a 24-digit upbound for ψ12.
ψ12 ≤N12 = 399165290221
* 798330580441 = 3186 65857 83403 11511 67461 (24 digits)
In
2003, we [Zhang and Tang 2003] lowered the upbounds
of ψ9 , ψ10 and
ψ11:
ψ9 ≤ψ10 ≤ψ11 ≤ N9=N10=N11=
149491 * 747451 * 34233211 = 3825 12305 65464 13051 (19 digits).
Denote
by ψ’m (resp. ψ’’m) the
smallest K2-( resp. C3-) spsp to all the first m prime bases. (Recall that a K2-spsp is an spsp of the form: n = pq
with p, q primes and q-1 = 2(p-1); and that a C3-spsp
is an spsp and a Carmichael number of the form: n =
q1q2q3 with each prime
factor qi ≡3 mod 4.) In
2007, we [Zhang 2007] obtained the following values:
ψ’13 =
1287836182261 * 2575672364521 = 33170 44064 67988 73859 61981 (25 digits) ;
ψ’14 =
54786377365501 * 109572754731001 = 600 30942 89670 10580 03125 96501 (28 digits) ;
ψ’15 =
172157429516701 * 344314859033401=
5927 63610 75595 57326 34463 30101 (29
digits) ;
ψ’16 = ψ’17 = 531099297693901 * 1062198595387801 = 56413 29280 21909
22101 40875 01701 (30 digits);
ψ’18= ψ’19 = 27778299663977101 * 55556599327954201 = 1543 26786 44434
20616 87767 76407 51301 (34 digits);
ψ’20 > 1036. Note that ψ’12 = N12 =
3186 65857 83403 11511 67461 was found in [Zhang 2005].
Conjectures on ψm （9 ≤m ≤20）
2022-1-28