The Extended Euclidean Algorithm is an extended version of the Euclidean Algorithm, which is used to find the greatest common divisor (GCD) of two numbers. This algorithm is mentioned in one of Vitalik's blog posts here, about stark proofs, which are zero knowledge proofs used to help Ethereum scale it´s network. In this article, we will explain how the algorithm works and how it is implemented in the Ethereum network, which you can find here.

Understanding the Euclidean Algorithm

Before we dive into the Extended Euclidean Algorithm, let's first discuss the Euclidean Algorithm. The Euclidean Algorithm is a simple and efficient way of finding the GCD of two numbers. It works by repeatedly subtracting the smaller number from the larger number until the remainder is zero. The GCD is the last non-zero remainder.

For example, to find the GCD of 24 and 16, we first divide the larger number, 24, by the smaller number, 16. The quotient is 1, and the remainder is 8. We then divide the smaller number, 16, by the remainder, 8. The quotient is 2, and the remainder is 0. Therefore, the GCD of 24 and 16 is 8.

Understanding the Extended Euclidean Algorithm

The extended Euclidean algorithm is a method for finding the coefficients of the Bezout identity ax + by = GCD(a, b) without explicitly computing the GCD. The algorithm proceeds by iteratively finding remainders and expressing them as linear combinations of the previous remainders until a remainder of 0 is obtained. At each step, the algorithm updates the coefficients of the linear combinations. The final coefficients are the Bezout coefficients that satisfy the Bezout identity.

Python Implementation of the algorithm in Ethereum used for zk starks

# Extended Euclidean Algorithm
def inv(a, n):
    if a == 0:
        return 0
    lm, hm = 1, 0
    low, high = a % n, n
    while low > 1:
        r = high // low
        nm, new = hm - lm * r, high - low * r
        lm, low, hm, high = nm, new, lm, low
    return lm % n

Let's unpack the code, what we are trying to find is the value of x such that (a*x) % n = 1, this equation can also be rewritten as:

a*x + n*y = 1

The point of the extendend Euclidean algorithm is to find the coefficients of this equation. During the algorithm, we keep track of two sequences of coefficients, lm and hm, such that:

lm*a + hm*n = low

if 'a' is 0 this means that there isn't a number that is going to make the remainder of 'a' divide by 'n' to be equal to 1, in this case the algorithm returns 0 because the coefficient doesn't exist.

on this line:

low, high = a % n, n
while low > 1:
    r = high // low

low is always going to be lower than high because by definition the remainder of 'a' divided by 'n' -> a % n will always have to be lower than 'n' itself. So when you calculate 'r' what you are answering is: How many times can the remainder of the division fit into 'n'? the '//' means integer division which means it will always be an int value, so if the result of a normal divison is 1.7 for example, the value would be 1 because of the integer division.

The expression:

hm - lm * r 

is used to update the value of lm in such a way that the linear combination of 'a' and 'n' still adds up to the current value of the remainder

nm, new = hm - lm * r, high - low * r

The value of nm is going to be the updated coefficient of 'lm' for each iteration which starts of equal to 1 -> lm = 1, at each iteration the value of 'hm' is going to become the previous value of 'lm', and the value of 'lm' is going to become -> nm = hm - lm * r, so think about this as if we are updating 'lm' based on the quotient 'r' of the previous iteration, and 'hm' is the previous value of 'lm', starting off as 0 in the first iteration, so 'hm' is 'lm' behind by one iteration.

on the right side we have:

new = high - low * r

Here 'low' represents the current smallest non-zero remainder and 'new' will be the next smallest non-zero remainder, so this 'new' value is going to be the updated value of 'low', which is the updated remainder, when you subtract 'high' which in the first iteration is 'n' by the remainder of the division of 'a' by 'n' (a % n) which is 'low' times the amount that this remainder can fit into 'n' itself ('r') what you are doing is getting the 'gap' that the remainder has until it reaches 'n'. Another way to look at it is new = high - low * r is equivalent to new = high % low, and in practice, the expression new = high - low * r is used in the algorithm because it is more efficient to compute low * r once, and then subtract it from high, rather than computing high mod low directly.

So let's say a = 5 and n = 20, then a % n = 5, which is the first 'low' and 'high' would be 20, this means 'r' would be 20 // 5 which is 4. If you calculate new = high - low * r you would get: new = 20 - 5 * 4 which would be 0. In this case the new 'low' would be 0 and the new 'high' would be 5. In this case low would be less than 1 so the algorithm would return lm % n, lm would be equal to nm after the first iteration which would be: nm = hm - lm * r, which in this case would be nm = 0 - 1 * 4 = -4, this means that -4 % 20 = 16 and this would be the value the algorithm returns.

The reason why -4 % 20 = 16 is because to compute the positive remainder of -4 when divided by 20, we can add 20 to -4 repeatedly until the result is positive and less than 20.

Applications of the Extended Euclidean Algorithm

The Extended Euclidean Algorithm has many applications in various fields, including:

1. Cryptography The Extended Euclidean Algorithm is used in the field of cryptography to find the multiplicative inverse of a number modulo another number. The multiplicative inverse of a number a modulo m is a number x such that ax ≡ 1 (mod m).

2. Zero knowledge proofs The Algorithm is one of the functions used to help make zero knowledge proofs possible on the Ethereum network.

3. Number Theory The Extended Euclidean Algorithm is used in number theory to solve Diophantine equations, which are equations of the form ax + by = c, where a, b, and c are integers.

Conclusion

The Extended Euclidean Algorithm is one of the functions that is used to make stark zero knowledge proofs on the Ethereum network. The Algorithm works by calculating the remainders of two numbers and updating the coefficients of their linear combinations at each iteration in order to find the inverse multiplicative module which is (a*x) % n = 1. We hope this article has helped you understand the Extended Euclidean Algorithm and its applications.