一、问题背景
笔者最近在研究RSA算法的时候遇到了一个问题，其中有一个核心公式，是为了计算private key : {d,n}中的参数d，公式如下：
d = e − 1 m o d ϕ ( n ) d = e^{-1} \bmod \phi(n)d=e−1modϕ(n)
其中只有d是未知项，原式为：
d e ≡ 1 ( m o d ϕ ( n ) ) de \equiv 1 (\bmod \phi(n))de≡1(modϕ(n))
代入之后得到（一个随机的例子）：
5 d ≡ 1 ( m o d 96 ) 5d \equiv 1 (\bmod 96)5d≡1(mod96)
这个式子的含义是5乘以一个数d，对96求余，结果为1，如果上式有解，则d称为5的乘法逆元。
二、乘法逆元
1. 什么是乘法逆元
乘法逆元的英文名称是Multiplicative inverse modulo，因为其中有对模的运算，所以也称作模逆元素，也可称作数论倒数。
说到这里，我们可以解释和理解一下这个概念，可以整理出如下的式子：
a ⋅ x ≡ 1 ( m o d p ) a \cdot x \equiv 1 (\bmod p)a⋅x≡1(modp)
其中，a与p是已知项，x是未知项。我们可以从倒数的概念入手来理解这个式子，比如：
5 ⋅ x = 1 5 \cdot x = 15⋅x=1
x = 5 − 1 x = 5^{-1}x=5−1
此时，5和x互为倒数，它们的乘积为1。模逆元素与之类似，只不过它们的乘积为 1 (mod p)，所以x可以表示为：
x ≡ a − 1 ( 1 m o d p ) x \equiv a^{-1} (1 \bmod p)x≡a−1(1modp)
但是需要注意，在这个式子中a的右上角标-1并不是a分之1，而是代表a的逆之类的含义，知道了表示x的式子我们就可以利用一些工具直接求出结果。
2. 在线计算网站
比如上面的例子，想要计算5对于(mod 96)的逆元，就可以得到：
x ≡ 5 − 1 ( 1 m o d 96 ) x \equiv 5^{-1} (1 \bmod 96)x≡5−1(1mod96)
可以直接得到结果：
结果为77，经过验算有：5 x 77 / 96 = 4 … 1。
也可以表示为：5 x 77 = 385 = 96 x 4 + 1。
3. 存在性条件
求模逆元素有解的前提是a与p互质，如果互质则一定存在一个正整数解，如果不互质，则一定不存在正整数解。
这一点用验算式子可以比较容易的证明，如果a与p不互质，就说明除1之外有其它公约数，并且还需要满足：
m , n ∈ N + , a ⋅ m − p ⋅ n = 1 m,n \in N_{+} , a \cdot m - p \cdot n = 1m,n∈N+,a⋅m−p⋅n=1
由于a和p存在其它公约数，所以等号左边可以提出一个系数，记为c：
c ( a c ⋅ m − p c ⋅ n ) = 1 c (\frac{a}{c} \cdot m - \frac{p}{c} \cdot n) = 1c(ca⋅m−cp⋅n)=1
可以看到，如果m和n均为正整数，找不到一个解能使上式成立。可以证明，当a与p不互质时，则一定不存在正整数解。
三、扩展欧几里得算法
如果a与p互质，求逆元的方法有很多，常见的有扩展欧几里得、线性求解、欧拉定理，如果满足某些条件，也可以使用费马小定理。
每种算法都可以通过编程来实现，这里给大家介绍一下使用扩展欧几里得方法手算的过程。
1. 算法简介
- 欧几里得算法
欧几里得算法也叫辗转相除法，相信大部分小伙伴在高中的时候就接触过，这个方法可以找到两个非负整数的最大公约数，在后面的求解过程中为大家具体演示。
- 扩展欧几里得
扩展欧几里得是欧几里得算法的扩展，可以在求出两个整数a、b最大公约数的同时，找到一对儿整数x、y(其中一个一般为负数)满足以下式子：
a x + b y = g c d ( a , b ) ax + by = gcd(a,b)ax+by=gcd(a,b)
结合上面的内容，如果两个数(a和p)是互质的，则gcd(a,p) = 1，也就有以下式子成立：
a x + p y = g c d ( a , p ) = 1 ax + py = gcd(a,p) = 1ax+py=gcd(a,p)=1
如果其中y是负数，那就和我们求解逆元素的等式相同了。
2. 求解过程
整个求解的过程就是使用辗转相除法求两个数的公约数，并且我们知道公约数的结果为1，所以一直计算到1为止即可。
- 例题1：a = 3,p = 17
首先使用大数除以小数，p / a：
2 = 17 − 3 ∗ 5 2 = 17 - 3 * 52=17−3∗5
接下来不断的用上式的除数去除以上式的余数，直到余数为1。
1 = 3 − 2 ∗ 1 1 = 3 - 2 * 11=3−2∗1
然后我们通过等式的代换就可以得到a与p的关系：
1 = 3 − ( 17 − 3 ∗ 5 ) ∗ 1 1 = 3 - (17 - 3 * 5) * 11=3−(17−3∗5)∗1
1 = 3 − 17 ∗ 1 + 3 ∗ 5 1 = 3 - 17 * 1 + 3 * 51=3−17∗1+3∗5
1 = 3 ∗ 6 − 17 ∗ 1 1 = 3 * 6 - 17 * 11=3∗6−17∗1
得到结果为6。
- 例题2：a = 5,p = 14
4 = 14 − 5 ∗ 2 4 = 14 - 5 * 24=14−5∗2
1 = 5 − 4 ∗ 1 1 = 5 - 4 * 11=5−4∗1
等号左侧得到1，继续进行等式代换：
1 = 5 − ( 14 − 5 ∗ 2 ) ∗ 1 1 = 5 - (14 - 5 * 2) * 11=5−(14−5∗2)∗1
1 = 5 − 14 ∗ 1 + 5 ∗ 2 1 = 5 - 14 * 1 + 5 * 21=5−14∗1+5∗2
1 = 5 ∗ 3 − 14 ∗ 1 1 = 5 * 3 - 14 * 11=5∗3−14∗1
得到结果为3。
3. 实用技巧
当数值较小时，可以通过较少的式子得到最终的结果，当数值较大时建议直接使用程序解决。以上两个例子都是通过两个式子就得到了结果，接下来通过一个例子和大家分享一个小技巧，也是一个可以直接使用的性质。
- 例题3：a = 5,p = 18
前面的步骤相同，使用辗转相除，会得到3个式子：
3 = 18 − 5 ∗ 3 3 = 18 - 5 * 33=18−5∗3
2 = 5 − 3 ∗ 1 2 = 5 - 3 * 12=5−3∗1
1 = 3 − 2 ∗ 1 1 = 3 - 2 * 11=3−2∗1
在代换时会发现一个问题，由于式子是奇数个，所以最后整理时a的系数为负：
1 = 3 − ( 5 − 3 ∗ 1 ) ∗ 1 1 = 3 - (5 - 3 * 1) * 11=3−(5−3∗1)∗1
1 = ( 18 − 5 ∗ 3 ) − ( 5 − ( 18 − 5 ∗ 3 ) ∗ 1 ) ∗ 1 1 = (18 - 5 * 3) - (5 - (18 - 5 * 3) * 1) * 11=(18−5∗3)−(5−(18−5∗3)∗1)∗1
1 = 18 − 5 ∗ 3 − 5 + 18 − 5 ∗ 3 1 = 18 - 5 * 3 - 5 + 18 - 5 * 31=18−5∗3−5+18−5∗3
1 = 18 ∗ 2 − 5 ∗ 7 1 = 18 * 2 - 5 * 71=18∗2−5∗7
当时得到这个结果小编一度以为自己做错了，因为如果将结果表示出来会是这个样子：
1 ≡ 5 ⋅ ( − 7 ) m o d 18 1 \equiv 5 \cdot (-7) \bmod 181≡5⋅(−7)mod18
但是利用两个数互质的性质以及最小公倍数，我们可以直接得到想要的结果：
1 ≡ 5 ⋅ ( − 7 ) m o d 18 ≡ 5 ⋅ ( 11 ) m o d 18 1 \equiv 5 \cdot (-7) \bmod 18 \equiv 5 \cdot (11) \bmod 181≡5⋅(−7)mod18≡5⋅(11)mod18
最后的结果为11，对于这个变换不理解的小伙伴可以查看文章结尾的视频，会进行较为详细的说明。
四、视频直达
视频地址：https://www.bilibili.com/video/bv1234y1m7Xs，喜欢的小伙伴儿一定要三连加关注哦~
扩展欧几里得求乘法逆元
写在结尾：作者力求做到将每个知识点细化，并且对于有关联的知识点都会使用传送门挂载链接。文章采用：“文字 + 配图 + 视频”的方式来进行展现，均是挤时间所作，希望看到这里能留下评论点个赞，略表支持！
