if in each step instead of collecting bi, we just multiply the second paired value to a result that starts at 1 (mod p), you can write this as the following python: def mod_inv(a, p): res = 1 while a != 1: q, r = p // a, p % a if r < a - r: a, res = r, (res * -q) % p else: a, res = a - r, (res * (q + 1)) % p return res
Combining her notes from the previous video: ``` def mod_inv(a, p): _, x, _ = egcd(a, p) return (x % p + p) % p def egcd(a, b): if is_prime(b): # AKS ? return egcd_reference(a, b) return egcd_gauss(a, b) def egcd_gauss(a, b): x, y, u, v = 0, 1, 1, 0 while a != 0: q1, r1 = b // a, b % a q2, r2 = q1 + 1, a - r1 if r1
Very interesting question! You could imitate the formalism using polynomials instead of integers (the usual model of finite fields). I think this works fine. It's a bit more work than the usual Euclidean algorithm, because you keep around p (which is now a big polynomial), instead of swapping it out for smaller things, like in the usual Euclidean algorithm. (In the prime modulus case also, this algorithm is slower than the euclidean one -- it's of more interest pedagogically than practically.)
