Comparative analysis of integer factorization algorithms

Year 2015, Volume: 3 Issue: 2, 22 - 33, 01.10.2015

G. Kimsanova R. Ismailova R. Sultanov

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 (