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

Lecture

Shor's Factoring Algorithm

Description

This lecture covers Shor's factoring algorithm, which aims to find an integer factor with high probability using quantum computation. The algorithm involves concepts such as general number fields, order finding, and group theory. It explains the process of finding factors efficiently and the theoretical background behind the algorithm.

Official source

Related concepts (32)

Euclidean algorithm

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use.

Shor's algorithm

Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (that is, non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future.

Quantum algorithm

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer.

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.

Quantum computing

A quantum computer is a computer that exploits quantum mechanical phenomena. At small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior, specifically quantum superposition and entanglement, using specialized hardware that supports the preparation and manipulation of quantum states. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer.

Related lectures (30)

Elementary Algebra: Numeric Sets

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

Shor's Factoring Algorithm

Covers Shor's factoring algorithm, which efficiently factors large numbers using quantum computers.

Number Theory: GCD and LCM

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

Number Theory: Fundamental Concepts

Covers binary addition, prime numbers, and the sieve of Eratosthenes in number theory.

Generator of a Group