Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An extension of a result about divisors in a residue class and its application to reducing integer factorization to computing Euler's totient

Author: Bartosz Źrałek
Journal: Math. Comp. 88 (2019), 1261-1272
MSC (2010): Primary 11Y16; Secondary 11Y05
Published electronically: August 1, 2018
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: According to a theorem of Coppersmith, Howgrave-Graham, and Nagaraj, relying on lattice basis reduction, the divisors of an integer $ n$ which lie in some fixed residue class modulo a given integer $ A$ can be computed efficiently if $ A$ is large enough. We extend their algorithm to the setting when the modulus is a product $ A\cdot B$, where $ A$ is given and the unknown $ 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 \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$ chosen values of $ \varphi $. This improves upon a previous recent result both in terms of the factor $ 72^{-\frac {1}{3}}$ and the number of values of $ \varphi $ needed.

In a more concrete setting, another algorithmic extension of the theorem of Coppersmith et al. may be worth noting. We can make use of the (unknown) smooth part of a shifted divisor $ d$ of $ n$ (or even several shifts of $ d$) to compute a suitably large modulus $ A$ and the corresponding residue class $ d\bmod A$ via Chinese remaindering.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 11Y05

Retrieve articles in all journals with MSC (2010): 11Y16, 11Y05

Additional Information

Bartosz Źrałek
Affiliation: Institute of Mathematics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland

Keywords: Euler's totient function, deterministic integer factoring
Received by editor(s): July 26, 2016
Received by editor(s) in revised form: September 23, 2017, and March 13, 2018
Published electronically: August 1, 2018
Additional Notes: The author was partially supported by MNiSW grant IP2011 064471
Article copyright: © Copyright 2018 American Mathematical Society