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 <i>N</i> 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 pr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-04-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/13/5/735 |
| _version_ | 1797537006812659712 |
|---|---|
| author | Rasyid Redha Mohd Tahir Muhammad Asyraf Asbullah Muhammad Rezal Kamel Ariffin Zahari Mahad |
| author_facet | Rasyid Redha Mohd Tahir Muhammad Asyraf Asbullah Muhammad Rezal Kamel Ariffin Zahari Mahad |
| author_sort | Rasyid Redha Mohd Tahir |
| collection | DOAJ |
| description | Fermat’s Factoring Algorithm (FFA) is an integer factorisation methods factoring the modulus <i>N</i> 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 <i>N</i> with unbalanced and balanced primes factor. The algorithm works for factoring a modulus with unbalanced and balanced primes. |
| first_indexed | 2024-03-10T12:08:57Z |
| format | Article |
| id | doaj.art-b8fb681bdcb34d2ab9d93e442f6ffbae |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-03-10T12:08:57Z |
| publishDate | 2021-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-b8fb681bdcb34d2ab9d93e442f6ffbae2023-11-21T16:24:44ZengMDPI AGSymmetry2073-89942021-04-0113573510.3390/sym13050735Determination of a Good Indicator for Estimated Prime Factor and Its Modification in Fermat’s Factoring AlgorithmRasyid Redha Mohd Tahir0Muhammad Asyraf Asbullah1Muhammad Rezal Kamel Ariffin2Zahari Mahad3Laboratory of Cryptography, Structure and Analysis, Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, MalaysiaLaboratory of Cryptography, Structure and Analysis, Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, MalaysiaLaboratory of Cryptography, Structure and Analysis, Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, MalaysiaLaboratory of Cryptography, Structure and Analysis, Institute for Mathematical Research (INSPEM), Universiti Putra Malaysia, Serdang 43400, MalaysiaFermat’s Factoring Algorithm (FFA) is an integer factorisation methods factoring the modulus <i>N</i> 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 <i>N</i> with unbalanced and balanced primes factor. The algorithm works for factoring a modulus with unbalanced and balanced primes.https://www.mdpi.com/2073-8994/13/5/735estimated prime factorinteger factorisation problemcontinued fractionFermat’s Factoring Algorithm |
| spellingShingle | Rasyid Redha Mohd Tahir Muhammad Asyraf Asbullah Muhammad Rezal Kamel Ariffin Zahari Mahad Determination of a Good Indicator for Estimated Prime Factor and Its Modification in Fermat’s Factoring Algorithm Symmetry estimated prime factor integer factorisation problem continued fraction 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 |
| topic | estimated prime factor integer factorisation problem continued fraction Fermat’s Factoring Algorithm |
| url | https://www.mdpi.com/2073-8994/13/5/735 |
| work_keys_str_mv | AT rasyidredhamohdtahir determinationofagoodindicatorforestimatedprimefactoranditsmodificationinfermatsfactoringalgorithm AT muhammadasyrafasbullah determinationofagoodindicatorforestimatedprimefactoranditsmodificationinfermatsfactoringalgorithm AT muhammadrezalkamelariffin determinationofagoodindicatorforestimatedprimefactoranditsmodificationinfermatsfactoringalgorithm AT zaharimahad determinationofagoodindicatorforestimatedprimefactoranditsmodificationinfermatsfactoringalgorithm |