Extended Euclidean Algorithm

The Extended Euclidean Algorithm (EEA)

Definition and Purpose

  • The Extended Euclidean Algorithm (EEA) is an algorithm used to compute multiplicative inverses modulo a prime number p.

Relation to the Euclidean Algorithm

  • Euclidean Algorithm Definition:

    • The Euclidean Algorithm is a method for finding the greatest common divisor (gcd) of two integers.

    • Example to find gcd(17, 5):

      • 17 = 5 × 3 + 2

      • 5 = 2 × 2 + 1

      • 2 = 1 × 2 + 0

      • The process stops here, and we find gcd(17, 5) = 1.

The Extended Euclidean Algorithm Explained

  • What Does EEA Do?

    • The EEA functions similarly to the Euclidean algorithm but with the added capability of producing integers x and y such that:

    • extgcd(a,b)=ax+byext{gcd}(a, b) = ax + by

  • This is particularly valuable in modular arithmetic as it allows us to compute the modular inverse:

    • If the relationship ab≡1mod  pab \equiv 1 \mod p holds true, then b serves as the inverse of a modulo p. The EEA is specifically designed to compute this modular inverse efficiently.