Comparative analysis of integer factorization algorithms
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. Algor...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kyrgyz Turkish Manas University
2015-10-01
|
| Series: | MANAS: Journal of Engineering |
| Subjects: | |
| Online Access: | https://dergipark.org.tr/en/download/article-file/575956 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1694-7398 |