An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler’s totient
Bartosz Źrałek · Mathematics of Computation · 2018
According to a theorem of Coppersmith, Howgrave-Graham, and Nagaraj, relying on lattice basis reduction, the divisors of an integer n n which lie in some fixed residue class modulo a given integer A A can be computed efficiently if A A is large enough. We extend their algorithm to the setting when the modulus is a product A ⋅ B A\cdot B , where A A is given and the unknown B B divides an integer whose prime factors are known. The resulting tool is applied in the context of reducing integer factorization to computing Euler’s totient function φ \varphi . Our reduction is deterministic, runs in at most exp ( ( 72 − 1 3 + o ( 1 ) ) ( ln n ) 1 3 ( ln ln n ) 2 3 ) \exp \left (\left (72^{-\frac {1}{3}}+o(1)\right ) (\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}\right ) time, and requires no more than ln 8 n \ln _8 n chosen values of φ \varphi . This improves upon a previous recent result both in terms of the factor