2025/06/11 by Andrew Shallue, Shallue, Andrew, Jonathan Webster +1
Computer Science · Mathematics · #11Y16 #Advanced Combinatorial Mathematics #Analytic Number Theory Research #Coding theory and cryptography #FOS: Mathematics #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2506.09903
openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03
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 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 1024 and we provide some statistics on these numbers.