Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm
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...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Multidisciplinary Digital Publishing Institute
2021
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/96655/ http://psasir.upm.edu.my/id/eprint/96655/1/ABSTRACT.pdf |
| _version_ | 1848862415808102400 |
|---|---|
| author | Mohd Tahir, Rasyid Redha Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal Mahad, Zahari |
| author_facet | Mohd Tahir, Rasyid Redha Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal Mahad, Zahari |
| author_sort | Mohd Tahir, Rasyid Redha |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T13:16:40Z |
| format | Article |
| id | upm-96655 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T13:16:40Z |
| publishDate | 2021 |
| publisher | Multidisciplinary Digital Publishing Institute |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-966552022-12-14T13:26:02Z http://psasir.upm.edu.my/id/eprint/96655/ Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm Mohd Tahir, Rasyid Redha Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal Mahad, Zahari 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. Multidisciplinary Digital Publishing Institute 2021 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/96655/1/ABSTRACT.pdf 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 https://www.mdpi.com/2073-8994/13/5/735 10.3390/sym13050735 |
| spellingShingle | Mohd Tahir, Rasyid Redha Asbullah, Muhammad Asyraf Kamel Ariffin, Muhammad Rezal Mahad, Zahari Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm |
| title | Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm |
| title_full | Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm |
| title_fullStr | Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm |
| title_full_unstemmed | Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm |
| title_short | Determination of a good indicator for estimated prime factor and its modification in Fermat’s Factoring Algorithm |
| title_sort | determination of a good indicator for estimated prime factor and its modification in fermat’s factoring algorithm |
| url | http://psasir.upm.edu.my/id/eprint/96655/ http://psasir.upm.edu.my/id/eprint/96655/ http://psasir.upm.edu.my/id/eprint/96655/ http://psasir.upm.edu.my/id/eprint/96655/1/ABSTRACT.pdf |