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.
Integer factorization GMP Trial division algorithm Fermat algorithm Pollard rho algorithm Brent algorithm
Diğer ID | JA58YZ46JP |
---|---|
Bölüm | Araştırma Makalesi |
Yazarlar | |
Yayımlanma Tarihi | 1 Ekim 2015 |
Yayımlandığı Sayı | Yıl 2015 Cilt: 3 Sayı: 2 |
Manas Journal of Engineering