扩展欧几里得算法求逆元算法java
时间: 2023-11-10 20:03:33 浏览: 116
扩展欧几里得算法是一种求解线性同余方程 ax ≡ 1 (mod m) 中 x 的逆元的方法。逆元是指数值 x 使得 ax 与 m 取模之后的结果为 1。
下面是一个用 Java 实现扩展欧几里得算法求逆元的代码示例:
```java
public class InverseElement {
public static int extendedEuclidean(int a, int b) {
int[] coeffs = new int[3]; // 存储扩展欧几里得算法求解的系数
int x = 0, y = 0;
while (b != 0) {
coeffs = updateCoeffs(a, b, coeffs);
a = coeffs[0];
b = coeffs[1];
x = coeffs[2];
y = coeffs[3];
}
if (a == 1) {
return (x % m + m) % m; // 防止结果为负数
} else {
return -1; // 没有逆元
}
}
private static int[] updateCoeffs(int a, int b, int[] coeffs) {
if (b == 0) {
coeffs[0] = a;
coeffs[1] = b;
coeffs[2] = 1;
coeffs[3] = 0;
return coeffs;
}
coeffs = updateCoeffs(b, a % b, coeffs);
int x1 = coeffs[2];
int y1 = coeffs[3];
coeffs[2] = y1;
coeffs[3] = x1 - (a / b) * y1;
return coeffs;
}
public static void main(String[] args) {
int a = 7;
int m = 11;
int inverse = extendedEuclidean(a, m);
System.out.println("逆元: " + inverse);
}
}
```
在上述代码中,`extendedEuclidean` 方法实现了扩展欧几里得算法, `updateCoeffs` 方法用于更新系数, `main` 方法用于测试求逆元的结果。在示例中,我们以 `a = 7` 和 `m = 11` 为例来求解逆元。
按照扩展欧几里得算法的步骤,我们递归调用 `updateCoeffs` 方法来更新系数,直到 b 为 0。然后,如果 a 为 1,则返回取模后的 x 值作为逆元;否则,返回 -1 表示没有逆元。
输出结果为:逆元:8,表示在模 11 下,7 的逆元为 8。
阅读全文