Paper #4

Speeding Up Fermat’s Factoring Method using Precomputation

Hatem M. Bahig

Abstract: The security of many public-key cryptosystems and protocols relies on the difficulty of factoring a large positive integer n into prime factors. The Fermat factoring method is a core of some modern and important factorization methods, such as the quadratic sieve and number field sieve methods. It factors a composite integer n=pq in polynomial time if the difference between the prime factors is equal to ?=p-q=n^(0.25) , where p>q. The execution time of the Fermat factoring method increases rapidly as ? increases. One of the improvements to the Fermat factoring method is based on studying the possible values of (n mod 20). In this paper, we introduce an efficient algorithm to factorize a large integer based on the possible values of (n mod 20) and a precomputation strategy. The experimental results, on different sizes of n and ?, demonstrate that our proposed algorithm is faster than the previous improvements of the Fermat factoring method by at least 48%.

Keywords: Fermat’s Factoring Method; Integer Factorization; Precomputation; Public-key Cryptosystem; RSA.