The parallel improved Lanczos method for integer factorization over finite fields for public key cryptosystems
Abstract
The integer factorization and discrete logarithm problems are of practical importance because of the widespread use of public key cryptosystems whose security depends on the presumed difficulty of solving these problems. Factoring integers and computing discrete logarithms often require solving large and sparse systems of linear equations over finite fields. In this paper, we propose an improved version of the Lanczos algorithm for solving the above problems effectively on parallel architectures. The algorithm is derived such that all inner products, matrix-vector multiplications and vector updates of a single iteration step are independent and communication time required for inner product can be overlapped efficiently with computation time of vector updates. Therefore, the cost of global communication on parallel distributed memory computers can be significantly reduced. The resulting algorithm maintains the favorable properties of the algorithm while not increasing computational costs. In this paper, a theoretical model of computation and communications phases is presented to allow us to give a quantitative analysis of the parallel performance. The model has been applied to estimate the parallel execution time for RSA130, RSA140 and RSA155, respectively.