**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Special number field sieve

Summary

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 special number field sieve is efficient for integers of the form re ± s, where r and s are small (for instance Mersenne numbers).
Heuristically, its complexity for factoring an integer is of the form:
in O and L-notations.
The SNFS has been used extensively by NFSNet (a volunteer distributed computing effort), NFS@Home and others to factorise numbers of the Cunningham project; for some time the records for integer factorization have been numbers factored by SNFS.
The SNFS is based on an idea similar to the much simpler rational sieve; in particular, readers may find it helpful to read about the rational sieve first, before tackling the SNFS.
The SNFS works as follows. Let n be the integer we want to factor. As in the rational sieve, the SNFS can be broken into two steps:
First, find a large number of multiplicative relations among a factor base of elements of Z/nZ, such that the number of multiplicative relations is larger than the number of elements in the factor base.
Second, multiply together subsets of these relations in such a way that all the exponents are even, resulting in congruences of the form a2≡b2 (mod n). These in turn immediately lead to factorizations of n: n=gcd(a+b,n)×gcd(a-b,n). If done right, it is almost certain that at least one such factorization will be nontrivial.
The second step is identical to the case of the rational sieve, and is a straightforward linear algebra problem. The first step, however, is done in a different, more efficient way than the rational sieve, by utilizing number fields.
Let n be the integer we want to factor. We pick an irreducible polynomial f with integer coefficients, and an integer m such that f(m)≡0 (mod n) (we will explain how they are chosen in the next section). Let α be a root of f; we can then form the ring Z[α]. There is a unique ring homomorphism φ from Z[α] to Z/nZ that maps α to m.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (1)

MATH-489: Number theory II.c - Cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC

Related lectures (5)

Integer Factorization: Quadratic Sieve

Covers the Quadratic Sieve method for integer factorization, emphasizing the importance of choosing the right parameters for efficient factorization.

Galois Fields and Elliptic Curves

Introduces Galois fields, elliptic curves, factorization algorithms, and the discrete logarithm problem in cryptography.

Elliptic Curve Cryptography: Basics and Applications

Explores the basics and applications of elliptic curve cryptography, covering ECM factorization, standard curves, practical examples, and real-world implementations.

Related publications (18)

Related people (7)

Related concepts (2)

Smooth number

In number theory, an n-smooth (or n-friable) number is an integer whose prime factors are all less than or equal to n. For example, a 7-smooth number is a number whose every prime factor is at most 7, so 49 = 72 and 15750 = 2 × 32 × 53 × 7 are both 7-smooth, while 11 and 702 = 2 × 33 × 13 are not 7-smooth. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography, which relies on factorization of integers.

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of 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, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4.

The RSA cryptosystem introduced in 1977 by Ron Rivest, Adi Shamir and Len Adleman is the most commonly deployed public-key cryptosystem. Elliptic curve cryptography (ECC) introduced in the mid 80's by Neal Koblitz and Victor Miller is becoming an increasin ...

Arjen Lenstra, Joppe Willem Bos, Thorsten Kleinjung, Andrea Miele

We show how the cofactorization step, a compute-intensive part of the relation collection phase of the number field sieve (NFS), can be farmed out to a graphics processing unit. Our implementation on a GTX 580 GPU, which is integrated with a state-of-the-a ...

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...