Concept

Euclidean algorithm

Related lectures (28)

Explores polynomial roots, factorization, and the Euclidean algorithm in depth.

Euclid and Bézout: Algorithms and Theorems

Explores the Euclidean algorithm, Bézout's identity, extended Euclid algorithm, and commutative groups in mathematics.

Covers the Shor Algorithm for period finding and its application in factorization, discussing the circuit implementation and measurement outcomes.

Euclidean Algorithm: GCD Calculation

Covers the Euclidean algorithm for GCD calculation and algorithmic complexity analysis.

Properties of Euclidean Domains

Covers the properties of Euclidean domains and irreducible elements in polynomial rings.

Algebra: Integer Numbers and Principles

Introduces integer numbers, well-ordering, induction principles, GCD, LCM, and Bezout's theorem.

Quantum Algorithms: Shor Algorithm

Covers the analysis of measurements in the context of the Shor algorithm.

Chinese Remainder Theorem and Euclidean Domains

Explores the Chinese remainder theorem, systems of congruences, and Euclidean domains in integer numbers and polynomial rings.

System Equivalence

Explores system equivalence, state-space representation, transfer functions, and Euclidean rings, emphasizing unimodular matrices and their properties.

Shor's Factoring Algorithm

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

Number Theory: GCD and LCM

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

Number Theory: GCD and LCM

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

Chinese Remainder Theorem: Rings and Fields

Covers the Chinese remainder theorem for commutative rings and integers, polynomial rings, and Euclidean domains.

Algorithms for Big Numbers: Z_n and Orders

Covers algorithms for big numbers, Z_n, and orders in a group, explaining arithmetic operations and cryptographic concepts.

Polynomial Factorization over Finite Fields

Introduces polynomial factorization over finite fields and efficient computation of greatest common divisors of polynomials.

The Greatest Common Divisor

Covers the greatest common divisor, Euclidean algorithm, Joseph Stein's algorithm, and practical examples.

Integers: Sets, Maps, and Principles

Introduces sets, maps, divisors, prime numbers, and arithmetic principles related to integers.

Total Order Broadcast: Basics and Consensus Equivalences

Explores total order broadcast and its equivalence to consensus in reliable systems.

Rudiments of Number Theory

Introduces modulo arithmetic, Euclid's algorithm, and congruence in number theory.

Quantum and nanocomputing

Covers the basics of number theory, RSA encryption, and Shor's period finding algorithm.