Factoring Integers and Computing Discrete Logarithms via Diophantine Approximation

Abstract

Let N be an integer with at least two distinct prime factors. We reduce the problem of factoring N to the task of finding random integer solutions (e ₁, ..., e _t) ∈ ℤ^t of the inequalities

$$ \begin{gathered} \left| {\sum\limits_{i = 1}^t {e_i \log p_i - \log N} } \right| \leqslant N^{ - c} and \hfill \\ \sum\limits_{i = 1}^t {\left| {e_i \log p_i } \right| \leqslant \left( {2c - 1} \right)\log N + o\left( {\log p_t } \right)} , \hfill \\ \end{gathered} $$

where c > 1 is fixed and p ₁, ..., p _t are the first t primes. We show, under the assumption that the smooth integers distribute “uniformly”, that there are N ^c+o(1) many solutions (e ₁, ..., e _t) if c > 1 and if ε: = c − 1 − (2c − 1)log log N / log p _t > 0. We associate with the primes p ₁, . . ., p _t a lattice L ⊂ ℝ^t+1 of dimension t and we associate with N a point N ∈ ℝ^t+1. We reduce the problem of factoring N to the task of finding random lattice vectors z that are sufficiently close to N in both the ∞-norm and the 1-norm. The dimension t of the lattice L is polynomial in log N. For N ≈ 2⁵¹² it is about 6300. We also reduce the problem of computing, for a prime N, discrete logarithms of the units in ℤ_/Nℤ to a similar diophantine approximation problem.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.