Paper 2024/1722
Revisiting Fermat's Factorization Method
Abstract
This paper addresses the problem of factoring composite numbers by introducing a novel approach to represent their prime divisors. We develop a method to efficiently identify smaller divisors based on the difference between the primes involved in forming the composite number. Building on these insights, we propose an algorithm that significantly reduces the computational complexity of factoring, requiring half as many iterations as traditional quadratic residue-based methods. The presented algorithm offers a more efficient solution for factoring composite numbers, with potential applications in fields such as cryptography and computational number theory.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- RSA
- Contact author(s)
-
gkuldeep @ ece au dk
rhj @ ece au dk - History
- 2024-10-25: approved
- 2024-10-21: received
- See all versions
- Short URL
- https://ia.cr/2024/1722
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1722,
author = {Gajraj Kuldeep and Rune Hylsberg Jacobsen},
title = {Revisiting Fermat's Factorization Method},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1722},
year = {2024},
url = {https://eprint.iacr.org/2024/1722}
}
