python域求逆元

求解一个数在模意义下的逆元是常见的数学问题，可以使用扩展欧几里得算法来解决。假设我们要求解 $a$ 在模 $m$ 意义下的逆元，即 $a^{-1} \pmod{m}$，则可以通过以下代码实现：

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = exgcd(b, a % b)
        return d, y, x - (a // b) * y

def mod_inv(a, m):
    d, x, y = exgcd(a, m)
    if d == 1:
        return (x % m + m) % m
    else:
        return -1

其中 `exgcd` 函数是扩展欧几里得算法的实现，返回值为 $a$ 和 $b$ 的最大公约数 $d$，以及满足 $ax+by=d$ 的一组整数解 $(x,y)$。`mod_inv` 函数则是利用 `exgcd` 函数来求解逆元的函数，如果 $a$ 和 $m$ 不互质，则返回 -1。

相关问题

java有限域求乘法逆元

以下是Java中有限域求乘法逆元的示例代码：

public static int getInverse(int a, int p) {
    int[] xy = extendedEuclidean(a, p);
    if (xy[0] != 1) {
        throw new ArithmeticException("Inverse does not exist");
    }
    return (xy[1] + p) % p;
}

public static int[] extendedEuclidean(int a, int b) {
    if (b == 0) {
        return new int[] {a, 1, 0};
    }
    int[] xy = extendedEuclidean(b, a % b);
    int x = xy[2];
    int y = xy[1] - (a / b) * xy[2];
    return new int[] {xy[0], x, y};
}

其中，`getInverse`方法用于计算乘法逆元，`extendedEuclidean`方法用于计算扩展欧几里得算法。在有限域GF(p)中，a的乘法逆元为b，当且仅当a和p互质，即gcd(a, p) = 1。

扩展欧几里得算法求逆元python

下面是一个用Python实现的扩展欧几里得算法求逆元的示例代码：

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x, y = exgcd(b, a % b)
        return gcd, y, x - (a // b) * y

def mod_inv(a, m):
    gcd, x, y = exgcd(a, m)
    if gcd != 1:
        return None  # 逆元不存在
    else:
        return (x % m + m) % m  # 返回正整数范围内的逆元

其中，`exgcd(a, b)`函数为扩展欧几里得算法的实现，返回值为`(gcd, x, y)`，其中`gcd`为`a`和`b`的最大公约数，`x`和`y`满足`ax + by = gcd`的一组解。`mod_inv(a, m)`函数为求`a`在模`m`意义下的逆元，当逆元不存在时返回`None`。

示例：

print(mod_inv(3, 11))  # 输出 4，因为 3 * 4 ≡ 1 (mod 11)
print(mod_inv(4, 8))   # 输出 None，因为 4 在模 8 意义下没有逆元