L10 Public Key Mathematics

Euclidean Algorithm, Extended Euclidean Algorithm. Other PK theorems.

What is modular multiplicative inverse and when does it exist?

The inverse of a mod p is a⁻¹ such that a · a⁻¹ ≡ 1 (mod p).

It exists if and only if gcd(a, p) = 1

What does the Euclidean Algorithm compute and how does it work?

It computes gcd(r₀, r₁) by repeatedly applying rᵢ = rᵢ₋₂ mod rᵢ₋₁ until the remainder is 0.

The last non-zero remainder is the GCD

What does the Extended Euclidean Algorithm (EAA) compute?

It computes gcd(r₀, r₁) and additionally finds values s and t such that s·r₀ + t·r₁ = gcd

This directly yields the modular inverse, essential for RSA key generation.

What is Bézout's Identity?

gcd(a, b) can always be expressed as a linear combination: s·a + t·b = gcd(a, b). The EEA finds s and t efficiently.