Michele Dinelli

Lab 01

Summary: Lecture content for the first laboratory session
Reading time: 3 minutes
Commit: dfdf9be

The Euclidean algorithm calculates the Greatest Common Divisor (GCD) between two numbers. For given integers \(a\) and \(b\), the extended Euclidean algorithm not only calculates the GCD between \(a\) and \(b\) but also two additional integers \(s\) and \(t\) that satisfy the equation \(as + bt = gcd(a, b)\).

Exercise 1

Solution 1

// Euclidean algorithm iterative version
func Gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }
    return a
}

// ExtendedGCD computes the greatest common
// divisor of a and b, along with coefficients
// x and y satisfying: ax + by = gcd(a, b)
//
// Returns: (gcd(a, b), x, y)
func ExtendedGCD(a, b int) (int, int, int) {
	// Base case: when a is 0, gcd is b
	// and the equation becomes: 0·x + b·y = b
	// which is satisfied by x=0, y=1
	if a == 0 {
		return b, 0, 1
	}

	// Recursive call with (b mod a, a)
	gcd, x1, y1 := ExtendedGCD(b%a, a)

	// Update coefficients using the recurrence relation:
	// x = y1 - (b/a) * x1
	// y = x1
	x := y1 - (b/a)*x1
	y := x1

	return gcd, x, y
}

Using algorithms above one can verify that

Exercise 2

One of the most common uses of the Extended Euclidean Algorithm is computing modular inverses which is essential in RSA cryptography.

Compute the following multiplicative inverses:

  1. \(17^{−1} \ mod \ 101\)
  2. \(357^{−1} \ mod \ 1234\)
  3. \(3125^{−1} \ mod \ 9987\)

Solution 2

An element \(x\) in \(\mathbb{Z}_n\) has a multiplicative inverse if and only if \(\gcd(x, n) = 1\), i.e., \(x\) and \(n\) are coprime. Two integers are coprime if and only if \(\gcd(x, n) = 1\), which holds if and only if there exist integers \(s, t\) such that \(xs + nt = 1\). In \(\mathbb{Z}_n\), the term \(nt\) is congruent to \(0\), so reducing modulo \(n\) gives \(xs + nt \equiv 1 \ (\text{mod } n)\), which is equivalent to \(xs \equiv 1 \ (\text{mod } n)\). Thus, \(s\) is the multiplicative inverse of \(x\) in \(\mathbb{Z}_n\).

Using the extended Euclidean algorithm one can solve \(xs + nt \equiv 1 \ (\text{mod } n)\)