第二章同余 §2.1同余的定义和基本性质 定义1给定一个正整数m,如果m|(a-b),则称整数a,b 对模m同余,记作a≡b(modm);如果mk(a-b),则称整 数a,b对模m不同余,记作a≠b(modm)。 从定义可以看出,任意的两个整数a,b,要么a≡b(modm), 要么a≠b(modm)。结合整除的性质,我们很容易得到同余 的两个等价定义 (1)整数a,b对模m同余的充要条件是存在一个整数k使得 a=6+km (2)整数a,b对模m同余的充要条件是用m去除整数a和b 所得的最小非负余数相同 在同余式a≡b(modm)中,若0≤b<m,则称b是a对 模m的最小非负剩余,一般用b= amod n来表示;若 l≤b≤m,则称b是a对模m的最小正剩余;若 m/2<b≤m/2(或-m/2≤b<m/2),0≤b<m,则称 b是a对模m的绝对值最小剩余 从关系的角度出发,我们很容易证明同余是一种等价关系, 即同余满足如下性质: 性质1(1)自反性:a≡a(modm); (2)对称性:a= b(mod m)分b≡a(modm); (3)传递性:
第二章 同余 §2.1 同余的定义和基本性质 定义 1 给定一个正整数 m ，如果 m | (a − b) ，则称整数 a,b 对模 m 同余，记作 a b(modm) ；如果 m | (a − b) ，则称整 数 a,b 对模 m 不同余，记作 a b(modm)。 从定义可以看出，任意的两个整数 a,b ，要么 a b(modm)， 要么 a b(modm) 。结合整除的性质，我们很容易得到同余 的两个等价定义： （1）整数 a,b 对模 m 同余的充要条件是存在一个整数 k 使得 a = b + km ； （2）整数 a,b 对模 m 同余的充要条件是用 m 去除整数 a 和 b 所得的最小非负余数相同。 在同余式 a b(modm) 中，若 0 b m ，则称 b 是 a 对 模 m 的最小非负剩余，一般用 b = amodm 来表示；若 1 b m ， 则 称 b 是 a 对 模 m 的 最 小 正 剩 余 ； 若 − m/ 2 b m/ 2(或− m/ 2 b m/ 2)，0 b m ，则称 b 是 a 对模 m 的绝对值最小剩余。 从关系的角度出发，我们很容易证明同余是一种等价关系， 即同余满足如下性质： 性质 1 （1）自反性： a a(mod m) ； （2）对称性： a b(modm) b a(modm) ； （3）传递性：
a= b(mod n),b≡c(modm)→a≡c(modm) 同余其实就是整除的一种符号表示,因此我们在第一章中了 解的整除的一些基本性质都可以用同余符号简单地表示 性质2(1)若a≡b(modm),a"(modn)=b,则 土C≡b±d(modm) ac= bd(mod m) 特别地,对于任意一个整数e,都有 a土e≡b±e(modm),ae≡be(modm); (2)若a≡b(modm),k>0,则 k≡bk( mod mk) (3)若a≡b(modm),d是a,b的公因数,则 (4)若a=b(modm),d|m,d>0,则 ≡b(mod) (5)若aC≡bc(modm),d是c,m的最大公因数,则 a≡b(mod ,进一步,若d=(c,m)=1,则 有a=b(mod (6)若a=b(modm),则a"≡b(modm),进一步 若P(x)=∑Cx是一个整系数多项式(即系数c 是整数,其中Cn≠0),则P(a)=P(b)modm)
a b(mod m),b c(mod m) a c(mod m)。 同余其实就是整除的一种符号表示，因此我们在第一章中了 解的整除的一些基本性质都可以用同余符号简单地表示。 性质 2 （1） 若 a b(modm)， 0 a (mod n) b m = ，则 a c b d(modm) ac bd(mod m) ， 特别地，对于任意一个整数 e ，都有 a e b e(modm)，ae be(mod m) ； （2）若 a b(modm)，k 0 ，则 ak bk(mod mk) ； （3）若 a b(modm)，d是a,b 的公因数，则 (mod ) d m d b d a ； （4）若 a b(modm)，d | m，d 0 ，则 a b(mod d) ； （5）若 ac bc(mod m)，d 是 c,m 的最大公因数，则 (mod ) d m a b ，进一步，若 d = (c,m) =1 ，则 有 a b(modm) ； （6）若 a b(modm) ，则 a b (mod m) n n ，进一步， 若 = = n k k k P x c x 0 ( ) 是一个整系数多项式（即系数 k c 是整数，其中 c n 0 ），则 P(a) P(b)(modm) ；
(7)同余式组a≡b(modm,),j=1,2,…,k同时成 立的充要条件是 a=b(modm,m2,…,m]) (8)(a b)modm=(amod m b mod m)mod m 利用上述关于同余的一些基本性质,我们可以得到检查因数 的两个方法: 例1证明:一个整数能被3或9整除的充要条件是它的十 进位数码的和能被3或9整除 证明:设a是一个正整数。把a写成十进位数的形式: a=a10”+a10″+…+a0≤a<10.i=0.1,n。 因为10≡1(mod3),所以a≡∑a(mod3),由此可知,3|a 当且仅当3|∑a,对于9的情形同理可证。如:a=5783214, ∑a,=5+7+8+3+2+1+4=30,3|30,930,所以3 是a的因数,9不是a的因数。 例2设 a=an1000+a1000″+…+an,0≤a<1000,i=0,1,…,n 证明:a能被7(或11,或13)整除的充要条件是7(或11, 或13)整除∑(-1)a。 证明:因为1001=7×11×13,即1000≡-1(mod7),所以 1000≡(-1)(mod7),即有
（7）同余式组 a b m j k j (mod ), =1,2, , 同时成 立的充要条件是 (mod[ , , , ]) a b m1 m2 mk ； （8） (a b)mod m = (amod mbmod m)mod m。 利用上述关于同余的一些基本性质，我们可以得到检查因数 的两个方法： 例 1 证明：一个整数能被 3 或 9 整除的充要条件是它的十 进位数码的和能被 3 或 9 整除。 证明：设 a 是一个正整数。把 a 写成十进位数的形式： a a a a ai i n n n n n 10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 因为 10 1(mod3) ，所以 (mod3) 0 = n i a ai ，由此可知， 3| a 当且仅当 = n i ai 0 3 | ，对于 9 的情形同理可证。如： a = 5783214， 5 7 8 3 2 1 4 30 0 = + + + + + + = = n i ai ，3 | 30,9 | 30 ，所以 3 是 a 的因数，9 不是 a 的因数。 例 2 设 a a a a ai i n n n n n 1000 1000 ,0 1000, 0,1, , 0 1 = + −1 − ++ = 证明： a 能被 7（或 11，或 13）整除的充要条件是 7（或 11， 或 13）整除 − = n i i i a 0 ( 1) 。 证明：因为 1001 = 71113 ，即 1000 −1(mod 7) ，所以 1000 ( 1) (mod 7) i i − ，即有
a=∑(-1)a(mod7),于是7|a当且仅当7∑(-1)a,对 于11、13的情形同理可证。 因为100≡l(md11),所以在判断一个整数是否被11整除 时用百进制更简单。 下面我们介绍一个很有名的称作弃九法的方法,它利用同余 的性质来验算整数计算结果是否错误。这个方法对于加、减、 乘都适用,为了简便,我们只给出普通乘法的证明。假设我 们由普通乘法运算求出整数a,b的乘积为c,并且设 a=a10"+a10″+…+a1,0≤a<10,i=0,1,…,m b=b10°+b10″+…+b0≤b<10,i=0,1…,n。 C=c10+c-10-+…+c0≤c.<10,i=0,1,…,l。 如果有 a心b≠∑cmod9) 则所计算的结果是错误的。 按照例1,a≡∑a(mod9) ∑b,(mod9) C≡∑c(mod9),由同余的性质当然可以得到 E)b=(0m9y,所以,若bmd9),则 1b≠C 例3设a=17891,b=253786,如果按照普通乘法计算 得到a,b的乘积是c=4540485226,那么按照上面的方法
− = n i i i a a 0 ( 1) (mod7) ，于是 7 | a 当且仅当 − = n i i i a 0 7 | ( 1) ，对 于 11、13 的情形同理可证。 因为 100 1(mod11) ，所以在判断一个整数是否被 11 整除 时用百进制更简单。 下面我们介绍一个很有名的称作弃九法的方法，它利用同余 的性质来验算整数计算结果是否错误。这个方法对于加、减、 乘都适用，为了简便，我们只给出普通乘法的证明。假设我 们由普通乘法运算求出整数 a,b 的乘积为 c ，并且设 a a a a ai i m m m m m 10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 b b b b b i n i n n n n 10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 c c c c c i l i l l l l10 10 ,0 10, 0,1, , 0 1 = + −1 − ++ = 。 如果有 ( )( ) (mod 9) 0 0 0 = = = l k k n j j m i i a b c 则所计算的结果是错误的。 按照例 1 ， (mod9) 0 = m i a ai ， (mod9) 0 = n j b bj ， (mod9) 0 = l k k c c ，由同余的性质当然可以得到 ( )( ) (mod 9) 0 0 0 = = = l k k n j j m i i a b c ，所以，若 ab c(mod9) ，则 ab c。 例 3 设 a =17891，b = 253786 ，如果按照普通乘法计算 得到 a,b 的乘积是 c = 4540485226 ，那么按照上面的方法
a≡26(mod9),b≡3l(mod9),c≡40(mod9),但是 26·31≠40mod9),所以计算有误 从上面的证明我们可以看出这种方法有一个缺陷,当使用弃 九法时,得到的结果虽然是(a)b)=c(md9,也不 能完全肯定原计算是正确的。如在上面例子中,如果有人计 算出来的结果为4540485362,那么用弃九法得到 26.31=41md9),而并未检査出错误来,实际的乘积结果为 4540485326。 例42005年7月26日是星期二,问此天后第2天是星期 几? 解依题意,我们需要求2°mod7,即整数2模7的最小 非负剩余。 因为2mod7=1,所以 2 mod 7=(2%.2)mod7=((2)mod. 2 mod 7)mod7=2 因此,第2天是星期四 现在我们利用同余的理论来计算某一特定的日子是星 期几。例如,香港回归日1997年7月1日是星期几,或者 中华人民共和国成立日是星期几?如果一年的天数可被7整 除,那么所有的日期在每一年中总有相同的星期数,这样日 历的编制将大大简化。但是,目前一年的天数是 365≡1(mod7),而闰年的天数是366≡2mod7),这表明, 在平年一个给定日期的星期数在下一年要加1,碰到闰年这
a 26(mod9) ， b 31(mod9) ， c 40(mod9) ，但是 26 31 40(mod9) ，所以计算有误。 从上面的证明我们可以看出这种方法有一个缺陷，当使用弃 九法时，得到的结果虽然是 ( )( ) (mod 9) 0 0 0 = = = l k k n j j m i i a b c ，也不 能完全肯定原计算是正确的。如在上面例子中，如果有人计 算 出 来 的 结 果 为 4540485362 ， 那 么 用 弃 九 法 得 到 26 31 41(mod 9) ，而并未检查出错误来，实际的乘积结果为 4540485326。 例4 2005 年 7 月 26 日是星期二，问此天后第 1000 2 天是星期 几？ 解 依题意，我们需要求 2 mod 7 1000 ，即整数 1000 2 模 7 的最小 非负剩余。 因为 2 mod 7 1 3 = ，所以 2 mod 7 (2 2)mod 7 ((2 ) mod 7 2mod 7)mod 7 2 1000 999 3 333 = = = 因此，第 1000 2 天是星期四。 现在我们利用同余的理论来计算某一特定的日子是星 期几。例如，香港回归日 1997 年 7 月 1 日是星期几，或者 中华人民共和国成立日是星期几？如果一年的天数可被 7 整 除，那么所有的日期在每一年中总有相同的星期数，这样日 历 的 编 制 将 大 大 简 化 。 但 是 ， 目 前 一 年 的 天 数 是 365 1(mod7) ，而闰年的天数是 366 2(mod 7) ，这表明， 在平年一个给定日期的星期数在下一年要加 1，碰到闰年这
一规律就被破坏了。值得注意的是,目前国际通用的公历是 教皇格里高利十三实行的。当时他召集了很多学者和僧侣讨 论历法改革问题,决定采用业余天文学家利里奥的方案,每 四百年去掉三个闰日,那些世纪数不能被4整除的世纪年不 再算作闰年。 下面我们给出一个方便的计算公式,为此规定0代表星 期日,1代表星期一,2代表星期二,3代表星期三,4代表 星期四,5代表星期五,6代表星期六。注意到闰年所加的 一天不在一年的开头,也不在一年的末尾,而是在2月的29 日,因此我们可以做如下处理:约定3月为第一个月,第二 年的2月作为第十二个月。如1997年7月1日要写成“1997 年5月1日”,1997年1月1日要写成“1996年11月1日”。 假定有一个具体的日期(注意如下的公式和公式的证明 都是经过处理后的时间):第y年m月d日。令n=y%100 (即n为100除y的最小非负余数),C=(y-m)/100,如果 用表示这一日期的星期数,则有如下计算公式: v=(d+[(13m-1)]+n+[,n]+[c]-2c)mod7 如1997年7月1日要写成“1997年5月1日”,代入上式 计算可得w=2,因此1997年7月1日是星期二。 上述公式的证明:首先任取一年如200年作为开始的一年, 并且把这一年的1月1日(实际时间为3月1日)的星期数
一规律就被破坏了。值得注意的是，目前国际通用的公历是 教皇格里高利十三实行的。当时他召集了很多学者和僧侣讨 论历法改革问题，决定采用业余天文学家利里奥的方案，每 四百年去掉三个闰日，那些世纪数不能被 4 整除的世纪年不 再算作闰年。 下面我们给出一个方便的计算公式，为此规定 0 代表星 期日，1 代表星期一，2 代表星期二，3 代表星期三，4 代表 星期四，5 代表星期五，6 代表星期六。注意到闰年所加的 一天不在一年的开头，也不在一年的末尾，而是在 2 月的 29 日，因此我们可以做如下处理：约定 3 月为第一个月，第二 年的 2 月作为第十二个月。如 1997 年 7 月 1 日要写成“1997 年 5 月 1 日”，1997 年 1 月 1 日要写成“1996 年 11 月 1 日”。 假定有一个具体的日期（注意如下的公式和公式的证明 都是经过处理后的时间）：第 y 年 m 月 d 日。令 n = y%100 （即 n 为 100 除 y 的最小非负余数）， c = (y − n)/100 ，如果 用 w 表示这一日期的星期数，则有如下计算公式： ] 2 )mod 7 4 1 ] [ 4 1 (13 1)] [ 5 1 w = (d +[ m − + n + n + c − c 如 1997 年 7 月 1 日要写成 “1997 年 5 月 1 日”，代入上式 计算可得 w = 2 ，因此 1997 年 7 月 1 日是星期二。 上述公式的证明：首先任取一年如 2000 年作为开始的一年， 并且把这一年的 1 月 1 日（实际时间为 3 月 1 日）的星期数
记为d,下面来求第y年1月1日的星期数。注意到平年 的天数为365,且365≡1(mod7),每过一个平年,星期数 将增加1,若不考虑闰年,则相应的第y年1月1日的星期 数为 (d2+100c+n-2000mod7 闰年的天数为366,注意到闰年每4年一次,通常年数被4 整除时是闰年,世纪年通常不是闰年,但当世纪数c可被4 整除时,第100c年仍然是闰年,所以需要对上述星期数增加 如下修正项: (100c+n-2000)]-(c-20)+[(c-20 合在一起即为 (d20+124c+n+[n]+[c]-2485)mod7 再按模7简化后得到 d=(dm-2c+n+En+c)mod7 2005年1月1日(实际为3月1日)是星期二,即 d2m=2,c=20,n=5,代入上式可以求出d=3,即第y年 1月1日的星期数为 (3-2c+n+[:n]+[,c])mod7 下面再来确定从1月1日到该年任意一日的星期数,注意每 月的1日(从1月开始)应该增加的星期数分别为0,3
记为 d2000 ，下面来求第 y 年 1 月 1 日的星期数。注意到平年 的天数为 365，且 365 1(mod7) ，每过一个平年，星期数 将增加 1，若不考虑闰年，则相应的第 y 年 1 月 1 日的星期 数为 (d2000 +100c + n − 2000)mod7 闰年的天数为 366，注意到闰年每 4 年一次，通常年数被 4 整除时是闰年，世纪年通常不是闰年，但当世纪数 c 可被 4 整除时，第 100c 年仍然是闰年，所以需要对上述星期数增加 如下修正项： ( 20)] 4 1 (100 2000)] ( 20) [ 4 1 [ c + n − − c − + c − 合在一起即为 ] 2485)mod 7 4 1 ] [ 4 1 ( 124 [ d y = d2000 + c + n + n + c − 再按模 7 简化后得到 ])mod 7 4 1 ] [ 4 1 ( 2 [ 2000 d d c n n c y = − + + + 2005 年 1 月 1 日（实际为 3 月 1 日）是星期二，即 d2005 = 2,c = 20,n = 5 ，代入上式可以求出 d2000 = 3 ，即第 y 年 1 月 1 日的星期数为 ])mod 7 4 1 ] [ 4 1 d (3 2c n [ n c y = − + + + 下面再来确定从 1 月 1 日到该年任意一日的星期数，注意每 一月的 1 日（从 1 月开始）应该增加的星期数分别为 0，3
5,8,10,13,16,18,21,23,26,29,每月的平均增长 是26,所以m个月的增长数应该为[26m-26],通过修正 被减项,我们可以得到正确的表达式为 [2.6m-2.2]=[(13m-11)],m=1,2,…,12 这个月的第d日的星期数应加上d-1,因此最终第y年m月 d日的星期数为 =d,+[(13m-11)]+d-1 (d+[(13m-1)+n+[H]+[c]-2c)mod7 密码学中有很多模运算,因为计算模n的离散对数和平 方根都很困难,即求解方程 a= b(modn)和x2≡a(modm) 很困难,它们的困难性将给密码体制的安全性带来保证。在 计算机上做模运算要要容易一些,因为它能够限制中间值和 结果的范围。对于模n(m位二进制),做加、减、乘和之间 结果都不会超过2m位。在计算s=a· bmod n时,如果整数 a和b的值都比较小,直接先计算a·b的值,然后对其进行求 模运算。 例5求2的十进制表示中的最后两位数字 在模运算计算中,还有一类问题,常常要对大整数模η和大 整数m,计算 a moa n
5，8，10，13，16，18，21，23，26，29，每月的平均增长 是 2.6，所以 m 个月的增长数应该为 [2.6m − 2.6] ，通过修正 被减项，我们可以得到正确的表达式为 (13 11)], 1,2, ,12 5 1 [2.6m − 2.2] = [ m − m = 这个月的第 d 日的星期数应加上 d −1 ，因此最终第 y 年 m 月 d 日的星期数为 ] 2 )mod 7 4 1 ] [ 4 1 (13 1)] [ 5 1 ( [ (13 11)] 1 5 1 [ d m n n c c w dy m d = + − + + + − = + − + − 密码学中有很多模运算，因为计算模 n 的离散对数和平 方根都很困难，即求解方程 a b(mod n) x 和 (mod ) 2 x a n 很困难，它们的困难性将给密码体制的安全性带来保证。在 计算机上做模运算要要容易一些，因为它能够限制中间值和 结果的范围。对于模 n （ m 位二进制），做加、减、乘和之间 结果都不会超过 2m 位。在计算 s = a bmod n 时，如果整数 a和b 的值都比较小，直接先计算 a b 的值，然后对其进行求 模运算。 例5 求 1000 2 的十进制表示中的最后两位数字。 在模运算计算中，还有一类问题，常常要对大整数模 n 和大 整数 m ，计算 a n m mod
如果按照普通的递归运算 a"modn=((a-modn)a)modn 对于大整数m而言比较费时,须做m-1次乘法,可以对其使 用加速算法。常用的加速算法有两种,一种是减少乘法的次 数,另一种是优化每次乘法 如果将m写成二进制: m=m+m·2+…+m·2, 其中m∈{0,1},i=0,1,2,…k,则模运算可以归纳为 a(a )"-(a )"(modn) 模重复平方算法2.1.1: (1)将m写成二进制: m=m+m.2+…+m22 其中m∈{0,1},i=0,2,…k; (2)i=0, a=a, b=a(modn (3)令i=i+1,a=a(modn),b=b·a;(modn); (4)如果i<k,回到(3); (5)否则,输出b的值,则有a"(modn)=b 此算法至多需要进行[log2m]次平方和[log2m]次乘法。当然 我们也可以对这个算法进行一些改进 a"=(a")(a")…(a")(a"(modn) 模重复平方算法212: 1)将m写成二进制:
如果按照普通的递归运算 a n a n a n m m mod (( mod ) )mod 1 = − ， 对于大整数 m 而言比较费时，须做 m −1 次乘法，可以对其使 用加速算法。常用的加速算法有两种，一种是减少乘法的次 数，另一种是优化每次乘法。 如果将 m 写成二进制： k m = m0 + m1 2 ++ mk 2 ， 其中 m i k i {0,1}, = 0,1,2, ，则模运算可以归纳为 ( ) ( ) ( ) (mod ) 2 2 1 2 1 0 1 a a a a a n k k k k m m m m − m − 模重复平方算法 2.1.1： （1）将 m 写成二进制： k m = m0 + m1 2 ++ mk 2 ， 其中 m i k i {0,1}, = 0,1,2, ； （2）令 i = 0，a0 = a， (mod ) 0 b0 a0 n m = ； （3）令 i = i +1， (mod ) 2 ai+1 = ai n ， (mod ) 1 b 1 b a 1 n mi i i i + + + = ； （4）如果 i k ，回到（3）； （5）否则，输出 k b 的值，则有 k m a (modn) = b 。 此算法至多需要进行 [log ] 2 m 次平方和 [log ] 2 m 次乘法。当然 我们也可以对这个算法进行一些改进 ( ) ( ) ( ) ( )(mod ) 1 0 1 2 1 2 2 a a a a a n m m m m m k k k k − − 模重复平方算法 2.1.2： 1）将 m 写成二进制：
m=m+m·2+…+m·2, 其中m∈{0,l},i=0,12,…k; (2)Ai=k,a,=l b=a"(modn); (3)i=i-1, a=b(modn), b=aa"(modn); (4)如果i>0,回到(3); (5)否则输出b的值,则有a"(modn)=b 算法2.1,2和算法2.1.1执行同样数量的平方和乘法,不过 算法2.1.2是以一个固定的a来做乘法。 对于模幂运算,有时候如果使用固定窗口算法或者滑动窗口 算法,将会达到优化平方运算的目的,减少运算的复杂性。 首先我们简单的介绍一下固定窗口算法:为了计算 a"(modn),我们首先对指数m进行一定的窗口处理,记 k'=[log, m]+l,t t'=k-kt,则m可以进行如下二进 制分块 n=m2-k+m.)-2k .+m 2-k+m 其中 2-2+∴+m m∈{0,1},t=1,2,…,t,j=1,2,…k, m=mn2+…+mn,若r=0,则m2=0。 因此有 C 固定窗口模幂算法2.1.3
k m = m0 + m1 2 ++ mk 2 ， 其中 m i k i {0,1}, = 0,1,2, ； （2）令 i = k ，ak =1 b a (modn) mk k = ； （3）令 i = i −1， (mod ) 2 ai = bi+1 n ， b a a (mod n) mi i i = ； （4）如果 i 0 ，回到（3）； （5）否则输出 0 b 的值，则有 0 a (modn) b m = 。 算法 2.1.2 和算法 2.1.1 执行同样数量的平方和乘法，不过， 算法 2.1.2 是以一个固定的 a 来做乘法。 对于模幂运算，有时候如果使用固定窗口算法或者滑动窗口 算法，将会达到优化平方运算的目的，减少运算的复杂性。 首 先 我 们 简 单 的 介 绍 一 下 固 定 窗 口 算 法 ： 为 了 计 算 a (mod n) m ，我们首先对指数 m 进行一定的窗口处理，记 t k kt k k k = m + t = ], ' = '− ' ' [log ] 1, [ 2 ，则 m 可以进行如下二进 制分块： 0 ' 1 ' 2 1 ' m m 2 m 2 m 2 m k k k kt t k k = t + + + + − − − − 其中 1 2 1 1 2 2 i k ik k mi = mik + m + + m − − − ， m i t j k ij {0,1}, =1,2, , , =1,2, , ， 01 ' 1 m0 m0 ' 2 m t = t + + − ，若 t' = 0,则m0 = 0。 因此有 ( ) ( ) ( ) ( ) 0 ' 1 ' 2 1 ' m m 2 m 2 m 2 m a a a a a k k k kt t k k t − − − − = 固定窗口模幂算法 2.1.3
