|
In mathematics, the general number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n is of the form Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
In computer science, efficiency is used to describe several desirable properties of an algorithm or other construct, besides clean design, functionality, etc. ...
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...
In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ...
for a constant c which depends on the complexity measure and on the variant of the algorithm (see Big O notation for an explanation of the o(1)). It is a generalization of the special number field sieve: while the latter can only factor numbers of a certain special form, the general number field sieve can factor any number (apart from prime powers, but this is a minor issue). When the term number field sieve (NFS) is used without qualification, it refers to the general number field sieve. Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...
The special number field sieve (SNFS) is a special-purpose integer factorization algorithm. ...
A prime power is a positive integer power of a prime. ...
The principle of the number field sieve (both special and general) can be understood as an extension of the simpler rational sieve. When using the rational sieve to factor a large number n, it is necessary to search for smooth numbers (i.e. numbers with small prime factors) of order n; the rarity of these causes the rational sieve to be impractical. The general number field sieve, on the other hand, only requires a search for smooth numbers of order n1/d, where d is some integer greater than one. Since larger numbers are far less likely to be smooth than smaller numbers, this is the key to the efficiency of the number field sieve. But in order to achieve this speed-up, the number field sieve has to perform computations and factorizations in number fields. This results in many rather complicated aspects of the algorithm, as compared to the simpler rational sieve. In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. ...
In number theory, a positive integer m is called B-smooth if all prime factors of m are such that . For example, 22335654 is 5-smooth since none of its prime factors are greater than 5. ...
In mathematics, an algebraic number field (or simply number field) is a finite field extension of the rational numbers Q. That is, it is a field which contains Q and has finite dimension when considered as a vector space over Q. The study of algebraic number fields, and these days...
Note that logn is the number of digits in the binary representation of n, that is the size of the input to the algorithm. The (worst-case) running time is therefore super-polynomial in the size of the input. It is an important open problem whether factorization can be done in reasonable time. In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
Method
We choose two irreducible polynomials f(x) and g(x) with a common root m mod n; these polynomials will be of order of m, while having small degrees d and e. An optimal strategy for choosing these polynomials is not known. One simple method is to pick a degree d for a polynomial and consider the expansion of n in basis m where m is of order n1/d. The point is to get the coefficients of f and g as small as possible. A better method was suggested by Murphy and Brent [1]. The best reported results [2] were achieved by the method of Thorsten Kleinjung, whose details have not been published. In mathematics, the adjective irreducible means that an object cannot be expressed as a product of at least two non-trivial factors in a given ring. ...
In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ...
Now, we consider the 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 too (but at least of order of m), and we have a better chance for them to be smooth at the same time. In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ...
Having enough such pairs, using Gaussian elimination, we can get products of certain r and of the corresponding s to be squares at the same time. We need a slightly stronger condition—that they are norms of squares in our number fields, but we can get that condition by this method too. 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" which can be determined (as a product of known factors in Z[r1])—it will typically be represented as an irrational algebraic number. Similarly, we get that the product of the factors a- r2*b is a square in Z[r2], with a "square root" which we can also compute. In mathematics, Gaussian elimination (not to be confused with Gauss–Jordan elimination), named after Carl Friedrich Gauss, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ...
In mathematics, the (field) norm is a mapping defined in field theory, to map elements of a larger field into a smaller one. ...
In mathematics, an algebraic number is any number that is a root of an algebraic equation, a non-zero polynomial with integer (or equivalently, rational) coefficients. ...
Since m is a root of both f and g mod n, there are homomorphisms from the rings Z[r1] and Z[r2] to the ring Z/nZ, which map r1 and r2 to m, and these homomorphisms will map each "square root" (typically not represented as a rational number) into its integer representative. Now the product of the factors a-m*b mod n can be obtained as a square in two ways—one for each homomorphism. Thus, we get two numbers x and y, with x2-y2 divisible by n and again with probability at least one half we get a factor of n by finding the greatest common divisor of n and x-y. In abstract algebra, a homomorphism is a structure-preserving map between two algebraic structures (such as groups, rings, or vector spaces). ...
In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers without remainder. ...
Implementations
References - ^ B. Murphy and R. P. Brent. "On quadratic polynomials for the number field sieve". Australian Computer Science Communications 20 (1998), pp. 199-213. [1]
|
Feeds |
Contact