31.3 模运算
可以把模运算非正式地与通常的整数运算一样看待，如果执行模n运算，则每个结果值x都由集合{0，1，...， n-1}中的某个元素所取代，该元素在模n的意义下与x等价(即用x mod n来取代x)。如果仅限于运用加法、减法和乘法运算，则用这样的非正式模型就足够了。模运算模型最适合于用群论结构来进行描述，下面就给出更为形式化的模型。
有限群
群(S，
)是一个集合S和定义在S上的二进制运算
，该运算满足下列性质：
封闭性：对所有a, b∈S，有a
b∈S。
单位元：存在一个元素e∈S，称为群的单位元，满足对所有a∈S，e
a=a
e=a。
结合律：对所有a, b, c∈S，有(a
b)
c=a
(b
c)。
逆元：对每个a∈S，存在唯一的元素b∈S，称为a的逆元，满足a
b=b
a=e。
例如，考察一个熟知的在加法运算下整数Z所构成的群(Z，+)：0是单位元，a的逆元为-a。如果群(S，
)满足交换律，即对所有a, b∈S，有a
b=ba，则它是一个交换群。如果群(S，
)满足|S|<∞，则它是一个有限群。
由模加法与模乘法所定义的群
通过对模n运用加法与乘法运算，可以得到两个有限交换群，其中n是正整数。这些群基于31.1节中定义的整数模n所形成的等价类。
我们需要合适的二元运算来定义Zn上的群，该运算可以通过重新定义普通的加法运算与乘法运算得到。Z上的加法与乘法运算很容易定义，因为两个整数的等价类唯一决定了其和或积的等价类。也就是说，如果a=a' (mod n)和b=b' (mod n)，那么
因此，定义模n加法与模n乘法如下(分别用+n和·n表示)：
(Zn上的减法可类似定义为[a]n-n[b]n=[a-b]n但下面将会看到，除法的定义要复杂一些。)
这些事实说明在Zn中进行计算时，可以很方便地使用每个等价类的最小非负元素作为其代表，这种方法也具有一般性。我们对这些代表元素像整数那样执行加法、减法与乘法，但每个结果x都由其所对应类的代表元素代替(即用x mod n来代替)。
运用该模n加法的定义，定义模n加法群(Zn+n)，它的规模为|zn|=n。图31-2(a)给出了群(Z6，+6)的运算表。
图31-2两个有 限群，其等价类由其代表元素表示。(a)群(Z6， +6)。(b)群(Z15*，·15)
定理31.12 系统(Zn,+n)是一个有限交换群。
证明 式(31. 18)表明(Zn,+n)是封闭的。由+满足交换律与结合律可以推出+n满足交换律与结合律：
(Zn，+n)的单位元是0(即[0]n)。元素a(即[a]n)的(加法)逆元是元素- a(即[-a]n或[n-a]n)，因为[a]n+n[-a]n=[a-a]n=[0]n。
运用模n乘法的定义，可以定义模n乘法群(Zn*，·n)。该群中的元素是Zn中与n互质的元素组成的集合Zn*：
其中定义在群上的运算是模15乘法运算。(这里把元素[a]15表示为a。例如，把[7]15表示为7。)图31-2(b)显示了群(Z15*，·15)。例如，在Z15*中，8·11=13(mod15)。该群的单位元为1。
定理31.13 系统(Zn*，·n)是一个有限交换群。
证明 定理 31. 6说明(Zn*，·n)是封闭的。和定理31. 12证明过程中对+n的证明类似，可以证明·n也满足交换律和结合律。其单位元为[1]。为了证明逆元的存在，设a是Zn*中的一个元素，并设(d, x, y)为EXTENDED-EUCLID(a, n)的输出结果，则d=1，因为a∈Zn*，而且
或者等价地，
因此，[x]n是[a]n对模n乘法的逆元。进一步，因为等式(31. 19)说明了x和n的最小正线性组合必然是1，所以断言[x]n∈Zn*。因此由定理31.2推出gcd(x, n)=1。关于逆元的唯一性证明留到推论31. 26。
作为计算乘法逆元的一个例子，设a=5且n=11，则EXTENDED-EUCLID(a, n)返回(d, x, y)=(1，-2，1)， 于是1=5·(-2)+11·1。因此[-2]11(即[9]11)是[5]11的乘法逆元。
为了方便起见，在本章的后面部分遇到群(Zn，+n)和(Zn*，·n)时，仍然用代表元素来表示等价类，并且分别用通常的运算记号+和·(或并置，故ab=a·b)来表示运算+n和·n。另外，模n等价也可以用Zn中的等式说明。例如，下列两种表示等价：
为了方便表示，当从上下文能看出所采用的运算时，有时仅用s来表示群(S，
)。因此可以用Zn和Zn*分别来表示群(Zn,+n)和(Zn*，·n)。
一个元素a的(乘法)逆元表示为(a-1 mod n)。Zn*中的除法由等式a/b=ab-1 (mod n)定义。例如，在Z15*中，有7-1=13(mod15)，因为7·13=91=1(mod15)。这样就有4/7=4·13=7(mod 15)。
Zn*的规模表示为Φ(n)。这个函数称为欧拉phi函数，满足下式：
其中p能整除n的任意素数(如果n是素数，则也包括n本身)。在此不对此公式作出证明。从直观上看，开始时有一张n个余数组成的表{0，1，...，n-1}，然后对于每个能整除n的素数p，在表中划掉所有p的倍数。例如，由于45的素约数为3和5，所以
如果p是素数，则Zp*={1, 2, ..，p-1}，并且
如果n是合数，则中(n)<n-1，尽管它可以表示为
其中n≥3，此时γ=0.577 215 664...是欧拉常数。当n>5时，一个更简单的(也更松弛)的下界是
式(31.22)中的下界事实上是最好的，因为
子群
如果(S，
)是一个群，S'
S，并且(S'，
)也是一个群，则(S'，
)称为(S，
)的子群。例如，在加法运算下，偶数形成一个整数的子群。下列定理提供了识别子群的一个有用工具。
定理31. 14 (一个有限群的非空封闭子集是一个子群)如果(S， 
)是一个有限群，S'是S的任意一个非空子集并满足对所有a, b∈S'，有a
b∈S'，则(S'，
)是(S，
)的一个子群。
证明 证明过程留作练习31. 3-3。
例如，集合{0，2，4, 6}形成Z8的一个子群，因为它是非空的，而且在+运算下具有封闭性(即在+8下它是封闭的)。
下列定理对子群的规模作出了一个非常有用的限制，证明在此略去。
定理31. 15(拉格朗日定理) 如果(S， 
)是一个有限群，(S'，
)是(S，
)的一个子群，则|S'|是|S|的一个约数。
对一个群S的子群S'，如果S'≠S，则子群S'称为群S的真子群。31. 8节中对Miller- Rabin素数测试过程的分析将用到下面的推论。
推论31.16如果 S'是有限群S的真子群，则|S'I≤|S|/2。
由一个元素生成的子群
定理31.14 给出了一种用于生成有限群(S，
)的子群的有趣方法：选择一个元素a，根据群上的运算取出由a能生成的所有元素。具体地，对k≥1定义a(k) 如下：
例如，如果取群Z6中的元素a=2，序列a(1)，a(2)，...为
在群Zn中，有a(k)>=ka mod n。在群Zn*中，有a(k)=ak mod n。由a生成的子群用<a>或(<a>，
)来表示，其定义如下：
我们称a生成子群<a>，或者a是<a>的生成元。因为S是有限集，所以<a>是S的有限子集，它可能包含S中的所有元素。由
满足结合律可知，
故<a>具有封闭性，根据定理31.14，<a>是S的一个子群。例如，在Z6中，有
类似地，在Z7*中，有
在群S中a的阶定义为满足a(t)=e的最小正整数t，用ord(a)来表示。
定理31.17 对任意有限群(S, 
)和任意a∈S，一个元素的阶等于它所生成子群的规模，即ord(a)= |<a>|。
证明 设t=ord(a)。 因为a(t)=e并且对k≥1有a(t+k)=a(t)
a(k)>=a(k)个j<i，有a(i)=a(j)因此，在a(t)后面不会出现新元素，于是<a>={a(1)，a(2)，... a(t)}，而且|<a>|≤t。为了证明 |<a>|≥t，我们证明序列a(1)，a(2)，...，a(t)中的元素各不相同。假设不成立，即对某个满足1≤i<j≤t的i和j有a(i)=a(j)。那么对k≥0，有a(i+k)=a(j+k)。但这说明a(i+(t+j))=a(j+(t-j))=e，因为i+(t-j)<t，而t是满足a(t)=e的最小正值，这样就产生了矛盾。因此，序列a(1)，a(2)，...，a(t)中的每个元素都是不同的，|<a> I≥t。于是得出结论ord(a)= |<a>|。
推论31.18 序列a(1)，a(2)，是周期序列，其周期为t=ord(a)，即a(i)=a(j)当且仅当i=j(mod t)。
对所有整数i，定义a(0)为e，且定义a(i)为a(imod)，其中t=ord(a)，与上述推论一致。
推论31.19 如果(S, 
)是具有单位元e的有限群，则对所有a∈S，
证明由拉格朗日定理可知，ord(a)||S|，因此|S|=0(mod t)，其中t=ord(a)。所以
练习
31.3-1 画出群(Z4，+4)和群(Z5*，·5)的运算表。通过找这两个群的元素间的一对应关系a，满足a+b=c(mod 4)当且仅当a(a)·a(b)=a(c)(mod 5)，来证明这两个群是同构的。
31.3-2 列举出Z9和Z13*的所有子群。
31.3-3 证明定理 31.14。
31.3-4 证明：如果p是素数且e是正整数，则
31.3-5 证明：对任意n>1和任意a∈Zn*，由式fa(x)=ax mod n所定义的函数fa: Zn*→Zn*是Zn*的一个置换。
上一篇：《算法导论》第三十一章 续
下一篇：《算法导论》第三十一章 续3
