Comparative analysis of integer factorization algorithms

Authors : G KİMSANOVA, R ISMAİLOVA, R Sultanov

Pages : 22-33

View : 15 | Download : 13

Publication Date : 2015-10-01

Article Type : Research Paper

Abstract :Integer factorization problem, which is used as the basis in many public key cryptosystem, is generally thought to be hard problem even on a modern computers. In this work we implement 4 integer factorization algorithms using GMP library on c++ and compare the running time of these algorithms. Algorithms were used to factor numbers of different sizes, as well as for number with different distance between factors. Our results showed that for numbers up to 296 bits the Pollard rho algorithm is the fastest one, while Fermat algorithm is fast when distances between factors are small. Brent algorithms appeared to run slower for this rage of numbers, however it succeeded to factor numbers which Fermat algorithm fail to factor.
Keywords : Integer factorization, GMP, Trial division algorithm, Fermat algorithm, Pollard rho algorithm, Brent algorithm