A Computational Perspective on Carmichael Numbers

Abstract: We consider the problem of deterministically factoring integers provided with oracle access to important number-theoretic functions such as Euler's Totient function - $\Phi(\cdot)$ and Carmichael's Lambda function - $\Lambda(\cdot)$. We focus on Carmichael numbers - also known as Fermat pseudoprimes. In particular, we obtain the following results:

1. Let $N$ be a `simple' Carmichael number with three prime factors (also known as simple $C_3$-numbers). Then, given oracle access to $\lambda(\cdot)$, we can completely factor $N$ in deterministic polynomial time.

2. There exists a deterministic polynomial-time algorithm that given oracle access to $\Phi(\cdot)$, completely factors simple $C_3$-numbers, satisfying some `size' bounds. Although in this case our methods do not provide a theoretical guarantee for all such numbers due to the required size bounds, we show experimentally that our algorithm can factor more than 99\% of all simple $C_3$-numbers up to $10^{13}$.

Our techniques extend the work of Morain, Renault, and Smith (Applicable Algebra in Engineering, Communication, and Computation, 2023), at the core of which sits the Coppersmith's method that provides an efficient way to find bounded roots of a bivariate polynomial over the integers. We combine these techniques with a new upper bound on $\gcd(N-1, \Phi(N))$ for $C_3$-numbers, which could be of an independent interest.

computational complexitynumber theory

Audience: researchers in the topic

Boston University Number Theory Seminar