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!
|
| _version_ | 1832542963768492032 |
|---|---|
| author | G. Kimsanova R. Ismailova R. Sultanov |
| author_facet | G. Kimsanova R. Ismailova R. Sultanov |
| author_sort | G. Kimsanova |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-7bb70f27b7824b029e7db13ef26ea012 |
| institution | Kabale University |
| issn | 1694-7398 |
| language | English |
| publishDate | 2015-10-01 |
| publisher | Kyrgyz Turkish Manas University |
| record_format | Article |
| series | MANAS: Journal of Engineering |
| spelling | doaj-art-7bb70f27b7824b029e7db13ef26ea0122025-02-03T12:02:43ZengKyrgyz Turkish Manas UniversityMANAS: Journal of Engineering1694-73982015-10-013222331437Comparative analysis of integer factorization algorithmsG. KimsanovaR. IsmailovaR. SultanovInteger 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.https://dergipark.org.tr/en/download/article-file/575956integer factorizationgmptrial division algorithmfermat algorithmpollard rho algorithmbrent algorithm |
| spellingShingle | G. Kimsanova R. Ismailova R. Sultanov Comparative analysis of integer factorization algorithms MANAS: Journal of Engineering integer factorization gmp trial division algorithm fermat algorithm pollard rho algorithm brent algorithm |
| title | Comparative analysis of integer factorization algorithms |
| title_full | Comparative analysis of integer factorization algorithms |
| title_fullStr | Comparative analysis of integer factorization algorithms |
| title_full_unstemmed | Comparative analysis of integer factorization algorithms |
| title_short | Comparative analysis of integer factorization algorithms |
| title_sort | comparative analysis of integer factorization algorithms |
| topic | integer factorization gmp trial division algorithm fermat algorithm pollard rho algorithm brent algorithm |
| url | https://dergipark.org.tr/en/download/article-file/575956 |
| work_keys_str_mv | AT gkimsanova comparativeanalysisofintegerfactorizationalgorithms AT rismailova comparativeanalysisofintegerfactorizationalgorithms AT rsultanov comparativeanalysisofintegerfactorizationalgorithms |