Comparative analysis of integer factorization algorithms

G. Kimsanova; R. Ismailova; R. Sultanov

EN

Comparative analysis of integer factorization algorithms

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

References

References
[1] R. L. Rivest, A. Shamir, and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM 21.2 ,pp. 120-126, 1978.
[2] O. M. Rabin, “Digitalized signatures and public-key functions as intractable as factorization”, MIT Technical Report TR-212, 1979.
[3] P. Smith and M. J. J. Lennon, “LUC: A new public key system”, Tech. report, 1993.
[4] D. Whitfield and M. E. Hellman, "New directions in cryptography", Information Theory, IEEE Transactions on 22.6, pp. 644-654, 1976.
[5] T. ElGamal, “A public-key cryptosystem and a signature scheme based on discrete logarithms”, IEEE Transactions on Information Theory IT-31, pp.10–18, 1985.
[6] D. R. Stinson, “Cryptography: theory and practice”. CRC press, 1995.
[7] T. Okamoto and S. Uchiyama, “A new public-key cryptosystem as secure as factoring”, Lecture Notes in Computer Science 1403, pp. 308–318, 1998.
[8] D. Knuth, “The Art of Computer Programming”, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley. ISBN 0-201-89684-2. Section 4.5.4: Factoring into Primes, pp. 379_417, 1997.
[9] I. Kleiner, "Fermat: The founder of modern number theory." Mathematics Magazine, pp. 3-14, 2005.

[10] Mc. James, “Turning Euler`s Factoring Method into a Factoring Algorithm", in Bulletin of the London Mathematical Society
issue 28 (volume 4), pp. 351-355, 1996.
[11] C. Pomerance, ”The quadratic sieve factoring algorithm”, In Proc. of the EUROCRYPT 84 Workshop on Advances in Cryptology: theory and Application of Cryptographic Techniques. Springer-Verlag New York, pp. 169-182, 1985.
[12] A. K. Lenstra, H.W. Lenstra, M.S. Manasse and J.M. Pollard, “The number field sieve”, In Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing. ACM, New York, NY,pp. 564-572, 1990.
[13] H. Riesel, “ Prime numbers and computer methods for factorization” (2nd ed.), Birkhauser Verlag, Basel, Switzerland, Switzerland, 1994.
[14] H. C.Williams and J. O. Shallit, “Factoring Integers Before Computers, Mathematics of Computation 1943–1993: a half-century of computational mathematics” (Providence) (Walter Gautschi, ed.), American Mathematical Society, pp. 481–531, 1991.
[15] J. M. Pollard, "Monte Carlo methods for index computation (

Details

Primary Language

English

Subjects

-

Journal Section

-

Authors

G. Kimsanova This is me

R. Ismailova This is me

R. Sultanov This is me

Publication Date

October 1, 2015

Submission Date

October 1, 2015

Acceptance Date

-

Published in Issue

Year 2015 Volume: 3 Number: 2

IZ

https://izlik.org/JA57LE95ME

APA

Kimsanova, G., Ismailova, R., & Sultanov, R. (2015). Comparative analysis of integer factorization algorithms. MANAS Journal of Engineering, 3(2), 22-33. https://izlik.org/JA57LE95ME

AMA

1.Kimsanova G, Ismailova R, Sultanov R. Comparative analysis of integer factorization algorithms. MJEN. 2015;3(2):22-33. https://izlik.org/JA57LE95ME

Chicago

Kimsanova, G., R. Ismailova, and R. Sultanov. 2015. “Comparative Analysis of Integer Factorization Algorithms”. MANAS Journal of Engineering 3 (2): 22-33. https://izlik.org/JA57LE95ME.

EndNote

Kimsanova G, Ismailova R, Sultanov R (October 1, 2015) Comparative analysis of integer factorization algorithms. MANAS Journal of Engineering 3 2 22–33.

IEEE

[1]G. Kimsanova, R. Ismailova, and R. Sultanov, “Comparative analysis of integer factorization algorithms”, MJEN, vol. 3, no. 2, pp. 22–33, Oct. 2015, [Online]. Available: https://izlik.org/JA57LE95ME

ISNAD

Kimsanova, G. - Ismailova, R. - Sultanov, R. “Comparative Analysis of Integer Factorization Algorithms”. MANAS Journal of Engineering 3/2 (October 1, 2015): 22-33. https://izlik.org/JA57LE95ME.

JAMA

1.Kimsanova G, Ismailova R, Sultanov R. Comparative analysis of integer factorization algorithms. MJEN. 2015;3:22–33.

MLA

Kimsanova, G., et al. “Comparative Analysis of Integer Factorization Algorithms”. MANAS Journal of Engineering, vol. 3, no. 2, Oct. 2015, pp. 22-33, https://izlik.org/JA57LE95ME.

Vancouver

1.G. Kimsanova, R. Ismailova, R. Sultanov. Comparative analysis of integer factorization algorithms. MJEN [Internet]. 2015 Oct. 1;3(2):22-33. Available from: https://izlik.org/JA57LE95ME

Manas Journal of Engineering

16155

Comparative analysis of integer factorization algorithms

Abstract

Keywords

Abstract

References

Details

Primary Language

Subjects

Journal Section

Authors

Publication Date

Submission Date

Acceptance Date

Published in Issue

IZ

Cite