Algorithms for Carmichael numbers

Abstract

Our primary concern is the computational complexity of algorithms that find all Carmichael numbers less than some specified bound $B$. We have three related results. First, we show CARMICHAELS is in $\text{P}$, where only the run-time is conditioned on the ERH. Second, we state a heuristically optimal tabulation algorithm, which is the first asymptotic improvement to tabulation algorithms in the $50$ years since Swift first described the prime-by-prime approach. Third, we implemented a related algorithm that tabulated $100$ times further while only doing about $5$ times the work of the prior tabulation. We found $308,279,939$ Carmichael numbers less than $10^{24}$ and we provide some statistics on these numbers.