求逆元的方法汇总



的

可以使用扩展欧几里得

。扩展欧几里得

可以求解形如ax + by = gcd(a, b)的整数解(x, y)，其中a和b为整数。当a和b互质时，gcd(a, b) = 1，所以可以得到ax + by = 1的整数解(x, y)。因此，x就是a对于模b的乘法

。

以下是求解

的Python代码：

def extended_gcd(a, b):

if b == 0:

return (a, 1, 0)

else:

gcd, x, y = extended_gcd(b, a % b)

return (gcd, y, x - (a // b) * y)

def modular_inverse(a, m):

gcd, x, _ = extended_gcd(a, m)

if gcd == 1:

return (x % m + m) % m

else:

return None

通过调用modular_inverse函数，可以求解给定数a对于质数p的乘法

。如果

不存在，则返回None。代码中使用了扩展欧几里得

来求解gcd(a, p) = 1的整数解(x, _)，其中x就是a对于模p的乘法

。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/9590.html