An improved parallel block Lanczos algorithm over GF(2) for integer factorization

RSA algorithm is one of the most popular and secure public key cryptographic algorithms and has been widely used in many real-life applications. The security of the RSA algorithm lies in the difficulty of factoring large integers efficiently and the General Number Field Sieve (GNFS) algorithm is the most efficient algorithm for factoring integers greater than 110 digits at present. In this paper, targeted to speed up the factorization process of RSA, we discuss the current research about solving large and sparse linear systems over GF(2), which is one of the most time-consuming steps of the GNFS algorithm. With that, we propose an improved parallel block Lanczos (IBL) algorithm to reduce the communication cost of solving large and sparse linear systems over GF(2). More specifically, we firstly re-implement the parallel block Lanczos algorithm from the BSP paradigm to Open MPI. To further improve the performance, we then reorganize and redesign the algorithm to reduce the synchronization and communication costs during the outer product step. After this, we integrate the improved parallel block Lanczos algorithm with the GNFS algorithm. Finally, theoretical and experimental results demonstrate that the IBL algorithm greatly enhances the performance of GNFS compared with previous parallel block Lanczos (PBL) algorithm, in terms of both execution time and speedup.