扩展欧几里得算法求逆元python
时间: 2023-09-30 17:09:06 浏览: 62
下面是一个用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`。
示例:
```python
print(mod_inv(3, 11)) # 输出 4,因为 3 * 4 ≡ 1 (mod 11)
print(mod_inv(4, 8)) # 输出 None,因为 4 在模 8 意义下没有逆元
```
相关问题
扩展欧几里得算法求逆元py
扩展欧几里得算法是一种求解线性方程ax+by=gcd(a,b)的算法,其中a、b是整数,x和y是整数解,gcd(a,b)表示a和b的最大公约数。
扩展欧几里得算法可以被用来求解模反元素,模反元素也被称为逆元。逆元是模数n下的一个数x,满足(ax mod n) ≡ 1。
我们可以使用扩展欧几里得算法来求解逆元。具体步骤如下:
1. 初始化a=n,b=m,其中n是模数,m是要求逆元的数。
2. 初始化x=1,y=0。
3. 当b不等于0时,重复以下步骤:
a. 计算商数q = a // b和余数r = a % b。
b. 更新a = b,b = r。
c. 更新x = x_prev - q * x,y = y_prev - q * y。
4. 返回x作为逆元。
下面是一个使用Python实现的例子:
```
def extended_gcd(a, b):
if b == 0:
return (1, 0)
(x_prev, y_prev) = extended_gcd(b, a % b)
(x, y) = (y_prev, x_prev - (a // b) * y_prev)
return (x, y)
def invert_modulo(m, n):
(x, _) = extended_gcd(n, m)
return x % n
n = 17
m = 5
inverse = invert_modulo(m, n)
print(inverse) # 输出7
```
在上面的例子中,我们想要求模数n=17下数字5的逆元。根据计算,我们得到逆元7。
扩展的欧几里得算法求乘法逆元python
以下是扩展的欧几里得算法求乘法逆元的Python代码:
```python
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
def multiplicative_inverse(a, m):
gcd, x, y = extended_gcd(a, m)
if gcd != 1:
raise ValueError("Multiplicative inverse does not exist")
return x % m
```
其中,`extended_gcd`函数用于求解最大公约数和贝祖等式中的`x`和`y`,`multiplicative_inverse`函数则是根据贝祖等式求解乘法逆元。如果`a`和`m`不互质,则在求解乘法逆元时会抛出`ValueError`异常。