cryptography - 如何使用扩展欧几里德算法获得模逆？

Question

给定一个 mod b 并找到它的逆，然后做扩展的 GCD。

ax + by = gcd(a,b)

在我得到 x 和 y 之后，我如何得到它的倒数？

Answer 1

如果gcd(a,b) != 1,a没有逆mod b。

否则ax + by = 1，这意味着mod的倒数也是ax = 1 (mod b)如此。xab

Answer 2

这样做可以计算x与模m的倒数：

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b === 1 return a % m
    error("must be coprime")

这里:=是同时赋值运算符，所以右边的所有计算都是先完成的，然后是所有的赋值。该divide函数返回 的商和余数b / x。