大数据

当前位置:首页 > 大数据

《算法导论》第三十一章 续2

31.3 模运算

可以把模运算非正式地与通常的整数运算一样看待,如果执行模n运算,则每个结果值x都由集合{0,1,..., n-1}中的某个元素所取代,该元素在模n的意义下与x等价(即用x mod n来取代x)。如果仅限于运用加法、减法和乘法运算,则用这样的非正式模型就足够了。模运算模型最适合于用群论结构来进行描述,下面就给出更为形式化的模型。

有限群

群(S,QQ截图20220624091215.jpg)是一个集合S和定义在S上的二进制运算QQ截图20220624091215.jpg,该运算满足下列性质:

  1. 封闭性:对所有a, b∈S,有aQQ截图20220624091215.jpgb∈S。

  2. 单位元:存在一个元素e∈S,称为群的单位元,满足对所有a∈S,eQQ截图20220624091215.jpga=aQQ截图20220624091215.jpge=a。

  3. 结合律:对所有a, b, c∈S,有(aQQ截图20220624091215.jpgb)QQ截图20220624091215.jpgc=aQQ截图20220624091215.jpg(bQQ截图20220624091215.jpgc)。

  4. 逆元:对每个a∈S,存在唯一的元素b∈S,称为a的逆元,满足aQQ截图20220624091215.jpgb=bQQ截图20220624091215.jpga=e。

例如,考察一个熟知的在加法运算下整数Z所构成的群(Z,+):0是单位元,a的逆元为-a。如果群(S,QQ截图20220624091215.jpg)满足交换律,即对所有a, b∈S,有aQQ截图20220624091215.jpgb=bQQ截图20220624091215.jpga,则它是一个交换群。如果群(S,QQ截图20220624091215.jpg)满足|S|<∞,则它是一个有限群。

由模加法与模乘法所定义的群

通过对模n运用加法与乘法运算,可以得到两个有限交换群,其中n是正整数。这些群基于31.1节中定义的整数模n所形成的等价类。

我们需要合适的二元运算来定义Zn上的群,该运算可以通过重新定义普通的加法运算与乘法运算得到。Z上的加法与乘法运算很容易定义,因为两个整数的等价类唯一决定了其和或积的等价类。也就是说,如果a=a' (mod n)和b=b' (mod n),那么

QQ截图20220624093645.jpg

因此,定义模n加法与模n乘法如下(分别用+n和·n表示):

QQ截图20220624093758.jpg

(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)的运算表。

QQ截图20220624094305.jpg

图31-2两个有 限群,其等价类由其代表元素表示。(a)群(Z6, +6)。(b)群(Z15*,·15)

定理31.12  系统(Zn,+n)是一个有限交换群。

证明  式(31. 18)表明(Zn,+n)是封闭的。由+满足交换律与结合律可以推出+n满足交换律与结合律:

QQ截图20220624094716.jpg

(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*:

QQ截图20220624095205.jpg

其中定义在群上的运算是模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*,而且

QQ截图20220624100026.jpg

或者等价地,

QQ截图20220624100113.jpg

因此,[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中的等式说明。例如,下列两种表示等价:

QQ截图20220624100908.jpg

为了方便表示,当从上下文能看出所采用的运算时,有时仅用s来表示群(S,QQ截图20220624091215.jpg)。因此可以用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函数,满足下式:

QQ截图20220624101347.jpg

其中p能整除n的任意素数(如果n是素数,则也包括n本身)。在此不对此公式作出证明。从直观上看,开始时有一张n个余数组成的表{0,1,...,n-1},然后对于每个能整除n的素数p,在表中划掉所有p的倍数。例如,由于45的素约数为3和5,所以

QQ截图20220624101445.jpg

如果p是素数,则Zp*={1, 2, ..,p-1},并且

QQ截图20220624101546.jpg

如果n是合数,则中(n)<n-1,尽管它可以表示为

QQ截图20220624101628.jpg

其中n≥3,此时γ=0.577 215 664...是欧拉常数。当n>5时,一个更简单的(也更松弛)的下界是

QQ截图20220624101745.jpg

式(31.22)中的下界事实上是最好的,因为

QQ截图20220624101856.jpg

子群

如果(S,QQ截图20220624091215.jpg)是一个群,S'QQ截图20220624102026.jpgS,并且(S',QQ截图20220624091215.jpg)也是一个群,则(S',QQ截图20220624091215.jpg)称为(S,QQ截图20220624091215.jpg)的子群。例如,在加法运算下,偶数形成一个整数的子群。下列定理提供了识别子群的一个有用工具。

定理31. 14  (一个有限群的非空封闭子集是一个子群)如果(S, QQ截图20220624091215.jpg)是一个有限群,S'是S的任意一个非空子集并满足对所有a, b∈S',有aQQ截图20220624091215.jpgb∈S',则(S',QQ截图20220624091215.jpg)是(S,QQ截图20220624091215.jpg)的一个子群。

证明  证明过程留作练习31. 3-3。

例如,集合{0,2,4, 6}形成Z8的一个子群,因为它是非空的,而且在+运算下具有封闭性(即在+8下它是封闭的)。

下列定理对子群的规模作出了一个非常有用的限制,证明在此略去。

定理31. 15(拉格朗日定理)  如果(S, QQ截图20220624091215.jpg)是一个有限群,(S',QQ截图20220624091215.jpg)是(S,QQ截图20220624091215.jpg)的一个子群,则|S'|是|S|的一个约数。

对一个群S的子群S',如果S'≠S,则子群S'称为群S的真子群。31. 8节中对Miller- Rabin素数测试过程的分析将用到下面的推论。

推论31.16如果 S'是有限群S的真子群,则|S'I≤|S|/2。

由一个元素生成的子群

定理31.14  给出了一种用于生成有限群(S,QQ截图20220624091215.jpg)的子群的有趣方法:选择一个元素a,根据群上的运算取出由a能生成的所有元素。具体地,对k≥1定义a(k) 如下:

QQ截图20220624105050.jpg

例如,如果取群Z6中的元素a=2,序列a(1),a(2),...为

QQ截图20220624105415.jpg

在群Zn中,有a(k)>=ka mod n。在群Zn*中,有a(k)=ak mod n。由a生成的子群用<a>或(<a>,QQ截图20220624091215.jpg)来表示,其定义如下:

QQ截图20220624105829.jpg

我们称a生成子群<a>,或者a是<a>的生成元。因为S是有限集,所以<a>是S的有限子集,它可能包含S中的所有元素。由QQ截图20220624091215.jpg满足结合律可知,

QQ截图20220624110034.jpg

故<a>具有封闭性,根据定理31.14,<a>是S的一个子群。例如,在Z6中,有

QQ截图20220624110132.jpg

类似地,在Z7*中,有

QQ截图20220624110158.jpg

在群S中a的阶定义为满足a(t)=e的最小正整数t,用ord(a)来表示。

定理31.17  对任意有限群(S, QQ截图20220624091215.jpg)和任意a∈S,一个元素的阶等于它所生成子群的规模,即ord(a)= |<a>|。

证明  设t=ord(a)。 因为a(t)=e并且对k≥1有a(t+k)=a(t)QQ截图20220624091215.jpga(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, QQ截图20220624091215.jpg)是具有单位元e的有限群,则对所有a∈S,

QQ截图20220624113016.jpg

证明由拉格朗日定理可知,ord(a)||S|,因此|S|=0(mod t),其中t=ord(a)。所以

QQ截图20220624113119.jpg


练习

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是正整数,则

QQ截图20220624113413.jpg

31.3-5  证明:对任意n>1和任意a∈Zn*,由式fa(x)=ax mod n所定义的函数fa: Zn*→Zn*是Zn*的一个置换。

相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~