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-Lovasz (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), (N1/5 log16/5 N) pp. 1367-1379], who achieved a complexity of O for factoring (loglog N)3/5 a semiprime N = pq, we demonstrate that in the balanced p and q case, the ( N1/5 log13/5 N) complexity can be improved to O . (log log N)3/5-For factoring sums and differences of powers, i.e., numbers of the form N = an +/- bn, we improve Hittmeir's result [Math. Comp. 86 (2017), pp. ( ) 2947-2954] from O(N1/4 log3/2 N) to O N1/5 log13/5 N .- For the problem of finding r-power divisors, i.e., finding all integers p such that pr | N, Harvey and Hittmeir [Res. Number Theory 8 (2022)] recently directly applied Coppersmith's method and achieved a complexity of ( N1/4r log10+epsilon N) O r3 . By using faster LLL-type algorithm and sieving on small (N1/4r log7+3 epsilon N) primes, we improve their result to O (log logN-log 4r)r2+epsilon . The worst case running time for their algorithm occurs when N = prq with q = Theta(N1/2). By focusing on this case and employing our rank-3 lattice approach, we achieve a ( ) complexity of O r1/4N1/4r log5/2 N . In conclusion, we offer a new perspective on these problems, which we hope will provide further insights.

Publication:

MATHEMATICS OF COMPUTATION

http://dx.doi.org/10.1090/mcom/4188

Author:

YIMING GAO

School of Cyber Science and Technology, University of Science and Technology of China, Hefei, People’s Republic of China

Email address: qw1234567@mail.ustc.edu.cn

YANSONG FENG

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, People’s Republic of China

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, People’s Republic of China

Email address: fengyansong@amss.ac.cn

HONGGANG HU

School of Cyber Science and Technology, University of Science and Technology of China，Hefei, People’s Republic of China; and Hefei National Laboratory, Hefei, People’s Republic of China

Email address: hghu2005@ustc.edu.cn

YANBIN PAN

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, People’s Republic of China; and School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, People’s Republic of China

Email address: panyanbin@amss.ac.cn