文章目录 0. 概述输入规模和算术计算的代价 1. 基础数论概念1.1 整除性和约数1.2 素数和合数1.3 除法定理、余数和等模1.4 公约数和最大公约数1.5 互质数1.6 唯一因子分解定理 2. 最大公约数2.1 欧几里得算法2.2 欧几里得算法的运行时间欧几里得算法的扩展形式 3. 模运算3.1 有限群3.2 由模加法和模乘法所定义的群3.2.1 模 n n n 加法群3.2.2 模 n n n 乘法群 3.3 子群3.4 由一个元素生成的子群 4. 求解模线性方程5. 中国余数定理6. 元素的幂7. RSA公钥加密系统8. 素数测试9. 整数的因子分解 0. 概述参考算导第31章 数论算法
数论曾经作为一种虽然优美、但没什么用处的纯数学学科。如今，数论算法 number-theoretic algorithms 却得到了广泛的使用。这很大程度归功于人们发明了「基于大素数的加密方案」。这些方案是可行的，因为我们能快速计算大素数 find large primes easily ；而且，这些方案是安全的，因为我们不知道如何高效将合数因子分解为大素数乘积（或求解相关问题，如计算离散对数）factor the product of large primes (or solve related problems, such as computing discrete logarithms) efficiently 。这里介绍一些数论知识、以及相关的算法，它们是上文这类应用的基础。
divisibility, modular equivalence, and unique factorization 。（算导31.2节）再研究世界上最古老算法之一的欧几里得算法，它用于计算两个整数的最大公约数。（算导31.3节）回顾模运算的概念。（算导31.4节）研究整数
a
a
a 的倍数模
n
n
n 所得的结果集合 the set of multiples of a given number a, modulo n ，并阐述如何用欧几里得算法求等式
a
x
≡
b
(
m
o
d
n
)
ax \equiv b\ (\bmod\ n)
ax≡b (mod n) 。（算导31.5节）再介绍中国余数定理。（算导31.6节）考虑整数
a
a
a 的幂模
n
n
n powers of a given number a, modulo n ，描述反复平方算法 repeated-squaring algorithm ，用于在已知
a
,
b
,
n
a, b, n
a,b,n 的情况下高效计算
a
b
m
o
d
n
a^b \bmod n
abmodn 。这一运算是高效素数检测和许多现代密码学内容的核心部分。（算导31.7节）描述RSA公钥加密系统。（算导31.8节）讨论一种随机性素数测试方法，该测试可用于高效地查找大素数，这正是为RSA加密系统创建密钥所必须的。（算导31.9节）回顾一个简单而有效的小整数因数分解启发式算法。有趣的是，由于RSA的安全性依赖于大整数因子分解的难度，人们恐怕更希望因子分解是一个无多项式解法的难题。
输入规模和算术计算的代价
由于我们处理的对象是大整数，我们需要调整「对于输入规模大小和基本算术运算代价的理解」。这里，一个“大输入”通常指一个包含“大整数”的输入，而不是包含“很多整数”的输入（像排序问题那样）。因此，我们利用输入所需的位数 number of bits 来度量输入的大小，而不仅仅是输入中整数的数目。给定
k
k
k 个整数输入
a
1
,
a
2
,
…
,
a
k
a_1, a_2, \dots, a_k
a1,a2,…,ak ，如果算法可以在
log
a
1
,
log
a
2
,
…
,
log
a
k
\log a_1, \log a_2, \dots, \log a_k
loga1,loga2,…,logak 的多项式时间内完成，则该算法称为多项式时间算法。也就是说，多项式是基于「二进制编码后的输入长度」polynomial in the lengths of its binary-encoded inputs 。
其他时候，将基本算术运算（乘法、除法或者计算余数）视为只耗费单位时间的原语 *** 作是非常方便的。通过计算算法中包含的这类算术运算的数目，我们就有一个基准、用来合理评估算法在计算机上的实际运算时间。然而，当输入很大时，基本运算也会变得耗时。因此，用数论算法所需的位运算 bit operations 数目作为基准（来衡量算法的时间代价）将更加方便且合适。在此模型中，将两个
β
\beta
β 位整数用常规方法相乘需要
Θ
(
β
2
)
\Theta(\beta^2)
Θ(β2) 次位运算。同样，用最朴素方法计算一个
β
\beta
β 位整数除以另一个较短整数的商或余数，也需要耗时
Θ
(
β
2
)
\Theta(\beta^2)
Θ(β2)（见算导练习31.1-12）。如今，更快的计算方法已经出现。例如，一个简单的分治算法，可以在两个
β
\beta
β 位整数相乘的问题上达到
Θ
(
β
log
3
)
\Theta(\beta^{\log 3})
Θ(βlog3) 的运行时间，而已知最快的算法则只需要
Θ
(
β
log
β
log
log
β
)
\Theta( \beta \log \beta \log \log \beta)
Θ(βlogβloglogβ) 的运行时间。然而在实际问题中，
Θ
(
β
2
)
\Theta(\beta^2)
Θ(β2) 的算法往往效果最好，我们也将以该界作为算法分析的基准。
我们将既使用「算法所需的算术运算的数目」，也使用「其所需位运算的数目」来分析算法。
1. 基础数论概念
本节将简单回顾，基础数论中关于整数集 Z = { … , − 2 , − 1 , 0 , 1 , 2 , … } \Z = \{ \dots, -2, -1, 0, 1, 2, \dots \} Z={…,−2,−1,0,1,2,…} 和自然数集 N = { 0 , 1 , 2 , … } \N = \{ 0, 1, 2, \dots \} N={0,1,2,…} 的一些概念。
1.1 整除性和约数一个整数可以被另外一个整数整除 divisible ，是数论中的一个关键概念。
若存在某个整数
k
k
k ，使得
a
=
k
d
a = kd
a=kd ，则称
d
d
d 整除
a
a
a（读作 d divides a ），写成
d
∣
a
d \mid a
d∣a（也有
k
∣
a
k \mid a
k∣a ）。如果不存在这样的整数
k
k
k ，则称
d
d
d 不能整除
a
a
a ，写成
d
∤
a
d \not { \mid}\ a
d∣ a 。如果
d
∣
a
d \mid a
d∣a ，则称
a
a
a 是
d
d
d 的倍数 multiple 。如果
d
∣
a
d \mid a
d∣a 且
d
≥
0
d \ge 0
d≥0 ，则称
d
d
d 是
a
a
a 的约数 divisor 。
注意，
d
∣
a
d\mid a
d∣a 当且仅当
−
d
∣
a
-d \mid a
−d∣a ，即
a
a
a 的任何约数的负数同样可以整除
a
a
a 。因此不失一般性，可定义约数为非负数。非零整数
a
a
a 的约数应至少为
1
1
1 ，且不会大于
∣
a
∣
|a|
∣a∣ 。例如，
24
24
24 的约数是
1
,
2
,
3
,
4
,
6
,
8
,
12
,
24
1, 2, 3, 4, 6, 8, 12, 24
1,2,3,4,6,8,12,24 。任何（正）整数
a
a
a 均可被平凡约数 trivial divisors ——
1
1
1 和其自身
a
a
a 所整除。整数
a
a
a 的非平凡约数称为
a
a
a 的因子 factors 。例如，
20
20
20 的因子是
2
,
4
,
5
,
10
2, 4, 5, 10
2,4,5,10 。
我们不难发现（无意义！），任何整数（包括 0 0 0 本身）均可整除 0 0 0（因为对任何整数 d d d 都有 0 = 0 × d 0 = 0 \times d 0=0×d ）。而且，如果 a > 0 a > 0 a>0 且 d ∣ a d \mid a d∣a ，那么 ∣ d ∣ ≤ ∣ a ∣ |d | \le |a| ∣d∣≤∣a∣（实际上 a < 0 a <0 a<0 且 d ∣ a d \mid a d∣a 时也成立）。
1.2 素数和合数如果一个整数
a
>
1
a > 1
a>1 、且只能被平凡约数（
1
1
1 和它自身）所整除，则这个数是素数 prime number 。素数有许多特殊的性质，它在数论中也扮演着十分重要的角色。前
20
20
20 个素数按序排列如下（算导31.1-2要求证明存在无穷多个素数）：
2
,
3
,
5
,
7
,
11
,
13
,
17
,
19
,
23
,
29
,
31
,
37
,
41
,
43
,
47
,
53
,
59
,
61
,
67
,
71
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,\ 31, 37, 41, 43, 47, 53, 59, 61, 67, 71
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71
如果一个整数
a
>
1
a > 1
a>1 且不是素数，则称之为合数 composite number 。例如，
39
39
39 是一个合数，因为
3
∣
39
3 \mid 39
3∣39 。称整数
1
1
1 为基本单位 unit ，并且它既不是素数也不是合数。同样，整数
0
0
0 和所有负整数既不是素数也不是合数 the integer 0 and all negative integers are neither prime nor composite 。
给定一个整数
n
n
n ，我们可以把整数集划分为
n
n
n 的倍数和非
n
n
n 倍数两部分。通过计算非
n
n
n 倍数除以
n
n
n 的余数，可以对非
n
n
n 倍数进行有效分类，许多数论理论正是基于改进这种划分（来改进对
n
n
n 的倍数和非
n
n
n 倍数的划分？）Much number theory is based upon refining this partition 。下面的定理给出该改进的理论基础。这里忽略了其证明（参见算导 Niven 和 Zuckerman 的证明）。
定理31.1（除法定理 Division theorem ）对于任何整数
a
a
a 和任何正整数
n
n
n ，存在唯一整数 unique integers
q
q
q 和
r
r
r ，满足
0
≤
r
<
n
0 \le r < n
0≤r<n 且
a
=
n
q
+
r
a = nq + r
a=nq+r 。
称正整数
n
n
n 为模数 modulo ，值
q
=
⌊
a
/
n
⌋
q = \lfloor a / n \rfloor
q=⌊a/n⌋ 为除法的商 quotient ，值
r
=
a
m
o
d
n
r = a \bmod n
r=amodn 为除法的余数 remainder or residue（限定
n
n
n 为正整数且
0
≤
r
<
n
0 \le r < n
0≤r<n 时
q
,
r
q, r
q,r 是唯一的）。
n
∣
a
n \mid a
n∣a 当且仅当
a
m
o
d
n
=
0
a \bmod n = 0
amodn=0 。根据整数模
n
n
n 的余数（因为是唯一的！），我们可以将所有整数划分为
n
n
n 个等价类 equivalence class 。包括整数
a
a
a 的模
n
n
n 等价类为：
[
a
]
n
=
{
a
+
k
n
∣
k
∈
Z
}
[a]_n = \{ a + k n \mid k \in \Z\}
[a]n={a+kn∣k∈Z}
例如， [ 3 ] 7 = { … , − 11 , − 4 , 3 , 10 , 17 , … } [3]_7 = \{ \dots, -11, -4, 3, 10, 17, \dots \} [3]7={…,−11,−4,3,10,17,…} ，这个集合同时也可以表示为 [ − 4 ] 7 , [ 10 ] 7 [-4]_7, [10]_7 [−4]7,[10]7 。
a
∈
[
b
]
n
a \in [b]_n
a∈[b]n 和
a
≡
b
(
m
o
d
n
)
a \equiv b\ (\bmod\ n)
a≡b (mod n) 是等价的。所有这类等价类的集合是：
Z
n
=
{
[
a
]
n
∣
0
≤
a
≤
n
−
1
}
(31.1)
\Z_n = \{ [a]_n \mid 0 \le a \le n - 1\} \tag{31.1}
Zn={[a]n∣0≤a≤n−1}(31.1) 当看到
Z
n
=
{
0
,
1
,
2
,
…
,
n
−
1
}
(31.2)
\Z_n = \{ 0, 1, 2, \dots, n - 1\} \tag{31.2}
Zn={0,1,2,…,n−1}(31.2) 这个定义时，按照式
(
31.1
)
(31.1)
(31.1) 理解即可：
0
0
0 代表
[
0
]
n
[0]_n
[0]n ，
1
1
1 代表
[
1
]
n
[1]_n
[1]n 等等，即用每个等价类最小的非负元素来表示等价类。然而，我们应该记住相应的等价类。例如，在说
−
1
-1
−1 是
Z
n
\Z_n
Zn 的一个元素时，实际上指的是
[
n
−
1
]
n
[n - 1]_n
[n−1]n ，因为
−
1
≡
n
−
1
(
m
o
d
n
)
-1 \equiv n - 1\ (\bmod \ n)
−1≡n−1 (mod n) 。
如果 d d d 是 a a a 的约数并且 d d d 也是 b b b 的约数，则 d d d 是 a a a 与 b b b 的公约数（为非负整数）。例如， 30 30 30 的约数包括 1 , 2 , 3 , 5 , 6 , 10 , 15 , 30 1, 2, 3, 5, 6, 10, 15, 30 1,2,3,5,6,10,15,30 ，因此 24 24 24 与 30 30 30 的公约数为 1 , 2 , 3 , 6 1, 2, 3, 6 1,2,3,6 。需要注意的是， 1 1 1 是任意两个整数的公约数。
公约数的一条重要性质是： d ∣ a 且 d ∣ b 蕴 含 着 d ∣ ( a + b ) 且 d ∣ ( a − b ) (31.3) d \mid a 且 d \mid b蕴含着 d \mid (a + b) 且 d \mid (a - b) \tag{31.3} d∣a且d∣b蕴含着d∣(a+b)且d∣(a−b)(31.3)
更一般地，对任意整数 x , y x, y x,y 有： d ∣ a 且 d ∣ b 蕴 含 着 d ∣ ( a x + b y ) (31.4) d \mid a 且 d \mid b 蕴含着 d \mid (ax + by) \tag{31.4} d∣a且d∣b蕴含着d∣(ax+by)(31.4)
并且，如果 a ∣ b a \mid b a∣b ，那么 ∣ a ∣ ≤ ∣ b ∣ |a | \le |b| ∣a∣≤∣b∣ 或者 b = 0 b = 0 b=0 ，而这说明： a ∣ b 且 b ∣ a 蕴 含 着 a = ± b (31.5) a \mid b 且 b \mid a 蕴含着 a = \pm b \tag{31.5} a∣b且b∣a蕴含着a=±b(31.5)
两个不同时为
0
0
0 的整数
a
a
a 与
b
b
b 的公约数中最大的，称为最大公约数 greatest common divisor ，记为
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) 。例如，
g
c
d
(
24
,
30
)
=
6
,
g
c
d
(
5
,
7
)
=
1
,
g
c
d
(
0
,
9
)
=
9
gcd(24, 30) = 6,\ gcd(5, 7) = 1,\ gcd(0, 9) = 9
gcd(24,30)=6, gcd(5,7)=1, gcd(0,9)=9 。如果
a
a
a 与
b
b
b 不同时为
0
0
0 ，则
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) 是一个在
1
1
1 与
min
(
∣
a
∣
,
∣
b
∣
)
\min (|a| , |b|)
min(∣a∣,∣b∣) 之间的整数。定义
g
c
d
(
0
,
0
)
=
0
gcd(0, 0) = 0
gcd(0,0)=0 ，该定义是使
g
c
d
gcd
gcd 函数的基本性质（如下面的等式
(
31.9
)
(31.9)
(31.9) ）普遍成立必不可少的。
下列性质是 g c d gcd gcd 函数的基本性质： g c d ( a , b ) = g c d ( b , a ) ( 31.6 ) g c d ( a , b ) = g c d ( − a , b ) ( 31.7 ) g c d ( a , b ) = g c d ( ∣ a ∣ , ∣ b ∣ ) ( 31.8 ) g c d ( a , 0 ) = ∣ a ∣ ( 31.9 ) g c d ( a , k a ) = ∣ a ∣ 对 任 意 k ∈ Z ( 31.10 ) \begin{aligned} &gcd(a, b) = gcd(b, a) \qquad \qquad\qquad \qquad &(31.6) \ &gcd(a, b) = gcd(-a, b) \qquad \qquad\qquad \qquad &(31.7) \ &gcd(a, b) = gcd(|a|, |b|) \qquad \qquad\qquad \qquad &(31.8) \ &gcd(a, 0) = |a| \qquad \qquad\qquad \qquad &(31.9) \ &gcd(a, ka) = |a| \ 对任意k \in \Z \qquad \qquad\qquad \qquad &(31.10) \ \end{aligned} gcd(a,b)=gcd(b,a)gcd(a,b)=gcd(−a,b)gcd(a,b)=gcd(∣a∣,∣b∣)gcd(a,0)=∣a∣gcd(a,ka)=∣a∣ 对任意k∈Z(31.6)(31.7)(31.8)(31.9)(31.10)
下面的定理给出了 g c d ( a , b ) gcd(a, b) gcd(a,b) 的另外一个有用特征。
定理31.2 如果任意整数
a
,
b
a, b
a,b 不都为
0
0
0 ，则
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) 是
a
,
b
a, b
a,b 的线性组合集
{
a
x
+
b
y
∣
x
,
y
∈
Z
}
\{ ax + by \mid x, y \in \Z\}
{ax+by∣x,y∈Z} 中的最小正元素。
证明：设
s
s
s 是
a
,
b
a, b
a,b 的线性组合集中的最小正元素，并且对某个
x
,
y
∈
Z
x, y \in \Z
x,y∈Z ，有
s
=
a
x
+
b
y
s = ax+by
s=ax+by 。设
q
=
⌊
a
/
s
⌋
q = \lfloor a / s \rfloor
q=⌊a/s⌋ ，则式
(
3.8
)
(3.8)
(3.8) 说明：
a
m
o
d
s
=
a
−
q
s
=
a
−
q
(
a
x
+
b
y
)
=
a
(
1
−
q
x
)
+
b
(
−
q
y
)
a \bmod s = a - qs = a - q(ax + by) = a(1 - qx) + b(-qy)
amods=a−qs=a−q(ax+by)=a(1−qx)+b(−qy) 因此，
a
m
o
d
s
a\bmod s
amods 也是
a
,
b
a, b
a,b 的一个线性组合。但由于
0
≤
a
m
o
d
s
<
s
0 \le a \bmod s < s
0≤amods<s ，我们可得
a
m
o
d
s
=
0
a \bmod s = 0
amods=0 ，因为
s
s
s 是这个线性组合中的最小正数。因此有
s
∣
a
s \mid a
s∣a 。类似地，可得到
s
∣
b
s \mid b
s∣b 。因此，
s
s
s 是
a
,
b
a, b
a,b 的公约数，所以
g
c
d
(
a
,
b
)
≥
s
gcd(a, b) \ge s
gcd(a,b)≥s 。
因为 g c d ( a , b ) gcd(a, b) gcd(a,b) 能同时整除 a a a 和 b b b ，并且 s s s 是 a a a 与 b b b 的一个线性组合，所以由式 ( 31.4 ) (31.4) (31.4) 可知 g c d ( a , b ) ∣ s gcd(a, b) \mid s gcd(a,b)∣s 。但由于 g c d ( a , b ) ∣ s gcd(a, b) \mid s gcd(a,b)∣s 和 s > 0 s > 0 s>0 ，因此 g c d ( a , b ) ≤ s gcd(a, b) \le s gcd(a,b)≤s 。
将上面已证明的 g c d ( a , b ) ≥ s gcd(a, b) \ge s gcd(a,b)≥s 与 g c d ( a , b ) ≤ s gcd(a, b) \le s gcd(a,b)≤s 结合起来，得到 g c d ( a , b ) = s gcd(a, b) = s gcd(a,b)=s ，因此证明了 s s s 是 a a a 与 b b b 的最大公约数。 ■ \blacksquare ■
推论31.3 对任意整数
a
,
b
a, b
a,b ，如果
d
∣
a
d \mid a
d∣a 且
d
∣
b
d\mid b
d∣b ，则
d
∣
g
c
d
(
a
,
b
)
d \mid gcd(a, b)
d∣gcd(a,b) 。
证明：根据定理31.2，
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) 是
a
a
a 与
b
b
b 的一个线性组合（考虑长为
a
a
a 、宽为
b
b
b 的一块木板？），所以由式
(
31.4
)
(31.4)
(31.4) 可知，该推论成立。
■
\blacksquare
■
推论31.4 对所有整数
a
,
b
a, b
a,b 以及任意非负整数
n
n
n ，有：
g
c
d
(
a
n
,
b
n
)
=
n
×
g
c
d
(
a
,
b
)
gcd(an, bn) = n\times gcd(a, b)
gcd(an,bn)=n×gcd(a,b)
证明：如果
n
=
0
n = 0
n=0 ，该推论显然成立。如果
n
>
0
n > 0
n>0 ，则
g
c
d
(
a
n
,
b
n
)
gcd(an, bn)
gcd(an,bn) 是集合
{
a
n
x
+
b
n
y
∣
x
,
y
∈
Z
}
\{ anx +bny \mid x , y \in \Z\}
{anx+bny∣x,y∈Z} 的最小正元素，即集合
{
a
x
+
b
y
∣
x
,
y
∈
Z
}
\{ ax + by\mid x, y\in \Z \}
{ax+by∣x,y∈Z} 中最小正元素（即
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) ）的
n
n
n 倍 。
■
\blacksquare
■
推论31.5 对于任意正整数
n
,
a
,
b
n, a, b
n,a,b ，如果
n
∣
a
b
n \mid ab
n∣ab 且
g
c
d
(
a
,
n
)
=
1
gcd(a, n) = 1
gcd(a,n)=1 ，则
n
∣
b
n \mid b
n∣b 。
证明：证明过程见练习31.1-5。
■
\blacksquare
■
如果两个整数
a
,
b
a, b
a,b 只有公约数
1
1
1 ，即
g
c
d
(
a
,
b
)
=
1
gcd(a, b) = 1
gcd(a,b)=1 ，则
a
,
b
a, b
a,b 称为互质数 relatively prime 。例如，
8
,
15
8, 15
8,15 是互质数，因为
8
8
8 的约数为
1
,
2
,
4
,
8
1, 2, 4, 8
1,2,4,8 、而
15
15
15 的约数为
1
,
3
,
5
,
15
1, 3, 5, 15
1,3,5,15 。下面的定理说明，如果两个整数分别与一个整数
p
p
p 为互质数，则其积与
p
p
p 互质。
定理31.6 对任意整数
a
,
b
,
p
a, b, p
a,b,p ，如果
g
c
d
(
a
,
p
)
=
1
gcd(a, p) = 1
gcd(a,p)=1 且
g
c
d
(
b
,
p
)
=
1
gcd(b, p) = 1
gcd(b,p)=1 ，则
g
c
d
(
a
b
,
p
)
=
1
gcd(ab, p) = 1
gcd(ab,p)=1 。
证明：由定理31.2可知，存在整数
x
,
y
,
x
′
,
y
′
x, y, x', y'
x,y,x′,y′ 满足：
a
x
+
p
y
=
1
b
x
′
+
p
y
′
=
1
ax + py = 1 \ bx' + py' = 1
ax+py=1bx′+py′=1 把上面两个等式两边分别相乘，经过整理得
a
b
(
x
x
′
)
+
p
(
y
b
x
′
+
y
′
a
x
+
p
y
y
′
)
=
1
ab(xx') + p( ybx' + y'ax + pyy') = 1
ab(xx′)+p(ybx′+y′ax+pyy′)=1 因为
1
1
1 是
a
b
ab
ab 与
p
p
p 的一个正线性组合，所以应用定理31.2就可以证明结论。
■
\blacksquare
■
对于整数
n
1
,
n
2
,
…
,
n
k
n_1, n_2, \dots, n_k
n1,n2,…,nk ，如果对任何
i
≠
j
i \ne j
i=j 都有
g
c
d
(
n
i
,
n
j
)
=
1
gcd(n_i, n_j ) = 1
gcd(ni,nj)=1 ，则称整数
n
1
,
n
2
,
…
,
n
k
n_1, n_2, \dots, n_k
n1,n2,…,nk 两两互质 pairwise relatively prime 。
下面的结论说明了，关于素数整除性 divisibility by primes 的一个基本而重要的事实。
定理31.7 对所有素数
p
p
p 和所有整数
a
,
b
a, b
a,b ，如果
p
∣
a
b
p \mid ab
p∣ab ，则
p
∣
a
p \mid a
p∣a 或
p
∣
b
p \mid b
p∣b（或两者都成立）。
证明 采用反证法，假设
p
∣
a
b
p \mid ab
p∣ab ，但
p
∤
a
p\not { \mid }\ a
p∣ a 并且
p
∤
b
p \not{\mid}\ \ b
p∣ b 。因此
g
c
d
(
a
,
p
)
=
1
gcd(a, p) = 1
gcd(a,p)=1 且
g
c
d
(
b
,
p
)
=
1
gcd(b, p)= 1
gcd(b,p)=1 。这是因为
p
p
p 的约数只有
1
,
p
1, p
1,p ，又因为假设
a
,
b
a, b
a,b 都不能被
p
p
p 整除（即
p
p
p 不是
a
,
b
a, b
a,b 的约数）。由定理31.6可知，
g
c
d
(
a
b
,
p
)
=
1
gcd(ab, p) =1
gcd(ab,p)=1 ；由假设
p
∣
a
b
p \mid ab
p∣ab（且
p
p
p 为素数）可知
g
c
d
(
a
b
,
p
)
=
p
gcd(ab, p) = p
gcd(ab,p)=p ，于是产生矛盾，从而证明定理成立。
从定理31.7可知，任意一个合数的素因数分解式是唯一的。例如，数 6000 6000 6000 可以唯一分解为 2 4 ⋅ 3 ⋅ 5 3 2^4 \cdot 3 \cdot 5^3 24⋅3⋅53 。
定理31.8（唯一因子分解定理 Unique factorization ）合数
a
a
a 仅能以一种方式写成如下乘积形式：
a
=
p
1
e
1
p
2
e
2
…
p
r
e
r
a = p_1^{e_1} p_2^{e_2} \dots p_r^{e_r}
a=p1e1p2e2…prer 其中
p
i
p_i
pi 为素数，
p
1
<
p
2
<
⋯
<
p
r
p_1 < p_2 < \dots < p_r
p1<p2<⋯<pr ，且
e
i
e_i
ei 为正整数。
证明：过程见（算导练习31.1-11）。
2. 最大公约数
在本节中，我们将描述高效计算「两个整数最大公约数」的欧几里得算法。在对其运行时间进行分析的过程中，我们将发现它与斐波那契数存在着惊人联系，由此产生欧几里得算法最坏情况下的输入。本节中，我们仅对非负整数进行讨论。由式 ( 31.8 ) g c d ( a , b ) = g c d ( ∣ a ∣ , ∣ b ∣ ) (31.8)\ \ gcd(a, b) = gcd(|a| , |b|) (31.8) gcd(a,b)=gcd(∣a∣,∣b∣) 可知， 这一限制是有道理的。
原则上讲，可以根据
a
,
b
a, b
a,b 的素因子分解，求出正整数
a
a
a 和
b
b
b 的最大公约数
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) 。的确，如果
a
=
p
1
e
1
p
2
e
2
…
p
r
e
r
(31.11)
a = p_1^{e_1} p_2 ^{e_2} \dots p_r ^{e_r} \tag{31.11}
a=p1e1p2e2…prer(31.11)
b
=
p
1
f
2
p
2
f
2
…
p
r
f
r
(31.12)
b = p_1^{f_2} p_2^{f_2} \dots p_r^{f_r} \tag{31.12}
b=p1f2p2f2…prfr(31.12) 其中使用了零指数，从而使得素数集合
p
1
,
p
2
,
…
,
p
r
p_1, p_2, \dots, p_r
p1,p2,…,pr 对于
a
,
b
a, b
a,b 相同。正如（算导练习31.2-1要求）证明的，
g
c
d
(
a
,
b
)
=
p
1
min
(
e
1
,
f
1
)
p
2
min
(
e
2
,
f
2
)
⋯
p
r
min
(
e
r
,
f
r
)
(31.13)
gcd(a, b) = p_1^{\min(e_1, f_1) } p_2 ^{\min(e_2, f_2) } \cdots p_r^{\min(e_r, f_r)} \tag{31.13}
gcd(a,b)=p1min(e1,f1)p2min(e2,f2)⋯prmin(er,fr)(31.13) 在（算导31.9节）说明，目前已知的最好的因子分解算法，也不能达到多项式运行时间（存在量子计算机的因子分解算法 Shor's Algorithm ）。因此，利用这种方法来计算最大公约数，不大可能获得高效率。
计算最大公约数的欧几里得算法，基于如下定理。
定理31.9（GCD递归定理 GCD recursion theorem ）对任意非负整数
a
a
a 和任意正整数
b
b
b ：
g
c
d
(
a
,
b
)
=
g
c
d
(
b
,
a
m
o
d
b
)
gcd(a, b) = gcd(b, a \bmod b)
gcd(a,b)=gcd(b,amodb)
证明：下面将证明
g
c
d
(
a
,
b
)
gcd(a, b)
gcd(a,b) 与
g
c
d
(
b
,
a
m
o
d
b
)
gcd(b, a\bmod b)
gcd(b,amodb) 可以互相整除，这样由等式
(
31.5
)
(31.5)
(31.5) 可知，它们一定相等（因为它们都是非负整数）。
欧几里得（公元前300年）的几何原本描述了下列 g c d gcd gcd 算法，实际上这一算法出现的时间可能还要早些。我们将其描述为一个由定理31.9直接得到的递归程序，其输入 a , b a, b a,b 都是任意非负整数。
EUCLID(A, B)
if b == 0
return a
else return EUCLID(b, a mod b)
下面举例说明 EUCLID 的运行过程。考虑
g
c
d
(
30
,
21
)
gcd(30, 21)
gcd(30,21) 的计算过程：EUCLID(30, 21) = EUCLID(21, 9) = EUCLID(9, 3)= EUCLID(3, 0) = 3 。该计算过程三次递归调用了 EUCLID 。
过程 EUCLID 的正确性，可以从定理31.9以及下列性质推出：如果算法在第二行返回
a
a
a ，则
b
=
0
b = 0
b=0 。因此由式
(
31.9
)
(31.9)
(31.9) 可知，
g
c
d
(
a
,
b
)
=
g
c
d
(
a
,
0
)
=
a
gcd(a, b) = gcd(a, 0) = a
gcd(a,b)=gcd(a,0)=a 。因为在递归调用的过程中，第二个参数的值单调递减且始终非负，所以算法不可能无限递归下去。因此，EUCLID 总能终止、并求出正确答案。
下面分析 EUCLID 算法在最坏情况下的运行时间，我们把它看成是「输入
a
,
b
a, b
a,b 的大小的函数」。不失一般性，设
a
>
b
≥
0
a > b \ge 0
a>b≥0 。为了确定这个假设的合理性，注意如果
b
>
a
≥
0
b > a \ge 0
b>a≥0 ，则 EUCLID(a, b) 会立即递归调用 EUCLID(b, a) ，即如果第一个自变量小于第二个自变量，则 EUCLID 进行一次递归调用以交换两个自变量、然后继续执行。类似地，如果
b
=
a
>
0
b = a > 0
b=a>0 ，则过程在进行一次递归调用后就终止执行，因为
a
m
o
d
b
=
0
a \bmod b = 0
amodb=0 。
过程 EUCLID 的运行时间与其递归调用的次数成正比。在我们的分析过程中，利用了由递归式
(
3.22
)
(3.22)
(3.22) 定义的斐波那契数
F
k
F_k
Fk 。
引理31.10 如果
a
>
b
≥
1
a > b \ge 1
a>b≥1 并且 EUCLID(a, b) 执行了
k
≥
1
k \ge 1
k≥1 次递归调用，则
a
≥
F
k
+
2
,
b
≥
F
k
+
1
a \ge F_{k+2}, b \ge F_{k+1}
a≥Fk+2,b≥Fk+1 。
证明：通过对
k
k
k 进行归纳来证明引理。作为归纳的基础，设
k
=
1
k = 1
k=1 ，则
b
≥
1
=
F
2
b \ge 1 = F_2
b≥1=F2 。又由于
a
>
b
a > b
a>b ，必有
a
≥
2
=
F
3
a \ge 2 = F_3
a≥2=F3 。因为
b
>
(
a
m
o
d
b
)
b > (a \bmod b)
b>(amodb) ，即在每次调用中，第一个变量严格大于第二个变量，因此对每次递归调用，假设
a
>
b
a > b
a>b 成立。
假设执行
k
−
1
k - 1
k−1 次递归调用时引理成立。下面将证明若执行
k
k
k 次递归调用，引理同样成立。因为
k
>
0
k > 0
k>0 ，且我们有
b
>
0
b > 0
b>0 ，并且 EUCLID(a, b) 递归调用 EUCLID(b, a mod b) ，该函数（指 EUCLID(b, a mod b)）依次进行了
k
−
1
k - 1
k−1 次递归调用。归纳假设蕴含
b
≥
F
k
+
1
b \ge F_{k+1}
b≥Fk+1（因此也就证明了引理的一部分），且
a
m
o
d
b
≥
F
k
a \bmod b \ge F_k
amodb≥Fk 。我们有：
b
+
(
a
m
o
d
b
)
=
b
+
(
a
−
b
⌊
a
/
b
⌋
)
≤
a
b + (a \bmod b)= b+(a - b\lfloor a / b \rfloor) \le a
b+(amodb)=b+(a−b⌊a/b⌋)≤a 因为
a
>
b
>
0
a > b > 0
a>b>0 蕴含
⌊
a
/
b
⌋
≥
1
\lfloor a / b\rfloor \ge 1
⌊a/b⌋≥1 。所以
a
≥
b
+
(
a
m
o
d
b
)
≥
F
k
+
1
+
F
k
=
F
k
+
2
a \ge b + (a \bmod b) \ge F_{k+1} +F_k = F_{k+2}
a≥b+(amodb)≥Fk+1+Fk=Fk+2 。
■
\blacksquare
■
下面的定理是这个引理的一个直接推论（逆否命题？）。
定理31.11（
L
a
m
e
ˊ
Lam\acute{e}
Lameˊ 定理）对任意整数
k
≥
1
k \ge 1
k≥1 ，如果
a
>
b
≥
1
a > b \ge 1
a>b≥1 且
b
<
F
k
+
1
b < F_{k +1}
b<Fk+1 ，则 EUCLID(a, b) 的递归调用次数少于
k
k
k 次。
证明：欲证明定理31.11中的上界是最优的，通过证明当
k
≥
2
k \ge 2
k≥2 时，EUCLID(Fk+1, Fk) 恰好进行了
k
−
1
k - 1
k−1 次递归调用（？）。我们在
k
k
k 上使用归纳法。
EUCLID(F3, F2) 恰好进行
1
1
1 次调用，变为 EUCLID(1, 0)（我们必须从
k
=
2
k = 2
k=2 开始，因为
k
=
1
k = 1
k=1 时没有
b
=
F
1
<
F
2
b = F_1 < F_2
b=F1<F2 ）。对于归纳步骤，假设 EUCLID(Fk, Fk-1) 恰好进行
k
−
2
k - 2
k−2 次调用。因为
k
>
2
k > 2
k>2 ，我们有
F
k
>
F
k
−
1
>
0
F_k > F_{k - 1} > 0
Fk>Fk−1>0 且
F
k
+
1
=
F
k
+
F
k
−
1
F_{k+1} = F_k + F_{k-1}
Fk+1=Fk+Fk−1 ，又由（算导练习31.1-1）有
F
k
+
1
m
o
d
F
k
=
F
k
−
1
F_{k+1} \bmod F_k = F_{k - 1}
Fk+1modFk=Fk−1 。于是有：
g
c
d
(
F
k
+
1
,
F
k
)
=
g
c
d
(
F
k
,
F
k
+
1
m
o
d
F
k
)
=
g
c
d
(
F
k
,
F
k
−
1
)
gcd(F_{k+1}, F_k) = gcd(F_k, F_{k+1} \bmod F_k) = gcd(F_k, F_{k-1})
gcd(Fk+1,Fk)=gcd(Fk,Fk+1modFk)=gcd(Fk,Fk−1)因此，
EUCLID(Fk+1, Fk) 的调用次数恰好比 EUCLID(Fk, Fk-1) 多一次，即恰好
k
−
1
k - 1
k−1 次，从而达到定理31.11中的上界。
由于
F
k
F_k
Fk 约为
ϕ
k
/
5
\phi^k / \sqrt{5}
ϕk/5
，其中
ϕ
\phi
ϕ 是由式
(
3.24
)
(3.24)
(3.24) 定义的黄金分割率
1
+
5
2
\dfrac{1 +\sqrt{5}} {2}
21+5
，所以 EUCLID 执行中递归调用的次数为
O
(
log
b
)
O(\log b)
O(logb)（更紧的界见练习31.2-5）。因此，如果过程 EUCLID 作用于两个
β
\beta
β 位数，则它将执行
O
(
β
)
O(\beta)
O(β) 次算术运算和
O
(
β
3
)
O(\beta^3)
O(β3) 次位 *** 作（假设
β
\beta
β 位数的乘法和除法运算要执行
O
(
β
2
)
O(\beta^2)
O(β2) 次位 *** 作）。（算导思考题31-2要求证明位 *** 作次数的界为
O
(
β
2
)
O(\beta^2)
O(β2) ）。
现在重写欧几里得算法、以计算出额外的有用信息。特别地，我们推广该算法用于计算出满足下列条件的整系数 x , y x, y x,y ： d = g c d ( a , b ) = a x + b y (31.16) d = gcd(a, b) = ax+by \tag{31.16} d=gcd(a,b)=ax+by(31.16)
注意：
x
,
y
x, y
x,y 可能为
0
0
0 或负数。我们将会发现这些系数对计算模乘法的逆 modular multiplicative inverses 是非常有用的。过程 EXTENDED-EUCLID 的输入为一对非负整数，其返回一个满足式
(
31.16
)
(31.16)
(31.16) 的三元组
(
d
,
x
,
y
)
(d, x, y)
(d,x,y) 。
EXTENDED-EUCLID(a, b)
if b == 0
return (a, 1, 0)
else (d', x', y') = EXTENDED-EUCLID(b, a mod b)
(d, x, y) = (d', y', x' - ⌊a / b⌋ * y')
return (d, x, y)
图31.1演示了用 EXTENDED-EUCLID 计算 gcd(99, 78) 的过程：
过程 EXTENDED-EUCLID 是过程 EUCLID 的一个变形。第一行等价于 EUCLID 第一行中的测试 b == 0 。如果
b
=
0
b = 0
b=0 ，则 EXTENDED-EUCLID 不仅返回第二行中的
d
=
a
d = a
d=a ，而且返回系数
x
=
1
,
y
=
0
x = 1, y = 0
x=1,y=0 ，使得
a
=
a
x
+
b
y
a = ax + by
a=ax+by 。如果
b
≠
0
b \ne 0
b=0 ，则 EXTENDED-EUCLID 首先计算出满足
d
′
=
g
c
d
(
b
,
a
m
o
d
b
)
d' = gcd(b, a\bmod b)
d′=gcd(b,amodb) 和满足
d
′
=
b
x
′
+
(
a
m
o
d
b
)
y
′
(31.17)
d' = bx' + (a \bmod b) y' \tag{31.17}
d′=bx′+(amodb)y′(31.17) 的
(
d
′
,
x
′
,
y
′
)
(d', x', y')
(d′,x′,y′) 。对过程 EUCLID 来说，在这种情况下，有
d
=
g
c
d
(
a
,
b
)
=
d
′
=
g
c
d
(
b
,
a
m
o
d
d
)
d = gcd(a, b) = d' = gcd(b, a\bmod d)
d=gcd(a,b)=d′=gcd(b,amodd) 。为了得到满足
d
=
a
x
+
b
y
d = ax + by
d=ax+by 的
x
,
y
x, y
x,y ，利用等式
d
=
d
′
d = d'
d=d′ 和式
(
3.8
)
(3.8)
(3.8) 来改写式
(
31.17
)
(31.17)
(31.17) ：
d
=
b
x
′
+
(
a
−
b
⌊
a
/
b
⌋
)
y
′
=
a
y
′
+
b
(
x
′
−
⌊
a
/
b
⌋
y
′
)
d = bx' + (a - b \lfloor a / b \rfloor ) y' = ay' + b(x' - \lfloor a / b\rfloor y')
d=bx′+(a−b⌊a/b⌋)y′=ay′+b(x′−⌊a/b⌋y′) 因此，当选择
x
=
y
′
x = y'
x=y′ 和
y
=
x
′
−
⌊
a
/
b
⌋
y
′
y = x' - \lfloor a / b\rfloor y'
y=x′−⌊a/b⌋y′ 时，就可满足等式
d
=
a
x
+
b
y
d = ax + by
d=ax+by ，从而证明了过程 EXTENDED-EUCLID 的正确性。
由于在 EUCLID 中所执行的递归调用次数，与 EXTENDED-EUCLID 中所执行的递归调用次数相等，因此 EUCLID 与 EXTENDED-EUCLID 的运行时间相同，两者相差不超过一个常数因子，即对
a
>
b
>
0
a > b > 0
a>b>0 ，递归调用的次数为
O
(
log
b
)
O(\log b)
O(logb) 。
3. 模运算
非正式地，我们可以把模运算 modular arithmetic 与通常的整数算术运算一样看待，如果执行模
n
n
n 运算，则每个结果值
x
x
x 都由集合
{
0
,
1
,
…
,
n
−
1
}
\{ 0, 1, \dots, n - 1\}
{0,1,…,n−1} 中的某个元素
a
a
a 所取代，该元素在模
n
n
n 的意义下与
x
x
x 等价（即用
a
=
x
m
o
d
n
a = x \bmod n
a=xmodn 取代
x
x
x ，即
a
∈
[
x
]
n
a \in [x]_n
a∈[x]n 或写成
a
≡
x
(
m
o
d
n
)
a \equiv x\ (\bmod\ n)
a≡x (mod n) ） 。如果仅限于运用加法、减法和乘法运算，则用这样的非正式模型就足够了。一个更为形式化的模运算模型，最适合于用群论结构来进行描述。
群 group
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 是一个集合
S
S
S 和定义在
S
S
S 上的二元运算
⊕
\oplus
⊕ ，该运算满足下列性质：
Closure ：对所有
a
,
b
∈
S
a, b \in S
a,b∈S ，有
a
⊕
b
∈
S
a \oplus b \in S
a⊕b∈S 。单位元 Identity ：存在一个元素
e
∈
S
e \in S
e∈S ，称为群的单位元 identity ，满足对所有
a
∈
S
a \in S
a∈S ，有
e
⊕
a
=
a
⊕
e
=
a
e \oplus a = a \oplus e = a
e⊕a=a⊕e=a 。结合律 Associativity ：对所有
a
,
b
,
c
∈
S
a, b,c \in S
a,b,c∈S ，有
(
a
⊕
b
)
⊕
c
=
a
⊕
(
b
⊕
c
)
(a \oplus b) \oplus c = a \oplus (b \oplus c)
(a⊕b)⊕c=a⊕(b⊕c) 。逆元 Inverses ：对每个
a
∈
S
a \in S
a∈S ，存在唯一的元素
b
∈
S
b \in S
b∈S ，称为
a
a
a 的逆元 inverse ，满足
a
⊕
b
=
b
⊕
a
=
e
a \oplus b = b \oplus a = e
a⊕b=b⊕a=e 。
例如，考察一个熟知的、在加法运算下整数
Z
\Z
Z 所构成的群
(
Z
,
+
)
(\Z, +)
(Z,+) ：
0
0
0 是单位元，
a
a
a 的逆元为
−
a
-a
−a 。如果群
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 满足交换律 commutative law ，即对所有
a
,
b
∈
S
a, b \in S
a,b∈S 、有
a
⊕
b
=
b
⊕
a
a \oplus b = b \oplus a
a⊕b=b⊕a ，则它是一个交换群/阿贝尔群 abelian group 。显然，
(
Z
,
+
)
(\Z, +)
(Z,+) 是一个交换群。如果群
(
S
,
⊕
)
(S, \oplus )
(S,⊕) 满足
∣
S
∣
<
∞
|S| < \infin
∣S∣<∞ ，则它是一个有限群 finite group 。
通过使用模 n n n 加法和模 n n n 乘法运算，可以形成两个有限交换群，其中 n n n 是正整数。这些群基于（算导31.1节中定义的）整数模 n n n 所形成的等价类。
为了定义一个在
Z
n
=
{
[
a
]
n
∣
0
≤
a
≤
n
−
1
}
\Z_n = \{ [a]_n \mid 0 \le a \le n - 1\}
Zn={[a]n∣0≤a≤n−1} 上的群，我们需要有合适的二元运算，该运算可以通过重新定义普通的加法和乘法运算得到。我们能轻松地定义
Z
n
\Z_n
Zn 上的加法和乘法运算，因为两个整数的等价类唯一地决定了它们和或积的等价类 the equivalence class of two integers uniquely determines the equivalence class of their sum or product 。也就是说，如果
a
≡
a
′
(
m
o
d
n
)
a \equiv a'\ (\bmod\ n)
a≡a′ (mod n) 且
b
≡
b
′
(
m
o
d
n
)
b \equiv b'\ (\bmod\ n)
b≡b′ (mod n) ，那么：
a
+
b
≡
a
′
+
b
′
(
m
o
d
n
)
a
b
≡
a
′
b
′
(
m
o
d
n
)
a + b \equiv a' + b'\ (\bmod\ n) \ ab \equiv a'b'\ (\bmod\ n)
a+b≡a′+b′ (mod n)ab≡a′b′ (mod n) 因此，定义模
n
n
n 加法和模
n
n
n 乘法如下（分别用
+
n
,
⋅
n
+_n, \cdot_n
+n,⋅n 表示）：
[
a
]
n
+
n
[
b
]
n
=
[
a
+
b
]
n
[
a
]
n
⋅
n
[
b
]
n
=
[
a
b
]
n
(31.18)
[a]_n +_n [b]_n = [a+b]_n \ [a]_n \cdot_n [b]_n = [ab]_n \tag{31.18}
[a]n+n[b]n=[a+b]n[a]n⋅n[b]n=[ab]n(31.18) 我们能类似定义
Z
n
\Z_n
Zn 上的减法为
[
a
]
n
−
n
[
b
]
n
=
[
a
−
b
]
n
[a]_n -_{n} [b]_n = [a-b]_n
[a]n−n[b]n=[a−b]n ，但下面将会看到，除法的定义更加复杂。
这些事实说明，当在 Z n \Z_n Zn 中进行计算时，「使用每个等价类的最小非负元素」作为其代表，这种方法具有一般性和便捷性。我们对这些代表元素像平常那样执行加法、减法与乘法，但每个结果 x x x 都由其所对应类的代表元素代替（即用 x m o d n x \bmod n xmodn 来代替）。
3.2.1 模 n n n 加法群运用该模
n
n
n 加法的定义，定义模
n
n
n 加法群 additive group modulo n
(
Z
n
,
+
n
)
(\Z_n, +_n)
(Zn,+n) ，它的大小规模为
∣
Z
n
∣
=
n
|\Z_n| = n
∣Zn∣=n 。图31-2(a)给出了群
(
Z
6
,
+
6
)
(\Z_6, +_6)
(Z6,+6) 的运算表。
定理31.12 系统
(
Z
n
,
+
n
)
(\Z_n, +_n)
(Zn,+n) 是一个有限交换群。
证明：式
(
31.18
)
(31.18)
(31.18) 表明
(
Z
n
,
+
n
)
(\Z_n, +_n)
(Zn,+n) 是封闭的。由
+
+
+ 满足交换律和结合律，可以推出
+
n
+_n
+n 满足交换律和结合律：
(
[
a
]
n
+
n
[
b
]
n
)
+
n
[
c
]
n
=
[
a
+
b
]
n
+
n
[
c
]
n
式
(
31.18
)
=
[
(
a
+
b
)
+
c
]
n
式
(
31.18
)
=
[
a
+
(
b
+
c
)
]
n
加
法
结
合
律
=
[
a
]
n
+
n
[
b
+
c
]
n
式
(
31.18
)
=
[
a
]
n
+
n
(
[
b
]
n
+
n
[
c
]
n
)
式
(
31.18
)
[
a
]
n
+
n
[
b
]
n
=
[
a
+
b
]
n
式
(
31.18
)
=
[
b
+
a
]
n
加
法
交
换
律
=
[
b
]
n
+
n
[
a
]
n
式
(
31.18
)
\begin{aligned}( [a]_n +_n [b]_n) +_n [c]_n &= [a + b]_n +_n [c]_n \quad& 式(31.18) \ &= [(a + b) + c]_n \quad& 式(31.18) \ &= [a + (b+c)]_n \quad& 加法结合律 \ &= [a]_n +_n [b + c]_n \quad& 式(31.18) \ &= [a]_n +_n ( [b]_n +_n [c]_n) \quad& 式(31.18) \ [a]_n +_n [b]_n &= [a + b]_n \quad& 式(31.18) \ &= [b+a]_n \quad& 加法交换律 \ &= [b]_n +_n [a]_n \quad& 式(31.18) \end{aligned}
([a]n+n[b]n)+n[c]n[a]n+n[b]n=[a+b]n+n[c]n=[(a+b)+c]n=[a+(b+c)]n=[a]n+n[b+c]n=[a]n+n([b]n+n[c]n)=[a+b]n=[b+a]n=[b]n+n[a]n式(31.18)式(31.18)加法结合律式(31.18)式(31.18)式(31.18)加法交换律式(31.18)
(
Z
n
,
+
n
)
(\Z_n, +_n)
(Zn,+n) 的单位元是
0
0
0（即
[
0
]
n
[0]_n
[0]n ）。元素
a
a
a（即
[
a
]
n
[a]_n
[a]n ）的（加法）逆元是元素
−
a
-a
−a（即
[
−
a
]
n
[-a]_n
[−a]n 或
[
n
−
a
]
n
[n - a]_n
[n−a]n ），因为
[
a
]
n
+
n
[
−
a
]
n
=
[
a
−
a
]
n
=
[
0
]
n
[a]_n +_n [-a]_n = [a - a]_n = [0]_n
[a]n+n[−a]n=[a−a]n=[0]n 。
■
\blacksquare
■
运用模
n
n
n 乘法的定义，我们定义模
n
n
n 乘法群 multiplicative group modulo n
(
Z
n
∗
,
⋅
n
)
(\Z^*_n, \cdot_n)
(Zn∗,⋅n) 。该群中的元素是「
Z
n
\Z_n
Zn 中与
n
n
n 互质的元素」组成的集合
Z
n
∗
\Z^*_n
Zn∗ ：
Z
n
∗
=
{
[
a
]
n
∈
Z
n
∣
g
c
d
(
a
,
n
)
=
1
}
\Z^*_n = \{ [a]_n \in \Z_n \mid gcd(a, n)= 1\}
Zn∗={[a]n∈Zn∣gcd(a,n)=1} 为了表明
Z
n
∗
\Z^*_n
Zn∗ 是良定义的，注意到，对
0
≤
a
<
n
0 \le a < n
0≤a<n 以及所有整数
k
k
k ，有
a
≡
(
a
+
k
n
)
(
m
o
d
n
)
a \equiv (a + kn) \pmod n
a≡(a+kn)(modn)（即
a
∈
[
a
]
n
a \in [a]_n
a∈[a]n ）。因此根据（算导练习31.2-3），
g
c
d
(
a
,
n
)
=
1
gcd(a, n) = 1
gcd(a,n)=1 蕴含着对所有整数
k
k
k 、
g
c
d
(
a
+
k
n
,
n
)
=
1
gcd(a+kn, n)= 1
gcd(a+kn,n)=1 。因为
[
a
]
n
=
{
a
+
k
n
∣
k
∈
Z
}
[a]_n = \{a + kn \mid k \in \Z\}
[a]n={a+kn∣k∈Z} ，所以集合
Z
n
∗
\Z_n^*
Zn∗ 是良定义的（？），下面是这种群的一个例子：
Z
15
∗
=
{
1
,
2
,
4
,
7
,
8
,
11
,
13
,
14
}
\Z^*_{15} = \{ 1, 2,4 , 7, 8, 11, 13, 14\}
Z15∗={1,2,4,7,8,11,13,14}
其中定义在群上的运算是模 15 15 15 乘法运算（这里把元素 [ a ] 15 [a]_{15} [a]15 表示为 a a a ，例如把 [ 7 ] 15 [7]_{15} [7]15 表示为 7 7 7 ）。图31-2(b)显示了群 ( Z 15 ∗ , ⋅ 15 ) (\Z^*_{15}, \cdot_{15}) (Z15∗,⋅15) 。例如，在 Z 15 ∗ \Z^*_{15} Z15∗ 中， 8 ⋅ 11 ≡ 13 ( m o d 15 ) 8 \cdot 11 \equiv 13 \pmod {15} 8⋅11≡13(mod15) 。该群的单位元为 1 1 1 。
定理31.13 系统
(
Z
n
∗
,
⋅
n
)
(\Z_n^*, \cdot_n)
(Zn∗,⋅n) 是一个有限交换群。
证明 定理31.6说明
(
Z
n
∗
,
⋅
n
)
(\Z^*_n, \cdot_n)
(Zn∗,⋅n) 是封闭的。和定理31.12证明过程中对
+
n
+_n
+n 证明类似，可以证明
⋅
n
\cdot_n
⋅n 也满足交换律和结合律。其单位元是
[
1
]
n
[1]_n
[1]n 。为了证明逆元的存在，设
a
a
a 是
Z
n
∗
\Z^*_n
Zn∗ 中的一个元素（
a
a
a 与
n
n
n 互质），并设
(
d
,
x
,
y
)
(d, x, y)
(d,x,y) 为 EXTENDED-EUCLID(a, n) 的输出结果，则
d
=
1
d = 1
d=1 ，因为
a
∈
Z
n
∗
a \in \Z^*_n
a∈Zn∗ ，而且：
a
x
+
n
y
=
1
(31.19)
ax+ny = 1 \tag{31.19}
ax+ny=1(31.19) 或者等价地，
a
x
≡
1
(
m
o
d
n
)
ax \equiv 1 \pmod n
ax≡1(modn) 即
[
a
]
n
⋅
n
[
x
]
n
=
[
a
x
]
n
=
[
1
]
n
[a]_n \cdot_n [x]_n = [ax]_n = [1]_n
[a]n⋅n[x]n=[ax]n=[1]n
因此 [ x ] n [x]_n [x]n 是 [ a ] n [a]_n [a]n 对模 n n n 乘法的逆元。进一步，我们断言 [ x ] n ∈ Z n ∗ [x]_n \in \Z^*_n [x]n∈Zn∗ ，因为等式 ( 31.19 ) (31.19) (31.19) 说明了 x x x 和 n n n 的最小正线性组合必然是 1 1 1 。因此，由定理31.2推出 g c d ( x , n ) = 1 gcd(x, n)= 1 gcd(x,n)=1 。关于逆元的唯一性证明留作（推论31.26）。 ■ \blacksquare ■
作为计算乘法逆元的一个例子，假设
a
=
5
,
n
=
11
a = 5, n = 11
a=5,n=11 ，则 EXTENDED-EUCLID(a, n) 返回
(
d
,
x
,
y
)
=
(
1
,
−
2
,
1
)
(d, x, y) = (1, -2, 1)
(d,x,y)=(1,−2,1) —— EXTENDED-EUCLID(5, 11) -> EXTENDED-EUCLID(11, 5) -> EXTENDED-EUCLID(5, 1) -> EXTENDED-EUCLID(1, 0) -> (1, 1, 0) -> (1, 0, 1) -> (1, 1, -2) -> (1, -2, 1) 。于是
1
=
5
⋅
(
−
2
)
+
11
⋅
1
1 = 5 \cdot (-2) + 11 \cdot 1
1=5⋅(−2)+11⋅1 。因此
[
−
2
]
11
[-2]_{11}
[−2]11（即
[
9
]
11
[9]_{11}
[9]11 ）是
[
5
]
11
[5]_{11}
[5]11 的乘法逆元。
当遇到群
(
Z
n
,
+
n
)
(\Z_n, +_n)
(Zn,+n) 和
(
Z
n
∗
,
⋅
n
)
(\Z^*_n, \cdot_n)
(Zn∗,⋅n) 时，我们遵循这一便利的实践——使用代表元素来表示它们的等价类，并分别用通常的运算记号
+
+
+ 和
⋅
\cdot
⋅（或 juxtaposition ，故
a
b
=
a
⋅
b
ab = a\cdot b
ab=a⋅b ）来表示运算
+
n
+_n
+n 和
⋅
n
\cdot_n
⋅n 。此外，模
n
n
n 等价也可以用
Z
n
\Z_n
Zn 中的等式说明，例如下面两种表示等价：
a
x
≡
b
(
m
o
d
n
)
[
a
]
n
⋅
n
[
x
]
n
=
[
b
]
n
ax \equiv b \pmod n \ [a]_n \cdot_n [x]_n = [b]_n
ax≡b(modn)[a]n⋅n[x]n=[b]n 为了方便表示，当从上下文能看出所采用的运算时，有时仅用
S
S
S 来表示群
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 。因此可以用
Z
n
,
Z
n
∗
\Z_n, \Z_n^*
Zn,Zn∗ 来分别表示群
(
Z
n
,
+
n
)
(\Z_n, +_n)
(Zn,+n) 和
(
Z
n
∗
,
⋅
n
)
(\Z_n^*, \cdot_n)
(Zn∗,⋅n) 。
一个元素 a a a 的（乘法）逆元表示为 ( a − 1 m o d n ) (a^{-1} \bmod n) (a−1modn) 。 Z n ∗ \Z_n^* Zn∗ 中的除法由等式 a / b ≡ a b − 1 ( m o d n ) a / b \equiv a b^{-1} \pmod n a/b≡ab−1(modn) 定义。例如，在 Z 15 ∗ \Z^*_{15} Z15∗ 中，有 7 − 1 ≡ 13 ( m o d 15 ) 7^{-1} \equiv 13 \pmod {15} 7−1≡13(mod15) ，因为 7 ⋅ 13 = 91 ≡ 1 ( m o d 15 ) 7 \cdot 13 = 91 \equiv 1 \pmod {15} 7⋅13=91≡1(mod15) 。这样就有 4 / 7 ≡ 4 ⋅ 13 ≡ 7 ( m o d 15 ) 4 / 7 \equiv 4 \cdot 13 \equiv 7 \pmod {15} 4/7≡4⋅13≡7(mod15) 。
Z
n
∗
\Z^*_n
Zn∗ 的规模表示为
ϕ
(
n
)
\phi(n)
ϕ(n) ，这个函数称为欧拉
p
h
i
phi
phi 函数 Euler's phi function ，满足下式：
ϕ
(
n
)
=
n
∏
p
:
p
i
s
p
r
i
m
e
a
n
d
p
∣
n
(
1
−
1
p
)
(31.20)
\phi(n) = n \prod_{\mathrm{p\ : \ p\ is\ prime\ and\ p \mid n} } \bigg(1 - \dfrac{1}{p} \bigg) \tag{31.20}
ϕ(n)=np : p is prime and p∣n∏(1−p1)(31.20) 其中
p
p
p 遍历 runs over 所有的能整除
n
n
n 的素数（如果
n
n
n 为素数，则也包括
n
n
n 本身）。在此不对此公式做出证明。从直观上看，开始时有一张
n
n
n 个余数组成的表
{
0
,
1
,
…
,
n
−
1
}
\{ 0, 1, \dots, n - 1\}
{0,1,…,n−1} ，然后对于每个能整除
n
n
n 的素数
p
p
p ，在表中划掉所有
p
p
p 的倍数。例如，由于
45
45
45 的素约数为
3
,
5
3, 5
3,5 ，所以：
ϕ
(
45
)
=
45
(
1
−
1
3
)
(
1
−
1
5
)
=
45
⋅
2
3
⋅
4
5
=
24
\phi(45) = 45\bigg( 1- \dfrac{1}{3} \bigg) \bigg( 1 - \dfrac{1}{5} \bigg) = 45 \cdot \dfrac{2}{3} \cdot \dfrac{4}{5} = 24
ϕ(45)=45(1−31)(1−51)=45⋅32⋅54=24 如果
p
p
p 是素数，则
Z
p
∗
=
{
1
,
2
,
…
,
p
−
1
}
\Z^*_p = \{ 1, 2, \dots, p - 1\}
Zp∗={1,2,…,p−1} ，并且：
ϕ
(
p
)
=
p
(
1
−
1
p
)
=
p
−
1
(31.21)
\phi(p) = p( 1- \dfrac{1}{p}) = p - 1 \tag{31.21}
ϕ(p)=p(1−p1)=p−1(31.21)
如果
n
n
n 是合数，则
ϕ
(
n
)
<
n
−
1
\phi(n) < n - 1
ϕ(n)<n−1 ，尽管它可以表示为：
ϕ
(
n
)
>
n
e
γ
ln
ln
n
+
3
ln
ln
n
(31.22)
\phi(n) > \dfrac{n}{ e^{\gamma} \ln \ln n +\dfrac{3}{\ln \ln n}} \tag{31.22}
ϕ(n)>eγlnlnn+lnlnn3n(31.22) 其中
n
≥
3
n \ge 3
n≥3 ，此时
γ
=
0.5772156649
…
\gamma = 0.577 215 664 9 \dots
γ=0.5772156649… 是欧拉常数 Euler's constant 。当
n
>
5
n> 5
n>5 时，一个更简单（也更松弛）的下界是：
ϕ
(
n
)
>
n
6
ln
ln
n
(31.23)
\phi(n) > \dfrac{n}{ 6 \ln \ln n } \tag{31.23}
ϕ(n)>6lnlnnn(31.23) 式
(
31.22
)
(31.22)
(31.22) 中的下界事实上是最好的，因为：
lim
n
→
∞
i
n
f
ϕ
(
n
)
n
/
ln
ln
n
=
e
−
γ
(31.24)
\lim_{n \to \infin} \mathrm{ inf} \dfrac{ \phi(n)}{ n / \ln \ln n} = e^{ - \gamma} \tag{31.24}
n→∞liminfn/lnlnnϕ(n)=e−γ(31.24)
如果
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 是一个群，
S
′
⊆
S
S' \subseteq S
S′⊆S ，并且
(
S
′
,
⊕
)
(S', \oplus)
(S′,⊕) 也是一个群，则
(
S
′
,
⊕
)
(S', \oplus)
(S′,⊕) 是
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 的一个子群 subgroup 。例如，在加法运算下，偶数形成一个整数的子群。下列定理提供了识别子群的一个有用工具。
定理31.14（一个有限群的非空封闭子集是一个子群 A nonempty closed subset of a finite group is a subgroup ）如果
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 是一个有限群，
S
′
S'
S′ 是
S
S
S 的任意一个非空子集，并满足对所有
a
,
b
∈
S
′
a, b \in S'
a,b∈S′ 有
a
⊕
b
∈
S
′
a \oplus b \in S'
a⊕b∈S′ ，则
(
S
′
,
⊕
)
(S', \oplus)
(S′,⊕) 是
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 的一个子群。
证明：证明过程见（算导练习31.3-3）。
■
\blacksquare
■
例如，集合 { 0 , 2 , 4 , 6 } \{ 0, 2, 4, 6\} {0,2,4,6} 形成 Z 8 \Z_8 Z8 的一个子群，因为它是非空的，而且在 + + + 运算下具有封闭性（即在 + 8 +_8 +8 下它是封闭的）。
下列定理对子群的规模，作出了一个非常有用的限制，证明在此略去。
定理31.5（拉格朗日定理 Lagrange’s theorem ）如果
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 是一个有限群，
(
S
′
,
⊕
)
(S', \oplus)
(S′,⊕) 是
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 的一个子群，则
∣
S
′
∣
|S'|
∣S′∣ 是
∣
S
∣
|S|
∣S∣ 的一个约数。
■
\blacksquare
■
对一个群
S
S
S 的子群
S
′
S'
S′ ，如果
S
′
≠
S
S' \ne S
S′=S ，则子群
S
′
S'
S′ 称为群
S
S
S 的真子群 proper subgroup 。（算导31.8节中）对 Miller-Rabin 素数测试过程的分析，将用到下面的推论。
推论31.16 如果 S ′ S' S′ 是有限群 S S S 的真子群，则 ∣ S ′ ∣ ≤ ∣ S ∣ / 2 |S'| \le |S| / 2 ∣S′∣≤∣S∣/2 。 ■ \blacksquare ■
3.4 由一个元素生成的子群定理31.14给出了一种用于生成有限群
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 的子群的简单方法：选择一个元素
a
a
a ，取出由
a
a
a 根据群上的运算能生成的所有元素。具体地，对
k
≥
1
k \ge 1
k≥1 定义
a
(
k
)
a^{(k)}
a(k)（这是一个元素！）如下：
a
(
k
)
=
⨁
i
=
1
k
a
=
a
⊕
a
⊕
⋯
⊕
a
⏟
k
个
a^{(k)} = \bigoplus^k_{i=1}a = \underbrace{ a \oplus a \oplus \dots \oplus a }_{k个}
a(k)=i=1⨁ka=k个
a⊕a⊕⋯⊕a 例如，如果取群
Z
6
\Z_6
Z6 中的元素
a
=
2
a = 2
a=2 ，序列
a
(
1
)
,
a
(
2
)
,
a
(
3
)
,
…
a^{(1)}, a^{(2)}, a^{(3)}, \dots
a(1),a(2),a(3),… 为：
2
,
4
,
0
,
2
,
4
,
0
,
2
,
4
,
0
,
…
2, 4, 0, 2, 4, 0, 2, 4, 0, \dots
2,4,0,2,4,0,2,4,0,…
在群
Z
n
\Z_n
Zn 中，有
a
(
k
)
=
k
a
m
o
d
n
a^{(k)} = ka \bmod n
a(k)=kamodn 。在群
Z
n
∗
\Z^*_n
Zn∗ 中，有
a
(
k
)
=
a
k
m
o
d
n
a^{(k)} = a^k \bmod n
a(k)=akmodn 。由
a
a
a 生成的子群用
⟨
a
⟩
\langle a \rangle
⟨a⟩ 或
(
⟨
a
⟩
,
⊕
)
( \langle a \rangle, \oplus )
(⟨a⟩,⊕) 来表示，其定义如下：
⟨
a
⟩
=
{
a
(
k
)
∣
k
≥
1
}
\langle a \rangle = \{ a^{(k) } \mid k \ge 1\}
⟨a⟩={a(k)∣k≥1} 我们称
a
a
a 生成 generates 子群
⟨
a
⟩
\langle a \rangle
⟨a⟩ ，或者
a
a
a 是
⟨
a
⟩
\langle a \rangle
⟨a⟩ 的生成元 generator 。因为
S
S
S 是有限集，所以
⟨
a
⟩
\langle a \rangle
⟨a⟩ 是
S
S
S 的有限子集，它可能包含
S
S
S 中的所有元素。由
⊕
\oplus
⊕ 满足结合律可知：
a
(
i
)
⊕
a
(
j
)
=
a
(
i
+
j
)
a^{(i) } \oplus a^{(j)} = a^{ (i+j)}
a(i)⊕a(j)=a(i+j) 故
⟨
a
⟩
\langle a\rangle
⟨a⟩ 具有封闭性。根据定理31.14，
⟨
a
⟩
\langle a \rangle
⟨a⟩ 是
S
S
S 的一个子群。例如，在
Z
6
\Z_6
Z6 中，有：
⟨
0
⟩
=
{
0
}
⟨
1
⟩
=
{
0
,
1
,
2
,
3
,
4
,
5
}
⟨
2
⟩
=
{
0
,
2
,
4
}
\begin{aligned} &\langle 0 \rangle = \{ 0 \} \ &\langle 1\rangle = \{ 0, 1, 2, 3, 4, 5 \} \ &\langle 2\rangle = \{ 0, 2, 4 \} \end{aligned}
⟨0⟩={0}⟨1⟩={0,1,2,3,4,5}⟨2⟩={0,2,4} 类似地，在
Z
7
∗
\Z^*_7
Z7∗ 中，有：
⟨
1
⟩
=
{
1
}
⟨
2
⟩
=
{
1
,
2
,
4
}
⟨
3
⟩
=
{
1
,
2
,
3
,
4
,
5
,
6
}
\begin{aligned} &\langle 1 \rangle = \{ 1 \} \ &\langle 2 \rangle = \{ 1, 2, 4 \} \ &\langle 3 \rangle = \{ 1,2,3,4,5,6\} \end{aligned}
⟨1⟩={1}⟨2⟩={1,2,4}⟨3⟩={1,2,3,4,5,6}
在群
S
S
S 中
a
a
a 的阶 order 定义为满足
a
(
t
)
=
e
a^{(t) } = e
a(t)=e 的最小正整数
t
t
t ，用
o
r
d
(
a
)
ord(a)
ord(a) 来表示。
定理31.17 对任意有限群
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 和任意
a
∈
S
a \in S
a∈S ，一个元素的阶等于它所生成子群的规模，即
o
r
d
(
a
)
=
∣
⟨
a
⟩
∣
ord(a) = | \langle a \rangle |
ord(a)=∣⟨a⟩∣ 。
证明：设
t
=
o
r
d
(
a
)
t = ord(a)
t=ord(a) 。因为
a
(
t
)
=
e
a^{(t)} = e
a(t)=e 并且对
k
≥
1
k \ge 1
k≥1 有
a
(
t
+
k
)
=
a
(
t
)
⊕
a
(
k
)
=
a
(
k
)
a^{ (t+k) } = a^{(t)} \oplus a^{(k)} = a^{(k)}
a(t+k)=a(t)⊕a(k)=a(k) ，如果
i
>
t
i > t
i>t ，则对某个
j
<
i
j < i
j<i ，有
a
(
i
)
=
a
(
j
)
a^{(i)} = a^{(j)}
a(i)=a(j) 。因此，当我们通过
a
a
a 生成元素时，在
a
(
t
)
a^{(t)}
a(t) 后面不会看到新元素。于是
⟨
a
⟩
=
{
a
(
1
)
,
a
(
2
)
,
…
,
a
(
t
)
}
\langle a \rangle = \{ a^{ (1) }, a^{ (2) } , \dots, a^{ (t)} \}
⟨a⟩={a(1),a(2),…,a(t)} ，而且
∣
⟨
a
⟩
∣
≤
t
| \langle a \rangle | \le t
∣⟨a⟩∣≤t 。
为了证明 ∣ ⟨ a ⟩ ∣ ≥ t | \langle a \rangle| \ge t ∣⟨a⟩∣≥t ，我们证明序列 a ( 1 ) , a ( 2 ) , … , a ( t ) a^{(1)}, a^{(2)}, \dots, a^{(t)} a(1),a(2),…,a(t) 中的元素各不相同。假设这一结论不成立，即对某个满足 1 ≤ i < j ≤ t 1 \le i < j \le t 1≤i<j≤t 的 i i i 和 j j j 有 a ( i ) = a ( j ) a^{(i)} = a^{(j)} a(i)=a(j) 。那么对 k ≥ 0 k \ge 0 k≥0 ，有 a ( i + k ) = a ( j + k ) a^{(i+k)} = a^{(j+k)} a(i+k)=a(j+k) 。但这说明 a ( i + ( t − j ) ) = a ( j + ( t − j ) ) = e a^{ ( i + (t - j)) } = a^{ (j + (t - j)) } = e a(i+(t−j))=a(j+(t−j))=e ，因为 i + ( t − j ) < t i + (t - j) < t i+(t−j)<t 、而 t t t 是满足 a ( t ) = e a^{(t)} = e a(t)=e 的最小正值，这样就出现了矛盾。因此，序列 a ( 1 ) , a ( 2 ) , … , a ( t ) a^{(1)}, a^{(2)}, \dots, a^{(t)} a(1),a(2),…,a(t) 中的每个元素都是不同的， ∣ ⟨ a ⟩ ∣ ≥ t | \langle a \rangle | \ge t ∣⟨a⟩∣≥t 。于是得出结论 o r d ( a ) = ∣ ⟨ a ⟩ ∣ ord(a) = | \langle a \rangle | ord(a)=∣⟨a⟩∣ 。 ■ \blacksquare ■
推论31.18 序列 a ( 1 ) , a ⟨ 2 ⟩ , … a^{ (1)} , a^{ \langle 2 \rangle }, \dots a(1),a⟨2⟩,… 是周期序列，其周期为 t = o r d ( a ) t = ord(a) t=ord(a) ，即 a ( i ) = a ( j ) a^{(i)} = a^{(j)} a(i)=a(j) 当且仅当 i ≡ j ( m o d t ) i \equiv j \pmod t i≡j(modt) 。 ■ \blacksquare ■
与上述推论一致的是，我们对所有整数 i i i ，定义 a ( 0 ) = a ( t ) a^{(0)} = a^{(t)} a(0)=a(t) 为 e e e 、且定义 a ( i ) a^{(i)} a(i) 为 a ( i m o d t ) a^{(i \bmod t)} a(imodt) ，其中 t = o r d ( a ) t = ord(a) t=ord(a) 。
推论31.19 如果
(
S
,
⊕
)
(S, \oplus)
(S,⊕) 是具有单位元
e
e
e 的有限群，则对所有
a
∈
S
a \in S
a∈S ，
a
(
∣
S
∣
)
=
e
a^{ ( | S| ) } = e
a(∣S∣)=e 。
证明：由拉格朗日定理可知，
o
r
d
(
a
)
∣
∣
S
∣
ord(a) \mid |S|
ord(a)∣∣S∣（即存在整除关系），因此
∣
S
∣
≡
0
(
m
o
d
t
)
|S| \equiv 0 \pmod t
∣S∣≡0(modt) ，其中
t
=
o
r
d
(
a
)
t = ord(a)
t=ord(a) ，所以
a
(
∣
S
∣
)
=
a
(
0
)
=
e
■
a^{ (|S|)} = a^{ (0) } = e\qquad \blacksquare
a(∣S∣)=a(0)=e■
4. 求解模线性方程 5. 中国余数定理 6. 元素的幂 7. RSA公钥加密系统 8. 素数测试 9. 整数的因子分解
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）