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

Lecture

Lenstra's Algorithm: Integer Factorization

In course

MATH-328: Algebraic geometry I - Curves

Algebraic geometry is the common language for many branches of modern research in mathematics. This course gives an introduction to this field by studying algebraic curves and their intersection theory. ...

Description

This lecture covers Lenstra's Algorithm for integer factorization, which computes the prime factors of an integer in polynomial time. The algorithm involves choosing random elliptic curves and points, and performing computations to find prime divisors efficiently.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Instructor

Dimitri Stelio Wyss

Official source

Ontological neighbourhood

Mathematics

Algebra: Abstract algebra

Theoretical computer science

Theory of computation: Computational complexity theory

Related concepts (32)

Integer factorization

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers. If the factors are further restricted to be prime numbers, the process is called prime factorization, and includes the test whether the given integer is prime (in this case, one has a "product" of a single factor). When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist.

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.

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Polynomial-time reduction

In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming or reducing it to inputs for the second problem and calling the subroutine one or more times. If both the time required to transform the first problem to the second, and the number of times the subroutine is called is polynomial, then the first problem is polynomial-time reducible to the second.

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Related lectures (24)

Elementary Algebra: Numeric Sets

Explores elementary algebra concepts related to numeric sets and prime numbers, including unique factorization and properties.

Factoring Polynomials: Complexity and Algorithms

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

Number Theory: GCD and LCM

Covers GCD, LCM, and the Euclidean algorithm for efficient computation of GCD.

Integer Factorization: Methods and Algorithms

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

Prime Numbers and Primality Testing