java - 在 Java 中使用扩展 Euclid 算法实现 modInverse

Question

不应使用 BigInteger 类的 modInverse 方法。我尝试并使用了这种方法，但它没有产生正确的结果。任何帮助，将不胜感激。

public static int[] extendedgcd(int a, int b) {
        if (b==0) {
            return new int[]{1, 0, a};
        } else {
            int output[] = extendedgcd(b, a%b);
            return new int[]{output[0], output[0]-((a/b)*output[1]), output[2]};
        }
    }

Answer 1

在 else-branch 中，第一个返回值应该output[1]是output[0]：

public static int[] extendedgcd(int a, int b) {
    if (b == 0) {
        return new int[]{1, 0, a};
    } else {
        int output[] = extendedgcd(b, a % b);
        return new int[]{
            output[1],
            output[0] - ((a / b) * output[1]),
            output[2]
        };
    }
}

您可以在这里测试实现：https ://onlinegdb.com/volwDTwnl