F-2: Factoring of Large Numbers using Number Field Sieve – Matrix Step 1 Abstract – The ability to conduct secure electronic transactions is becoming more and more important everyday. One of the most popular cryptosystems for securing electronic data is RSA and it relies on the fact that it is computationally difficult to factor a large number into its prime factors. If an algorithm that can achieve this in a reasonable amount of time is discovered, the value of the RSA cryptosystem is expected to decrease significantly. Number Field Sieve (NFS) is the fastest known algorithm to factor numbers larger than 110 digits and while the method still has many unexplored features that require further research, its development in the past few years has facilitated factoring of integers that were once considered to be infeasible to factor with today’s technology. In this project, we are implementing one of the most time consuming stages of NFS, the linear algebra step. Our project consists of the Block Wiedemann implementation in software using LiDIA and the hardware emulation of the mesh routing algorithm proposed by Lenstra et al that reduces the asymptotic complexity and implementation cost. Index Terms – Factorization, Number Field Sieve (NFS), Mesh Routing Algorithm. I. INTRODUCTION The General Number Field Sieve is the fastest known method for factoring integers larger than 110 digits. It is known to be the best algorithm to factor keys in the RSA public key cryptography system. GNFS was used in factoring a 512-bit number in 1999 as part of the RSA Challenge. It was estimated that had the RSA-129 challenge used the GNFS instead of the Multiple Polynomial Quadratic Sieve, it would have taken a quarter of the time. Special Number Field Sieve (SNFS) is a specialized form of GNFS and is asymptotically faster than GNFS for factoring integers in the form re ± s with r, e, s ε Z and e > 0. This made SNFS the best method to factor the 155-bit ninth Fermat number and the Mersenne Primes. GNFS is also an academically interesting subject since the algorithm uses ideas and results from diverse fields of mathematics and computer science. Algebraic number theory, graph theory, finite fields, linear algebra, and real and complex analysis all play vital roles in GNFS. Our goal is to implement the linear algebra step which is one of the four main steps of GNFS. We will primarily use the LiDIA C++ library for computational number theory which provides a collection of optimized implementations of time intensive algorithms. A hardware emulation using Java will also be presented that uses the Mesh Routing algorithm proposed by Lenstra et al and implemented by Kris Gaj et al. II. GENERAL INFORMATION ON NUMBER FIELD SIEVE A. Definition Number field sieve is a fast factorization method developed by Pollard and it uses steps to factor an integer n and for General Number Field Sieve (GNFS) that can be applied to any odd positive number: The space complexity in General Number Field Sieve scales with the square root of the time complexity and it is a generalization of the special number field sieve which can only factor numbers of a certain special form. Number Field Sieve can be thought of as an extension of the rational sieve where smooth numbers of order n are sought for, rarity of which makes the algorithm impractical. An integer is called B-smooth if all of its prime factors are less than B. The General Number Field Sieve requires searching for smooth numbers of order n1/d where d is an integer greater than 1. Since small numbers are much more likely to be smooth than large numbers, GNFS is considered to be a more efficient algorithm than rational sieve. However, in order to achieve its higher performance, GNFS has to perform operations in number fields which causes increased complexity. B. Methodolgy The basic methodology to find the factors of an integer n is to find two numbers x and y such that: x2 ≡ y2 (mod n) => x2 – y2 ≡ 0 (mod n) => (x-y).(x+y) ≡ 0 (mod n) One of the factors of n can then be found via gcd(x-y, n). The algorithm starts with choosing two irreducible polynomials f(x) and g(x) with a common root m mod n. These polynomials have small degrees d and e and of Factoring of Large Numbers using Number Field Sieve Matrix Step Chandana Anand, Arman Gungor, and Kimberly A. Thomas ECE 646 Fall 2006F-2: Factoring of Large Numbers using Number Field Sieve – Matrix Step 2 order m. While the best technique to choose these polynomials hasn’t been proven, it is usually done by starting with a random degree d for a polynomial and considering the expansion of n in base m where m is of order n1/d. The second step is to consider number field rings Z[r1] and Z[r2], where r1 and r2 are roots of the polynomials f and g, and look for values a and b such that r = bd·f(a/b) and s = be·g(a/b) are smooth relative to the chosen basis of primes. If a and b are small, then r and s will be as well and we have a better chance for them to be smooth at the same time. Once enough such pairs are obtained, Gaussian elimination is used to get products of r and the corresponding s to be squares at the same time. Each r is a norm of a- r1*b and hence we get that the product of the corresponding factors a- r1*b is a square in Z[r1], with a square root that can be determined. The product of the factors a- r2*b is a square in Z[r2], with a square root which can also computed. Each relation will yield a sparse D-dimensional bit vector representing the exponent of its factors modulo 2 where D ≈ π (Br)+π(Ba) where π(y) = # of primes less than y After finding more than D relations, in the matrix step, one or more linear dependencies modulo 2 among the corresponding D dimensional bit vectors are searched. For each dependency, there is 50% chance that a factor of N is found in the last step, square root step. We end up with two numbers x and y, with x2-y2 divisible by n and again with at least 50% probability we get a factor of n by finding the gcd of n and x-y as described above. Four important main steps of the algorithm are polynomial selection, sieving, matrix step and the square root step. We have implemented the matrix step in our project, which is one of the two most complicated and expensive steps with sieving. III. SOFTWARE IMPLEMENTATIONS OF BLOCK WIEDEMANN ALGORITHM A. The Block Wiedemann Algorithm A primary difficulty in implementation of the Matrix step
View Full Document
Unlocking...