Title
On Carmichael numbers with 3 factors and the strong pseudoprime test
Author
Warren D. Smith
Abstract
The well known ``strong pseudoprime test'' has its highest probability
of error ($\approx 1/4$) when the numbers being tested are certain Carmichael
numbers with 3 prime factors. We present a nonrigorous plausibility
argument that the count $C_3(x)$ of 3-factor
Carmichaels up to
$x$, is asymptotically
$C_3(x) \asympt K x^{1/3} ( \ln x )^{-3}$
where $K \approx 559 \pm 110$ is an absolute constant given by
\BE \label{Kdef1}
K = 3^3 \sum_{1 \le a** 1/8$ in the strong pseudoprime test
are certain numbers with only 2 prime factors and certain prime
powers. However
if these cases are somehow known to apply,
then we show how to improve the
strong pseudoprime test so that its probability of error on $N$
is $O ( 1/\sqrt{\ln N} )$.
Keywords
Carmichael numbers, Fermat test, pseudoprimes
**