Speeding Up Fermat’s Factoring Method using Precomputation

Annals of Emerging Technologies in Computing

article

Bahig, Hatem M.¹ 

[1] Ain Shams University

关键词: Fermat’s Factoring Method;    Integer Factorization;    Precomputation;    Public-key Cryptosystem;    RSA;   

DOI  :  10.33166/AETiC.2022.02.004

学科分类：电子与电气工程

来源: International Association for Educators and Researchers (IAER)

【 摘 要 】

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 ∆= ? − ? ≤ ? ?.?? , 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%.

【 授权许可】

CC BY