Lattice sieving

Last updated October 25, 2023

Lattice sieving is a technique for finding smooth values of a bivariate polynomial $f(a,b)$ over a large region. It is almost exclusively used in conjunction with the number field sieve. The original idea of the lattice sieve came from John Pollard.^[1]

The algorithm implicitly involves the ideal structure of the number field of the polynomial; it takes advantage of the theorem^{Which one?} that any prime ideal above some rational prime p can be written as $p\mathbb {Z} [\alpha ]+(u+v\alpha )\mathbb {Z} [\alpha ]$ . One then picks many prime numbers q of an appropriate size, usually just above the factor base limit, and proceeds by

For each q, list the prime ideals above q by factorising the polynomial f(a,b) over

GF(q)

For each of these prime ideals, which are called 'special

{\mathfrak {q}}

's, construct a reduced basis

\mathbf {x} ,\mathbf {y}

for the lattice L generated by

{\mathfrak {q}}

; set a two-dimensional array called the sieve region to zero.

For each prime ideal

{\mathfrak {p}}

in the factor base, construct a reduced basis

\mathbf {x} _{\mathfrak {p}},\mathbf {y} _{\mathfrak {p}}

for the sublattice of L generated by

{\mathfrak {pq}}

For each element of that sublattice lying within a sufficiently large sieve region, add

\log |{\mathfrak {p}}|

to that entry.

Read out all the entries in the sieve region with a large enough value

For the number field sieve application, it is necessary for two polynomials both to have smooth values; this is handled by running the inner loop over both polynomials, whilst the special-q can be taken from either side.

Treatments of the inmost loop

There are a number of clever approaches to implementing the inmost loop, since listing the elements of a lattice within a rectangular region efficiently is itself a non-trivial problem, and efficiently batching together updates to a sieve region in order to take advantage of cache structures is another non-trivial problem. The normal solution to the first is to have an ordering of the lattice points defined by couple of generators picked so that the decision rule which takes you from one lattice point to the next is straightforward; the normal solution to the second is to collect a series of lists of updates to sub-regions of the array smaller than the size of the level-2 cache, with the number of lists being roughly the number of lines in the L1 cache so that adding an entry to a list is generally a cache hit, and then applying the lists of updates one at a time, where each application will be a level-2 cache hit. For this to be efficient you need to be able to store a number of updates at least comparable to the size of the sieve array, so this can be quite profligate in memory usage.

Related Research Articles

In mathematics, a finite field or Galois field is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtraction and division are defined and satisfy certain basic rules. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

In mathematics, and more specifically in ring theory, an ideal of a ring is a special subset of its elements. Ideals generalize certain subsets of the integers, such as the even numbers or the multiples of 3. Addition and subtraction of even numbers preserves evenness, and multiplying an even number by any integer results in an even number; these closure and absorption properties are the defining properties of an ideal. An ideal can be used to construct a quotient ring in a way similar to how, in group theory, a normal subgroup can be used to construct a quotient group.

In commutative algebra, the prime spectrum of a ring R is the set of all prime ideals of R, and is usually denoted by $; in algebraic geometry it is simultaneously a topological space equipped with the sheaf of rings .$

In algebraic number theory, an algebraic integer is a complex number which is integral over the integers. That is, an algebraic integer is a complex root of some monic polynomial whose coefficients are integers. The set of all algebraic integers $A$ is closed under addition, subtraction and multiplication and therefore is a commutative subring of the complex numbers.

In mechanics and geometry, the 3D rotation group, often denoted SO(3), is the group of all rotations about the origin of three-dimensional Euclidean space $under the operation of composition.$

In mathematics, the adele ring of a global field is a central object of class field theory, a branch of algebraic number theory. It is the restricted product of all the completions of the global field and is an example of a self-dual topological ring.

In mathematics, the ring of integers of an algebraic number field $is the ring of all algebraic integers contained in . An algebraic integer is a root of a monic polynomial with integer coefficients: . This ring is often denoted by or . Since any integer belongs to and is an integral element of, the ring is always a subring of .$

In geometry and group theory, a lattice in the real coordinate space $is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be a subgroup of the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is a Delone set. More abstractly, a lattice can be described as a free abelian group of dimension which spans the vector space . For any basis of, the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as a regular tiling of a space by a primitive cell.$

In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number $p$ , then this root can be lifted to a unique root modulo any higher power of $p$ . More generally, if a polynomial factors modulo $p$ into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of $p$ .

In mathematics, the Noether normalization lemma is a result of commutative algebra, introduced by Emmy Noether in 1926. It states that for any field k, and any finitely generated commutative k-algebraA, there exist algebraically independent elements y₁, y₂, ..., y_d in A such that A is a finitely generated module over the polynomial ring S = k [y₁, y₂, ..., y_d]. The integer d is equal to the Krull dimension of the ring A; and if A is an integral domain, d is also the transcendence degree of the field of fractions of A over k.

In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

In commutative algebra, an element b of a commutative ring B is said to be integral overA, a subring of B, if there are n ≥ 1 and a_j in A such that

In algebraic geometry, the Nisnevich topology, sometimes called the completely decomposed topology, is a Grothendieck topology on the category of schemes which has been used in algebraic K-theory, A¹ homotopy theory, and the theory of motives. It was originally introduced by Yevsey Nisnevich, who was motivated by the theory of adeles.

In mathematics the Function Field Sieve is one of the most efficient algorithms to solve the Discrete Logarithm Problem (DLP) in a finite field. It has heuristic subexponential complexity. Leonard Adleman developed it in 1994 and then elaborated it together with M. D. Huang in 1999. Previous work includes the work of D. Coppersmith about the DLP in fields of characteristic two.

In cryptography, Learning with errors (LWE) is a mathematical problem that is widely used in cryptography to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear $-ary function over a finite ring from given samples some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.$

In cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the fast Fourier transform (FFT). SWIFFT is not the first hash function based on FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction algorithm. It can be shown that finding collisions in SWIFFT is at least as difficult as finding short vectors in cyclic/ideal lattices in the worst case. By giving a security reduction to the worst-case scenario of a difficult mathematical problem, SWIFFT gives a much stronger security guarantee than most other cryptographic hash functions.

In mathematics, an algebraic number field is an extension field $of the field of rational numbers such that the field extension has finite degree . Thus is a field that contains and has finite dimension when considered as a vector space over .$

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

Short integer solution (SIS) and ring-SIS problems are two average-case problems that are used in lattice-based cryptography constructions. Lattice-based cryptography began in 1996 from a seminal work by Miklós Ajtai who presented a family of one-way functions based on SIS problem. He showed that it is secure in an average case if the shortest vector problem $(where for some constant) is hard in a worst-case scenario.$

In algebraic number theory, the Dedekind–Kummer theorem describes how a prime ideal in a Dedekind domain factors over the domain's integral closure.

References

↑ Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.

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] Arjen K. Lenstra and H. W. Lenstra, Jr. (eds.). "The development of the number field sieve". Lecture Notes in Math. (1993) 1554. Springer-Verlag.

[1]