The parallel improved Lanczos method for integer factorization overfinite fields for public key cryptosystems

摘要

The integer factorization and discrete logarithm problems are ofpractical importance because of the widespread use of public keycryptosystems whose security depends on the presumed difficulty ofsolving these problems. Factoring integers and computing discretelogarithms often require solving large and sparse systems of linearequations over finite fields. In this paper, we propose an improvedversion of the Lanczos algorithm for solving the above problemseffectively on parallel architectures. The algorithm is derived suchthat all inner products, matrix-vector multiplications and vectorupdates of a single iteration step are independent and communicationtime required for inner product can be overlapped efficiently withcomputation time of vector updates. Therefore, the cost of globalcommunication on parallel distributed memory computers can besignificantly reduced. The resulting algorithm maintains the favorableproperties of the algorithm while not increasing computational costs. Inthis paper, a theoretical model of computation and communications phasesis presented to allow us to give a quantitative analysis of the parallelperformance. The model has been applied to estimate the parallelexecution time for RSA130, RSA140 and RSA155, respectively