Ilya Volkovich (BC)

We consider the problem of deterministically factoring integers provided with oracle access to important number-theoretic functions such as Euler’s Totient function – phi(.) and Carmichael’s Lambda function – lambda(.).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(.), we can completely factor N in deterministic polynomial time.
2. There exists a deterministic polynomial-time algorithm that given oracle access to phi(.), 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.

This is a joint work with Nikhil Gupta and Alan Sikarov.