A Practical Analysis of the Fermat Factorization and Pollard Rho Method for Factoring Integers

Aminudin Aminudin; Eko Budi Cahyono

doi:10.24843/LKJITI.2021.v12.i01.p04

Aminudin Aminudin Universitas Muhammadiyah Malang
Eko Budi Cahyono Department of Informatic, University of Muhammadiyah Malang Tlogomas Street 246 Malang, Indonesia

DOI: https://doi.org/10.24843/LKJITI.2021.v12.i01.p04

Abstract

The development of public-key cryptography generation using the factoring method is very important in practical cryptography applications. In cryptographic applications, the urgency of factoring is very risky because factoring can crack public and private keys, even though the strength in cryptographic algorithms is determined mainly by the key strength generated by the algorithm. However, solving the composite number to find the prime factors is still very rarely done. Therefore, this study will compare the Fermat factorization algorithm and Pollard rho by finding the key generator public key algorithm's prime factor value. Based on the series of test and analysis factoring integer algorithm using Fermat's Factorization and Pollards' Rho methods, it could be concluded that both methods could be used to factorize the public key which specifically aimed to identify the prime factors. During the public key factorizing process within 16 bytes – 64 bytes, Pollards' Rho's average duration was significantly faster than Fermat's Factorization.

Downloads

Download data is not yet available.

References

[1] A. Aminudin, A. F. Helmi, and S. Arifianto, “Analisa Kombinasi Algoritma Merkle-Hellman Knapscak dan Logaritma Diskrit pada Aplikasi Chat,” Jurnal Teknologi Informasi dan Ilmu Komputer, vol. 5, no. 3, pp. 325–334, 2018.
[2] P. P. Thwe, M. Htet, Y. C. City, and I. Technology, "Extended Pollard's Rho Factorization Algorithm For Finding Factors In Composite Number," Journal of Science, Engineering and Education, pp. 232–235, 2020. doi: 10.13140/RG.2.2.34889.16485
[3] A. Aminudin, G. P. Aditya, and S. Arifianto, "RSA algorithm using key generator ESRKGS to encrypt chat messages with TCP/IP protocol," Jurnal Teknologi dan Sistem Komputer, vol. 8, no. 2, pp. 113–120, 2020, doi: 10.14710/jtsiskom.8.2.2020.113-120.
[4] K. Chiewchanchairat, P. Bumroongsri, and S. Kheawhom, "Improving Fermat factorization algorithm by dividing modulus into three forms," KKU Engineering Journal, vol. 40, no. March, pp. 131–138, 2016, doi: 10.14456/kkuenj.2016.127.
[5] C. L. Duta, L. Gheorghe, and N. Tapus, "Framework for evaluation and comparison of integer factorization algorithms," Proceeding 2016 SAI Computing Conference, pp. 1047–1053, 2016, doi: 10.1109/SAI.2016.7556107.
[6] K. Somsuk, "The new integer factorization algorithm based on Fermat's Factorization Algorithm and Euler's theorem," International Journal of Electrical and Computer Engineering, vol. 10, no. 2, pp. 1469–1476, 2020, doi: 10.11591/ijece.v10i2.pp1469-1476.
[7] P. Chinniah and A. Ramalingam, "An Integer Factorization Method Equivalent to Fermat Factorization," International Journal of Mathematics And its Applications, vol. 6, no. 2, pp. 107–111, 2018.
[8] J. LI, "Algorithm Design and Implementation for a Mathematical Model of Factoring Integers," IOSR Journal of Mathematics, vol. 13, no. 01, pp. 37–41, 2017, doi: 10.9790/5728-1301063741.
[9] S. Sarnaik, R. Bhakkad, and C. Desai, "Comparative study on Integer Factorization algorithm-Pollard's RHO and Pollard's P-1," in 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom), 2015, pp. 677–679.