UPM Institutional Repository

Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm


Citation

Mohd Tahir, Rasyid Redha and Asbullah, Muhammad Asyraf and Kamel Ariffin, Muhammad Rezal and Mahad, Zahari (2021) Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm. Symmetry-Basel, 13 (5). art. no. 735. pp. 1-22. ISSN 2073-8994

Abstract

Fermat’s Factoring Algorithm (FFA) is an integer factorisation methods factoring the modulus N using exhaustive search. The appearance of the Estimated Prime Factor (EPF) method reduces the cost of FFA’s loop count. However, the EPF does not work for balanced primes. This paper proposed the modified Fermat’s Factoring Algorithm 1-Estimated Prime Factor (mFFA1-EPF) that improves the EPF method. The algorithm works for factoring a modulus with unbalanced and balanced primes, respectively. The main results of mFFA1-EPF focused on three criteria: (i) the approach to select good candidates from a list of convergent continued fraction, (ii) the establishment of new potential initial values based on EPF, and (iii) the application of the above modification upon FFA. The resulting study shows the significant improvement that reduces the loop count of FFA1 via (improved) EPF compared to existing methods. The proposed algorithm can be executed without failure and caters for both the modulus N with unbalanced and balanced primes factor. The algorithm works for factoring a modulus with unbalanced and balanced primes.


Download File

[img] Text (Abstract)
ABSTRACT.pdf

Download (181kB)
Official URL or Download Paper: https://www.mdpi.com/2073-8994/13/5/735

Additional Metadata

Item Type: Article
Divisions: Faculty of Science
Institute for Mathematical Research
Centre of Foundation Studies for Agricultural Science
DOI Number: https://doi.org/10.3390/sym13050735
Publisher: Multidisciplinary Digital Publishing Institute
Keywords: Estimated prime factor; Integer factorisation problem; Continued fraction; Fermat’s Factoring Algorithm
Depositing User: Ms. Nuraida Ibrahim
Date Deposited: 14 Dec 2022 13:26
Last Modified: 14 Dec 2022 13:26
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.3390/sym13050735
URI: http://psasir.upm.edu.my/id/eprint/96655
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item