MFFV3: An Improved Integer Factorization Algorithm to Increase Computation Speed

摘要

RSA, a public key cryptosystem, was proposed to protect the information in the insecure channel. The security of RSA relies on the difficulty of factoring the modulus which is the product of two large primes. We proposed Modified Fermat Factorization Version 2 (MFFV2) modified from Modified Fermat Factorization (MFF) to break RSA. The key of MFFV2 is to decrease the number of times of MFF for computing an integer's square root. However, MFFV2 is still time-consuming to some extent due to computation time of the subtraction of two integers for all iterations. Thus, this paper aims to propose Modified Fermat Factorization Version 3 (MFFV3) to increase the computation speed when compared with MFFV2. For MFFV3, we can ignore computing the difference between two integers when we know that the subtraction's result is certainly not a perfect square. Hence, we develop the Difference's Least Significant Digit Table (DLSDT), the information table used to analyze the least significant digit of the subtraction's result. Experimental results show that the computation time of MFFV3 for factoring the modulus is substantially reduced in comparison to MFF and MFFV2 respectively.