Annals of Emerging Technologies in Computing | |
Speeding Up Fermat’s Factoring Method using Precomputation | |
article | |
Bahig, Hatem M.1  | |
[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
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202306300002709ZK.pdf | 802KB | download |