Experimental Analysis of Integer Factorization Methods Using Lattices

Since 1991, Schnorr has proposed methods using lattices for solving the integer factorization problem whose hardness supports the security of the RSA cryptosystem. In 2022, Yan et al. proposed a modification of Schnorr’s lattices and reported numerical experiments by an optimization method using quantum computation. After that, Yamaguchi et al. reported that they succeeded in factoring RSA-type composite numbers of at most 55 bits based on Yan et al.’s modification, using classical annealing calculation. In this paper, we report experimental results of integer factorization methods using lattices in classical computing. Specifically, we analyze the structure of Schnorr’s lattices to select suitable parameters and apply existing lattice algorithms for finding smooth relations in the difference-of-squares method. We report the running time of integer factorization using lattices for RSA-type composite numbers of at most 90 bits and the success probability of finding a smooth relation from a lattice. We also discuss the time complexity of integer factorization methods using lattices based on experimental results.