设
u
0
u_0
u0，
u
1
u_1
u1是给定的两个整数，
u
1
≠
0
u_1neq 0
u1=0，反复使用带余数除法：
u
0
=
q
0
u
1
+
u
2
,
0
<
u
2
<
∣
u
1
∣
,
u
1
=
q
1
u
2
+
u
3
,
0
<
u
3
<
u
2
,
u
2
=
q
2
u
3
+
u
4
,
0
<
u
4
<
u
3
,
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
begin{array}{ll} u_0=q_0u_1+u_2,&qquad 0
⋯
⋯
⋯
⋯
⋯
⋯
⋯
⋯
u
k
−
2
=
q
k
−
2
u
k
−
1
+
u
k
,
0
<
u
k
<
u
k
−
1
,
u
k
−
1
=
q
k
−
1
u
k
+
u
k
+
1
,
0
<
u
k
+
1
<
u
k
,
u
k
=
q
k
u
k
+
1
,
即
u
k
+
2
=
0.
(1)
begin{array}{ll} cdotscdotscdotscdots&qquad cdotscdotscdotscdots\ u_{k-2}=q_{k-2}u_{k-1}+u_k,&qquad 0
从倒数第二个式子开始，依次上推，可得
u
k
+
1
=
u
k
−
1
−
q
k
−
1
u
k
=
u
k
−
1
−
q
k
−
1
(
u
k
−
2
−
q
k
−
2
u
k
−
1
)
=
⋯
=
x
0
u
0
+
x
1
u
1
,
u_{k+1}=u_{k-1}-q_{k-1}u_k=u_{k-1}-q_{k-1}(u_{k-2}-q_{k-2}u_{k-1})=cdots =x_0u_0+x_1u_1,
uk+1=uk−1−qk−1uk=uk−1−qk−1(uk−2−qk−2uk−1)=⋯=x0u0+x1u1,
即
u
k
+
1
u_{k+1}
uk+1一定能表示成
u
0
u_0
u0和
u
1
u_1
u1的整系数线性组合
特别地，当
u
0
u_0
u0与
u
1
u_1
u1互素时，存在整数
x
x
x，
y
y
y，使得
x
u
0
+
y
u
1
=
u
k
+
1
=
1.
xu_0+yu_1=u_{k+1}=1.
xu0+yu1=uk+1=1.
从而
1
≡
x
u
0
+
y
u
1
≡
x
u
0
(
m
o
d
u
1
)
.
1equiv xu_0+yu_1equiv xu_0pmod{u_1}.
1≡xu0+yu1≡xu0(modu1).
即
x
x
x是
u
0
u_0
u0对模
u
1
u_1
u1的逆
当 u 0 u_0 u0与 u 1 u_1 u1互素时，欧几里得算法给出了一个 u 0 − 1 ( m o d u 1 ) u_0^{-1}pmod{u_1} u0−1(modu1)的构造
事实上，对于
(
1
)
(1)
(1)过程中任何一个
u
j
u_j
uj，都存在整数
x
j
x_j
xj，
y
j
y_j
yj，使得
x
j
u
0
+
y
j
u
1
=
u
j
.
(2)
x_j u_0+y_j u_1=u_j. tag{2}
xju0+yju1=uj.(2)
再设有
x
j
+
1
u
0
+
y
j
+
1
u
1
=
u
j
+
1
,
(3)
x_{j+1}u_0+y_{j+1}u_1=u_{j+1},tag{3}
xj+1u0+yj+1u1=uj+1,(3)
由
u
j
=
q
j
u
j
+
1
+
u
j
+
2
u_{j}=q_ju_{j+1}+u_{j+2}
uj=qjuj+1+uj+2，
(
2
)
−
q
j
(
3
)
(2)-q_j(3)
(2)−qj(3)得
(
x
j
−
q
j
x
j
+
1
)
u
0
+
(
y
j
−
q
j
y
j
+
1
)
u
1
=
u
j
+
2
.
(x_j-q_jx_{j+1})u_0+(y_j-q_jy_{j+1})u_1=u_{j+2}.
(xj−qjxj+1)u0+(yj−qjyj+1)u1=uj+2.
从而有递推关系
x
j
+
2
=
x
j
−
q
j
x
j
+
1
,
y
j
+
2
=
y
j
−
q
j
y
j
+
1
.
begin{array}{l} x_{j+2}=x_j-q_jx_{j+1},\ y_{j+2}=y_j-q_jy_{j+1}. end{array}
xj+2=xj−qjxj+1,yj+2=yj−qjyj+1.
由
x
0
u
0
+
y
0
u
1
=
u
0
x_0u_0+y_0u_1=u_0
x0u0+y0u1=u0及
x
1
u
0
+
y
1
u
1
=
u
1
x_1u_0+y_1u_1=u_1
x1u0+y1u1=u1，设初值
x
0
=
1
,
y
0
=
0
,
x
1
=
0
,
y
1
=
1.
begin{array}{l} x_0=1,quad y_0=0,\ x_1=0,quad y_1=1. end{array}
x0=1,y0=0,x1=0,y1=1.
由此即可求得
u
0
u_0
u0对模
u
1
u_1
u1的逆
def gcd(a, b):
#使用欧几里得算法返回a和b的最大公约数
while a != 0:
a, b = b % a, a
return b
def findModInverse(a, m):
#返回a%m的逆
if gcd(a, m) != 1:
return None #如果a,m不互素，不进行求逆
u1, u2, u3 = 1, 0, a
v1, v2, v3 = 0, 1, m
while v3 != 0:
q = u3 // v3
v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m
参考资料
潘承洞,潘承彪.初等数论(第三版):北京大学出版社
阿尔·斯威加特(美).Python密码学编程(第2版):人民邮电出版社
