Skip to Main content Skip to Navigation
Journal articles

Deterministic factoring with oracles

François Morain 1 Guénaël Renault 2 Benjamin Smith 1 
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : We revisit the problem of integer factorization with number-theoretic oracles, including a well-known problem: can we factor an integer $N$ unconditionally, in deterministic polynomial time, given the value of the Euler totient $ϕ(N)$? We show that this can be done, under certain size conditions on the prime factors of N. The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show for example that if $N$ is a squarefree integer with a prime factor $p > √ N$ , then we can recover p in deterministic polynomial time given $ϕ(N)$. We also shed some light on the analogous problems for Carmichael's function, and the order oracle that is used in Shor's quantum factoring algorithm.
Complete list of metadata
Contributor : François Morain Connect in order to contact the contributor
Submitted on : Thursday, August 12, 2021 - 5:37:54 PM
Last modification on : Friday, July 8, 2022 - 10:05:25 AM


Files produced by the author(s)



François Morain, Guénaël Renault, Benjamin Smith. Deterministic factoring with oracles. Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2021, ⟨10.1007/s00200-021-00521-8⟩. ⟨hal-01715832v2⟩



Record views


Files downloads