Quadratic Sieve integer factorization using Hadoop

Abstract

Integer factorization problem is one of the most important parts in the world of cryptography. The security of the widely-used public-key cryptographic algorithm, RSA [1], and the Blum Blum Shub cryptographic pseudorandom number generator [2] heavily depend on the presumed difficulty of factoring a number to its prime constituents. As the size of the number to be factored gets larger, the difficulty of the problem increases enormously. This fact has led to the development of many different algorithms to attack bigger number within polynomial time. However, there is no known efficient algorithm for very large numbers, to shake up the security of real-world cryptographic applications. The fastest factoring algorithms to factor general numers are General Number Field Sieve (GNFS) and Quadratic sieve (QS). While QS is regarded as the fastest one for integers less than 110 digits, GNFS is by far the fastest for very big numbers. As of December 2009, the biggest number factored is 768-bit, 232-digit number taken from RSA challange [6] by using GNFS algorithm over a period of two years. The success came after a long hard work and complex programming development. This shows the complexity and difficulty of the Integer factorization problem. As the size of the number to be factored increases, the data required to factor that number equally increases. Hadoop-MapReduce is a powerful tool for processing for such magnitude data in a reasonable time. Because of this advantage, the thesis investigates the possiblity of attacking the problem in a distributed fashion using MapReduce programming paradigm on Hadoop. A single quadratic sieve algorithm written in Java was used to test different composite numbers. The results were carefully analyzed, then the strength and limitations of the approach are thoroughly discussed.