Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Integer Factorization: Quadratic Sieve

In course

MATH-489: Number theory II.d - Cryptography

. ...

Description

This lecture covers the Quadratic Sieve method for integer factorization, which generalizes to allow for factoring smaller size numbers. The method involves sieving and selecting smooth numbers to efficiently factorize integers. It also discusses the complexity of the Quadratic Sieve algorithm and its application in finding B-smooth numbers. The instructor explains the process step by step, from sieving to selecting numbers to be factored, emphasizing the importance of choosing the right parameters for efficient factorization.

Instructor

Dimitar Petkov Jetchev

Official source

Ontological neighbourhood

Mathematics

Number theory: Topics in number theory

Related concepts (32)

Quadratic sieve

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). 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.

General number field 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 ⌊log2 n⌋ + 1 bits) is of the form in O and L-notations. 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 (which are trivial to factor by taking roots).

Sieve of Atkin

In mathematics, the sieve of Atkin is a modern algorithm for finding all prime numbers up to a specified integer. Compared with the ancient sieve of Eratosthenes, which marks off multiples of primes, the sieve of Atkin does some preliminary work and then marks off multiples of squares of primes, thus achieving a better theoretical asymptotic complexity. It was created in 2003 by A. O. L. Atkin and Daniel J. Bernstein. In the algorithm: All remainders are modulo-sixty remainders (divide the number by 60 and return the remainder).

Sieve of Eratosthenes

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.

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.

Related lectures (51)

Factoring Polynomials: Complexity and Algorithms

Delves into the complexity of factoring polynomials and the implications for security.

Integer Factorization: Methods and Algorithms

Explores methods and algorithms for integer factorization, including testing for B smoothness and computing small primes.

Integer Factorization: Quadratic Sieve

Explores integer factorization using the quadratic sieve method and the challenges of working with algebraic number fields.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Number Theory: Fundamental Concepts