1 Abstract: One of the most popular publickey cryptosystems RSA, relies on the fact that it is computationally difficult to factor a large integer into its component prime integers. The Number Field Sieve algorithm is the fastest known method for factoring large integers. The two most time consuming steps in NFS algorithm are Sieving and Linear algebra .In this paper, we present an implementation of Sieving step using a radically new system which was designed to solve computationally hard problems in algebra, number theory, geometry, called Magma. 1. INDEX TERMS: Factorization, Number Field Sieve, Sieving, Magma. 2. INTRODUCTION: Factoring a positive integer n means finding positive integers x and y such that the product of x and y equals to n, such that both x and y are greater than 1. Such x and y are called factors of n, and n = x. y is called factorization of n. Factorization of a composite number and prime factorization are the two main factorizations possible. Factorization of a composite number is not necessarily unique, but prime factorization of a number, written as a product of prime numbers is unique. Factoring a composite integer is believed to be a hard problem; this is evident from the fact that there is no fast and practical factoring algorithm, which can factor a large number. The security of one of the most popular public key cryptosystems,RSA relies on the supposed difficulty of factoring. This relation between factoring and cryptography is one of the main reasons why people are interested in evaluating the practical difficulty of the integer factorization problem and started to keep track of the largest numbers factored so far.RSA relies on the fact that it is computationally difficult to factor a large integer into its component prime integers. If an efficient algorithm is developed that can factor any arbitrarily large integer in a reasonable amount of time, the security value of the RSA system would be nullified. When keys are generated, efficient algorithms are used to generate two very large prime numbers and multiply them together. The person who generated the keys knows these two numbers, but everyone else knows only the product. The product contains enough information to encrypt a message to the person; the two primes allow the recipient to decrypt it. There is no known way to decrypt it without using the primes, but by factoring, we can extract the two prime factors from the product and break the encryption. At the time when RSA was invented, factoring integers started with as few as 80 decimal digits which was intractable; all known algorithms were either too slow or required the number to have a special form, this made, 256-bit keys relatively secure. The first major breakthrough was quadratic sieve, a relatively simple factoring algorithm which can factor numbers up to 100 digits and more. It's still the best known method for numbers under 110 digits or so; but for factoring large numbers, the Number Field Sieve is the fastest known alogorithm(NFS) so far. Factorization of large numbers using Number Field Sieve Sieving Step Sushma Gudavalli, Teja Valurupalli23. NUMBER FIELD SIEVE: The GNFS also has fundamental similarities to simpler and previously known algorithms. At its core, as with the continued fraction method and the quadratic sieve, its goal is to find a congruence of squares. If N, the number to be factored, is composed of two prime factors, each solution to x2 ≡ y2modN, has a 50% chance of producing a non-trivial factorization of N. Whereas previous algorithms seek a congruence of squares through rather elementary means, the GNFS uses the theory of algebraic rings to find a congruence of squares in a more efficient way. The algorithm consists of 5 main steps which are mutual dependent and can not be made in parallel, but some of the steps can be parallel internally. A. Polynomial selection: Selecting a usable polynomial is not difficult, but a good polynomial is hard to find. The yield of a polynomial refers to the number of smooth values it produces in its sieve region. There are two main factors which influence the yield of the polynomial, they are size and root properties. A polynomial is said to be good if it has a good yield i.e. has a good combination of size and root properties. A polynomial selection step consists of the following steps: i. Identify a large set of usable polynomials. ii. Using heuristics remove obviously bad polynomials from the set. iii. Do small sieving experiments on the remaining polynomials and choose the one with the best yield. B. Factor bases: The algorithm needs a well defined domain to work in, and this is specified with the factor bases. Factor base is a mathematical tool commonly used in integer factorization, more specifically algorithms involving extensive sieving of potential factors. There are mainly two factor bases: Rational Factor Base (RFB), Algebraic Factor Base (AFB). RFB: RFB consists of all the primes pi up to some bound and we also store pi mod m, so the rational factor base consists of pairs (p, p mod m) i.e. RFB = (p0, p0 mod m), (p1, p1 mod m) . . . . . . AFB: AFB consists of pairs (p, r) such that f(r) = 0 mod p i.e., AFB = (p0, r0),(p1, r1) . . . . The size of the algebraic factor base should be 2-3 times the size of the rational factor base. In general, an integer is said to be y-smooth if all of its prime divisors are less than or equal to y. C. Sieving: The purpose of sieving step is to find usable relations, i.e. elements (a, b) with the following properties i. gcd (a, b) = 1. ii. a + bm is smooth over the rational factor base iii. bdeg(f)f(a/b) is smooth over the algebraic factor base Finding elements with these properties can be done by various sieving methods like classical line sieving or faster lattice sieving. D. Linear algebra(Matrix step): From the sieving step we have a list of (a, b)’s which are RFB smooth and AFB smooth and we have to find a combination of elements from the relation set which has a product that is a square. For a number to be a square the elements in its factorization must have an even power and this property is what is used to find elements that are squares. This method involves solving a system of linear equations and this can be done by building a matrix. The matrix
View Full Document
Unlocking...