Factor base

Last updated March 31, 2019

In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.

In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations.

Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the prototypical example of a sieve is the sieve of Eratosthenes, or the more general Legendre sieve. The direct attack on prime numbers using these methods soon reaches apparently insuperable obstacles, in the way of the accumulation of error terms. In one of the major strands of number theory in the twentieth century, ways were found of avoiding some of the difficulties of a frontal attack with a naive idea of what sieving should be.

Usage in factoring algorithms

A factor base is a relatively small set of distinct prime numbers P, sometimes together with -1.^[1] Say we want to factorize an integer n. We generate, in some way, a large number of integer pairs (x, y) for which $x\neq \pm y$ , $x^{2}\equiv y^{2}{\pmod {n}}$ , and $x^{2}{\pmod {n}}{\text{ and }}y^{2}{\pmod {n}}$ can be completely factorized over the chosen factor base—that is, all their prime factors are in P.

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics. The language of set theory can be used to define nearly all mathematical objects.

Prime number Integer greater than 1 that has no positive integer divisors other than itself and 1

A prime number is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 6 is composite because it is the product of two numbers that are both smaller than 6. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In practice, several integers x are found such that $x^{2}{\pmod {n}}$ has all of its prime factors in the pre-chosen factor base. We represent each $x^{2}{\pmod {n}}$ expression as a vector of a matrix with integer entries being the exponents of factors in the factor base. Linear combinations of the rows corresponds to multiplication of these expressions. A linear dependence relation mod 2 among the rows leads to a desired congruence $x^{2}\equiv y^{2}{\pmod {n}}$ .^[2] This essentially reformulates the problem into a system of linear equations, which can be solved using numerous methods such as Gaussian elimination; in practice advanced methods like the block Lanczos algorithm are used, that take advantage of certain properties of the system.

A vector space is a collection of objects called vectors, which may be added together and multiplied ("scaled") by numbers, called scalars. Scalars are often taken to be real numbers, but there are also vector spaces with scalar multiplication by complex numbers, rational numbers, or generally any field. The operations of vector addition and scalar multiplication must satisfy certain requirements, called axioms, listed below.

Matrix (mathematics) Two-dimensional array of numbers with specific operations

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. For example, the dimensions of the matrix below are 2 × 3, because there are two rows and three columns:

In mathematics, a system of linear equations is a collection of two or more linear equations involving the same set of variables. For example,

This congruence may generate the trivial $\textstyle n=1\cdot n$ ; in this case we try to find another suitable congruence. If repeated attempts to factor fail we can try again using a different factor base.

Algorithms

Factor bases are used in, for example, Dixon's factorization, the quadratic sieve, and the number field sieve. The difference between these algorithms is essentially the methods used to generate (x, y) candidates. Factor bases are also used in the Index calculus algorithm for computing discrete logarithms.^[3]

In number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run-time bound comes with a rigorous proof that does not rely on conjectures about the smoothness properties of the values taken by polynomial.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than $10100$ . Heuristically, its complexity for factoring an integer $n$ (consisting of $⌊log 2 n ⌋ + 1$ bits) is of the form

Related Research Articles

The Chinese remainder theorem is a theorem of number theory, which states that if one knows the remainders of the Euclidean division of an integer $n$ by several integers, then one can determine uniquely the remainder of the division of $n$ by the product of these integers, under the condition that the divisors are pairwise coprime.

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these integers are further restricted to prime numbers, the process is called prime factorization.

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus. The modern approach to modular arithmetic was developed by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae, published in 1801.

RSA (Rivest–Shamir–Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public and it is different from the decryption key which is kept secret (private). In RSA, this asymmetry is based on the practical difficulty of the factorization of the product of two large prime numbers, the "factoring problem". The acronym RSA is made of the initial letters of the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who first publicly described the algorithm in 1978. Clifford Cocks, an English mathematician working for the British intelligence agency Government Communications Headquarters (GCHQ), had developed an equivalent system in 1973, but this was not declassified until 1997.

Fermat's little theorem states that if $p$ is a prime number, then for any integer $a$ , the number $a p - a$ is an integer multiple of $p$ . In the notation of modular arithmetic, this is expressed as

In the mathematics of the real numbers, the logarithm log_ba is a number x such that b^x = a, for given numbers a and b. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm log_ba is an integer k such that b^k = a. In number theory, the more commonly used term is index: we can write x = ind_ra for r^x ≡ a if r is a primitive root of m and gcd(a,m)=1.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might be called compositeness tests instead of primality tests.

In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that:

In computational number theory, the Lucas test is a primality test for a natural number n; it requires that the prime factors of n − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that n is prime.

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proven to be as hard as integer factorization, which is not currently known to be true of the RSA problem. It has the disadvantage that each output of the Rabin function can be generated by any of four possible inputs; if each output is a ciphertext, extra complexity is required on decryption to identify which of the four possible inputs was the true plaintext.

In number theory, a congruence of squares is a congruence commonly used in integer factorization algorithms.

In number theory, a branch of mathematics, the special number field sieve (SNFS) is a special-purpose integer factorization algorithm. The general number field sieve (GNFS) was derived from it.

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. It has been largely superseded by the Baillie-PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi pseudoprime test.

In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in $where is a prime, index calculus lead to a family of algorithms adapted to finite fields and to some families of elliptic curves. The algorithm collects relations among the discrete logarithms of small primes, computes them by a linear algebra procedure and finally expresses the desired discrete logarithm with respect to the discrete logarithms of small primes.$

In mathematics, the rational sieve is a general algorithm for factoring integers into prime factors. It is a special case of the general number field sieve. While it is less efficient than the general algorithm, it is conceptually simpler. It serves as a helpful first step in understanding how the general number field sieve works.

In mathematics, in particular the area of number theory, a modular multiplicative inverse of an integer $a$ is an integer $x$ such that the product $ax$ is congruent to 1 with respect to the modulus $m$ . In the standard notation of modular arithmetic this congruence is written as

In mathematics elliptic curve primality testing techniques, or elliptic curve primality proving (ECPP), are among the quickest and most widely used methods in primality proving. It is an idea put forward by Shafi Goldwasser and Joe Kilian in 1986 and turned into an algorithm by A. O. L. Atkin the same year. The algorithm was altered and improved by several collaborators subsequently, and notably by Atkin and François Morain, in 1993. The concept of using elliptic curves in factorization had been developed by H. W. Lenstra in 1985, and the implications for its use in primality testing followed quickly.

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

References

↑ Koblitz, Neal (1987), A Course in Number Theory and Cryptography, Springer-Verlag, p. 133, ISBN 0-387-96576-9
↑ Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, p. 185, ISBN 978-0-13-186239-5
↑ Stinson, Douglas R. (1995), Cryptography / Theory and Practice, CRC Press, p. 171, ISBN 0-8493-8521-0

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Koblitz, Neal (1987), A Course in Number Theory and Cryptography, Springer-Verlag, p. 133, ISBN 0-387-96576-9

[2] Trappe, Wade; Washington, Lawrence C. (2006), Introduction to Cryptography with Coding Theory (2nd ed.), Prentice-Hall, p. 185, ISBN 978-0-13-186239-5

[3] Stinson, Douglas R. (1995), Cryptography / Theory and Practice, CRC Press, p. 171, ISBN 0-8493-8521-0

Factor base

Contents

Usage in factoring algorithms

Algorithms

Related Research Articles

References