On factoring and power divisor problems via rank-3 lattices and the second vector

We propose a deterministic algorithm based on Coppersmith’s method that employs a rank-3 lattice to address factoring-related problems. An interesting aspect of our approach is that we utilize the second vector in the Lenstra–Lenstra–Lovász (LLL)-reduced basis to avoid trivial collisions in the Baby-step Giant-step method, rather than the shortest vector as is commonly used in the literature. Our results are as follows: - Compared to the result by Harvey and Hittmeir [Math. Comp. 91 (2022), pp. 1367–1379], who achieved a complexity of O ( N 1 / 5 log 16 / 5 ⁡ N ( log ⁡ log ⁡ N ) 3 / 5 ) O\left ( \frac {N^{1/5} \log ^{16/5} N}{(\log \log N)^{3/5}} \right ) for factoring a semiprime N = p q N = pq , we demonstrate that in the balanced p p and q q case, the complexity can be improved to O ( N 1 / 5 log 13 / 5 ⁡ N ( log ⁡ log ⁡ N ) 3 / 5 ) O\left ( \frac {N^{1/5} \log ^{13/5} N}{(\log \log N)^{3/5}} \right ) . - For factoring sums and differences of powers, i.e., numbers of the form