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

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

Lontar Komputer: Jurnal Ilmiah Teknologi Informasi
Vol 12 No 1 (2021): Vol. 12, No. 01 April 2021

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.