Java实现模多项式求逆

在Java中，如果需要实现模多项式的求逆，通常涉及到数论中的扩展欧几里得算法（Extended Euclidean Algorithm），特别是在计算模素数p下的整数逆元时。对于两个整数a和p，其中p是质数，如果它们互质（即gcd(a, p) = 1），那么a就有逆元a^-1 mod p，使得aa^-1 ≡ 1 (mod p)。

你可以通过以下步骤实现模逆：

1. 定义一个`ModularInverse`类，包含一个静态方法`extendedEuclidean(a, p)`，用于计算a关于p的逆元。
2. 使用扩展欧几里得算法找到最大公约数gcd(a, p)，以及满足ax + py = gcd(a, p)的解x和y。如果gcd != 1，则说明a和p不是互质的，此时不存在逆元。
3. 如果gcd == 1，那么a的逆元就是x mod p。因为ax ≡ gcd ≡ 1 (mod p)，所以x % p即为所求的逆元。

下面是一个简单的示例实现：

public class ModularInverse {
    public static int extendedEuclidean(int a, int p) {
        if (p == 0) throw new IllegalArgumentException("p must be non-zero");
        int x = 0, lastX = 1, y = 1, lastY = 0;
        while (a != 0) {
            int q = p / a;
            int t = a;
            a = p % a; // 将a更新为余数
            p = t;
            t = x;
            x = lastX - q * x;
            lastX = t;
            t = y;
            y = lastY - q * y;
            lastY = t;
        }
        return (lastY + p) % p; // 返回结果并取模
    }

    // 示例：计算5的模7逆元
    public static void main(String[] args) {
        int a = 5, p = 7;
        int inv = extendedEuclidean(a, p);
        System.out.printf("5's inverse modulo 7 is: %d%n", inv);
    }
}