Lecture

Lenstra's Algorithm: Integer Factorization

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

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.

Instructor

Dimitri Stelio Wyss

I did my PhD under the supervision of Tamas Hausel at EPFL and the Institue of Science and Technology Austria . From 2017-2019 I was a postdoctoral researcher at the Sorbonne University Paris 6 with François Loeser. Since September 2019 I hold the chair of arithmetic geometry at EPFL as a tenure track assistant professor. For more information see my CV.I work in algebraic and arithmetic geometry. My research uses ideas from p-adic and motivic integration to study the interplay between geometric and arithmet

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.

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.

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.

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.

Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

Related lectures (64)

Elementary Algebra: Numeric Sets

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

Primes and Coprime

Explores prime numbers, coprime integers, and their properties in number theory.

Shor's algorithm: factoring integers

Covers the basics of Shor's algorithm for factoring integers and the steps involved in the quantum algorithm.

Shor's Factoring Algorithm

Covers Shor's factoring algorithm, aiming to find integer factors efficiently using quantum computation.

Factoring Polynomials: Complexity and Algorithms