乘法逆元学习记录

乘法逆元

对整数a、p，若gcd(a,p) == 1（即需要a、p互质），则存在整数b使得ab ≡ 1 mod p，称b为a关于1模p的乘法逆元，一般将乘法逆元b记作。

存在的意义

在计算如  mod n时，可能会由于精度问题而导致结果的不准确（ 可能为小数），或是因为运算的先后问题而导致结果错误（先求模在作除法=》可能会导致结果错误），故需要将除法转成乘法，从而避免了误差或直接错误，这里就需要用到乘法逆元。

设c为b关于1模n的乘法逆元，则有bc ≡ 1 mod n，则 mod n =   * 1 mod n =  *bc = ac mod n

即a/b的模就等于a*(b的逆元)的模。

求乘法逆元的方法

利用费马小定理

理论：对于互质的两整数a、p，有 ≡ a mod p

上式进行变形可得到：  ≡ 1 mod p

设x为a的逆元，则ax ≡ 1 mod p，用mod p替换1可得逆元x ≡  mod p

代码实现：

def Fastpow(a,p_2,moshu):
    result = 1
    while p_2 > 0:
        if p_2 % 2 == 1:
            p_2 = p_2 / 2
            a = a * a % moshu
        else:
            p_2 = p_2 - 1
            result = result * a % moshu
            p_2 = p_2 / 2
            a = a * a % moshu
    return result
a = int(input())
p = int(input())
 
x = Fastpow(a,p-2,p)
print(x)

4为3关于1模11的逆元，即3*4  1 mod 11 

这里用到了快速幂算法，这位大佬写得非常清楚！因为第一次接触，学习了他的思路，写的基础代码，后面再对快速幂算法作重新学习并记录，并优化代码。

利用扩展欧几里得算法

理论基础：欧几里得算法（辗转相除法）、贝祖定理

欧几里得算法：用于求两数的最大公约数，具体做法为（为了方便自己理解，直接用实例来进行说明，如求202和19的最大公约数的）：

202 / 19 = 10 余 12

19 / 12 = 1 余 7

12 / 7 = 1 余 5

7 / 5 = 1 余 2

5 / 2 = 2 余 1

2 / 1 = 0 余 0        结束计算

计算过程即为：不断用除数（b作为新的a）除以余数（a%b作为新的b），直至能够整除，最后一步的除数即为所求的最大公约数，即举例中的202和19的最大公约数为1。

贝祖定理：对于任意的整数a，b，都存在一对整数x，y，使得ax+by=gcd(a,b)成立。求乘法逆元的过程中，对于互质的a、b，有gcd(a,b) = 1，故有ax+by=1。由乘法逆元的定义，ab ≡ 1 mod p，即ab = 1+kp ==》ab-kp = 1，提个负号并交换下k、p的位置得：ab + pk = 1，到这就能够用扩展欧几里得算法来求得b、k

在上面的欧几里得算法中，利用递归，不断对参数进行改变：gcd(a,b) = gcd(b,a%b)，当b=0时，结束递归，返回a，此时a即为最大公约数gcd，则gcd * x + 0 * y = gcd，显然，有解x=1，y=0。

我们假设通过n次的迭代求得了最后一次的xn=1和yn=0，现在我们要求初始的x和y，则须通过反推。

第一次计算gcd(a,b)，有ax1 + by1 = gcd，

第二次计算gcd(b,a%b)，有bx2 + (a%b)y2 = gcd

则ax1 + by1 = bx2 + (a%b)y2

又a%b = a - a = a - a//b * b（整除），整理得ax1 + by1 = ay2​+b(x2​−(a/b)y2​)

即x1 = y2 ，y1 = x2​−(a/b)y2

说明每一组的解可以由后一组得到，而最后的解又是知道的，从而解出初始x、y

代码实现：

def ext_gcd(a, b): #扩展欧几里得算法
    if b == 0:
        return 1, 0, a
    else:
        x, y, gcd = ext_gcd(b, a % b) #递归直至余数等于0(需多递归一层用来判断)
        x, y = y, (x - (a // b) * y) #辗转相除法反向推导每层a、b的因子使得gcd(a,b)=ax+by成立
        return x, y, gcd
 
a = int(input())#模数
b = int(input())#求b的逆元
 
x,y,gcd = ext_gcd(a,b)
print(x,y,gcd)

代码参考的http://t.csdn.cn/qSauX，有点晕了说实话，先记录着，后面复习按自己的思路再来敲。

思路参考了许多大佬。 

还有其它方法能够求逆元，目前先熟悉熟悉这两种。菜鸟叹气🙃