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.
Description
Master's thesis in Computer Science