koorio.com
海量文库 文档专家
当前位置:首页 >> 理学 >>

ch2数学基础


《应用密码学》
( 第2章 数学基础 )

刘嘉勇

第 X 周

上周讲到……
四川大学电子信息学院 1/73

第1章 绪论 ? 第2章 数学基础(初等数论基础 ) 第3章 古典密码学 第4章 香农(Shannon)理论 第5章 分组密码 第6章 公开密钥密码 第7章 密钥管理技术 第8章 报文鉴别与散列函数 第9章 数字签名与身份鉴别

四川大学电子信息学院

2/73

第2章 数学基础(数论导引)
1.素数与互为素数
? 整除与因子的概念: 任给两个整数a,b,其中 b≠0,如果存在一个整数q使得等式 a=qb 成立,此时称b整除a,记为b | a,并称b为a的因子,把a为b的倍数。 否则b不整除a,记为 b∣a 整数具有以下性质:(1)b | a,c | b,则c | a (2)a | 1,则a=±1 (3)对任一b(b≠0), b ∣0 (4) b | g, b | h,则对任意整数m, n有b | (mg+nh)

定理1:任给两个整数a,b,其中 b>0,则存在两个唯一的整数q和r,
使得

a = qb + r
成立。

,0≤r<b
余数,也叫做非负最小剩余 不完全商
四川大学电子信息学院 3/73

? 最大公因数与辗转相除法 定义:设a1,a2,…,an是n个不全为零的整数,若整数d(通常考虑d>0)
是它们之中每一个的因数(子),那么d 就叫做设a1,a2,……,an的一个公因数。 公因数只有有限个,其中最大的一个公因数叫最大公因数(子) 。 记为: ( a1,a2,……,an ), 若( a1,a2,……,an )=1,则称a1,a2,…,an互素。 对于整数a, b,其最大公因数等价的定义形式是: (a, b)=max{k, k | a且k | b} 注意: (a, b)= (-a, b)= (a, -b)= (|a|,|b|)

定理2:设a, b, c是任意不全为零的整数,且 a 除以b, 商q余c a = qb + c ;其中q是整数,
则有 ( a, b )=( b, c )。 即被除数和除数的最大公因子与除数和余数最大公因子相同。

例:(18, 12) = ( 12, 6) = (6, 0) = 6

(11, 10) = ( 10, 1) = (1, 0) = 1
四川大学电子信息学院 4/73

辗转相除法: (Euclid算法,欧几里德算法)
任给两个整数a,b,设 a > b>0,由代余数的除法,有下列等式:

a = bq1 + r1 ,0 < r1 < b, b = r1 q2 + r2 ,0 < r2 < r1 , …… (1) rn-2 = rn-1 qn + rn ,0 < rn < rn-1 rn-1 = rn qn+1 + rn+1 , rn+1 = 0
因为b> r1 > r2 > r3 > …, 故经有限次代余数除法后,总可以得到 一个余数是零,即上式中rn+1 = 0。

定理3:任给整数 a > b > 0 ,则(a, b)就是(1)中最后一个不等于零 的余数,即(a, b)= rn (举例)
定理4:任给整数 a > b > 0 ,则存在两个整数 m, n 使得
(a, b)= m a + n b 由上式,显然有推论:a 和 b 的公因数是(a, b)的因数。
转一次不定方程 四川大学电子信息学院 5/73

例:用辗转相除法求,a=288,b=158的最大公因数和m, n,使ma + nb=(a, b)
288 = 158×1 + 130, 158 = 130 ×1 + 28, 130 = 28 × 4 + 18, 28 = 18 ×1 + 10, 18 = 10 ×1 + 8, 10 = 8 ×1 + 2,
8 = 2 ×4 + 0 再进行逆向迭代,2 = 10-8 ×1 (代2) = 10-(18-10) ×1 (代8) = 10×2 -18 = (28-18 ×1)×2 -18 (代10) = 28×2-18×3 = 28×2-(130-28 × 4 )×3 = 28×14-130×3 = (158-130 ×1 )×14- 130×3 = 158×14-130×17 = 158×14-(288-158×1 )×17 = 158×31-288×17 = - 17 × 288 + 31×158 因此,最大公因数 (a, b) = 2

(代18) (代28) (代130)

所以 m = -17, n=31

6/73

最小公倍数:

a ? 0,b ? 0,有: a,b的最小公倍数: [a,b] ?

a?b (a,b)

练习题:
用辗转相除法求, a =1970,b = 1066的最大公因数和m, n, 使ma + nb=(a, b)

四川大学电子信息学院

7/73

定义:若(a,b)=1,则a与b互素。
? 素数(质数)的概念:
大于1的整数 被称为素数是指 p 的因子仅有1, -1, p, -p。

引理1:若p是素数,a是任意整数,则有 p | a 或 (p, a) = 1 即素数与一个数要么互素,要么可整除该数。 引理2:若p是素数, p | ab ,则 p | a 或 p | b

四川大学电子信息学院

8/73

定理5:任一整数 a ( a >1)都能唯一地分解为以下形式:

a ? p1 1 p2 2 ... pk k 其中,p1 ? p2 ? ... ? pk 是素数,? i ? 0( i ? 1,2,..., k ) 如: 120 ? 2 ? 2 ? 2 ? 3 ? 5 ? 23 ? 3 ? 5
(整数的惟一分解性定理)

?

?

?

推论1:若d | a,则d一定有形式: ? p1 x p2 x ... pk x d
1 2

k

如整数120的所有因子可表示为:

? 0 ? x1 ? ?1 ? ; 这里 ? ...... ?0 ? x ? ? k k ?

2 x1 3x2 5 x3 ,且0 ? x1 ? 3; 0 ? x2 ? 1; 0 ? x3 ? 1

? 120 所有可能的因数个数为: 4 ? 2 ? 2 ? 16 记为: D(120 ) ? 16

推广到一般:a ? Z , 则a的因数个数: D(a) ? (?1 ? 1)(? 2 ? 1)......( ? k ? 1)
四川大学电子信息学院

转一次不定方程
9/73

一个趣味问题 ——“拉灯”问题: 有 50个队员,分别编号为1、2…、50;另有50盏电灯 (为拉线式开关),分别编号为(1)、(2)…、(50)。 规则:若某灯的编号正好是某队员编号的倍数,则该队员就 拉该灯一次。
如1号队员将对50个灯都拉一次; 3号队员将拉(3)、(6)、(9)、……(45)、(48)号灯各一次; …… 50号队员将只拉(50)号灯一次;

问题:最后有哪几盏灯是亮的?(设初始为全熄)。 结果:共7盏灯是亮的。即: (1),(4),(9),(16),(25),(36),(49) 定理5 推论2:a是一个完全平方数
四川大学电子信息学院

D(a)是奇数。
10/73

2.一次不定方程
二元一次不定方程是指: a1x + a2 y = n (1) 其中a1,a2,n是给定的整数, a1,a2 ≠ 0

对" 不失一般性" 可利用性质: ? a b ? a ,b ? Z,有? , ? ( a ,b ) ( a ,b ) ? ? 1 ? ? ?

定理6:方程 (1) 有解的充分必要条件是: ( a1,a2 ) | n
证明: 式 (1) 有解 → (a1,a2 ) | n显然成立,必要条件得证。 当(a1,a2 ) | n,不失一般性,可假设 (a1,a2 ) =1, a1 > 0,a2 >0 由前面定理4,当 (a1,a2 ) =1,存在整数s,t 使: s a1 + t a2= (a1,a2 ) =1 两边乘以n, s na1 + tn a2= n 与(1)式比较,有解: x0 = s n , y0 = t n ,充分条件得证。 此为方程(1)的一组特解,而全部解可由下面定理给出: 定理7:(a1,a2 ) =1,则方程 (1) 一定有解,且全部解(通解)为:

其中,k ? Z, x0, y0是方程 (1) 的一组特解。(证明略)
四川大学电子信息学院 11/73

x = x0 + a2 k y = y0 - a1 k

转同余方程(组)

【例】

解方程 10x + 7y = 24

解:此例, a1=10, a2=7, n=24, 因为(10, 7) = 1 所以方程有解。

由辗转相除法计算满足下式的s和t: 10s + 7t = 1 ,有
10 =7×1+3 7 =3×2+1 1= 7-3×2 = 7-(10-7×1) ×2 = 10×(-2) + 7×3

得 s = -2,t = 3 所以所求特解为: x0 =-2×24=-48,

y0 = 3×24 = 72 所以,方程的完全解为: x = x0 +a2k = -48 +7k y = y0-a1k = 72-10k
四川大学电子信息学院

其中 k ? Z
12/73

3.模运算与同余式
(1) 定义:设 n 是一正整数,a是整数,如果用n除a,得商为q,余数为r,
则 a = qn + r ,0≤ r ≤ n, q = ?a/n? 其中, ?x?为小于或等于x的最大整数。 用a mod n 表示余数 r,则 a = ?a/n? n + a mod n ? 如果 (a mod n ) = (b mod n ) ,则称两整数 a 和 b 模n 同余,记为: a ≡ b mod n 称与 a 模 n 同余的数的全体为 a 的同余类,记为[a],并称 a 为该 同余类的表示元素。(显然,同余类中的每一元素都可作为这个同余类的表示元素) ? 如果 a ≡ 0 mod n ,n|a

(2) 同余的性质:
?如果(a mod n ) = (b mod n ) ,则a ≡ b mod n; (定义) ? a ≡ a mod n; (自反性) ? 如果a ≡ b mod n,则b ≡ a mod n; (对称性) ? 如果则a ≡ b mod n,b ≡ c mod n,则a ≡ c mod n;(传递性)
四川大学电子信息学院 13/73

? a, b对模n同余的充要条件:
如果 n|(a-b),则a ≡ b mod n ;
证明:
必要性:设 a ≡ b mod n ,则有 a= k1n + r, b= k2n + r,0≤r<n 故 a- b = n ( k1-k2 ) 有 显然有, n|(a-b)

充分性:设 a= k1n + r1, b= k2n + r2,
a- b = n(k1-k2)+ r1-r2, 如果有,n|(a- b),必有

0≤r1<n,0≤r2<n

n|(r1-r2) ,而 |r1-r2|< n

所以

r1 = r2, 即 a ≡ b mod n
返回模运算性质

四川大学电子信息学院

14/73

(3) 模运算及性质:
概念:求余数运算 a mod n 将整数 a 映射到非负整数集合Zn= {0, 1, …, n-1}, 称为求余运算,在这个集合上的运算称为模运算。

模运算性质:模n下的算术运算性质
下面设 a, b, c, d 都是整数,而 n 为正整数,有模运算性质: ? (a±b)mod n = [(a mod n)±(b mod n )] mod n

证明: 设 a mod n = ra , b mod n = rb ,有:
a =jn + ra , b = kn + rb ,j,k分别为两个整数。有: (a±b)mod n =(jn + ra ± kn ± rb ) mod n = (ra±rb + jn±kn) mod n = (ra±rb) mod n = [(a mod n)±(b mod n )] mod n ? (a×b)mod n = [(a mod n)×(b mod n )] mod n (证明:作业4-3)
四川大学电子信息学院

15/73

?满足交换律、结合律、分配律、恒等、加法逆元。(证明略)
交换律:
结合律: 分配律: 恒等:

(a * b) mod n = (b * a) mod n

; “ * ”可为 +、×
; “ * ”可为 +、×

[ a * ( b * c) ] mod n = [( a * b ) * c ] mod n ( 0 + a ) mod n = ( 1×a ) mod n = a mod n

[ a ×( b + c) ] mod n = [ a ×b + a ×c) ] mod n

加法逆元: 对每一个w ∈Zn ,存在一个u,使得 w + u=0 mod n 记为,u = -w,显然,在模n下, -w= n -w

? 如果

a ≡ b mod n c ≡ d mod n 则有 (1) (a±c) ≡ (b±d) mod n ;特例: a±c ≡ b ±c mod n 更一般式: (ax + cy) ≡ (bx + dy) mod n x, y为任意整数 (2) ac ≡ bd mod n ;特例: ac ≡ bc mod n (3) f (a) ≡ f (b) mod n ;其中f (x)为任给定的一个整系数多项式

证(1):因为n|(a-b), n|(c-d),故 n| [x(a-b)+y (c-d )] 即,n| [(ax+c y)- ( bx+dy )] 即(ax + cy) ≡ (bx + dy) mod n 证(2):由 n| [c(a-b)+ b (c-d )] 即n| [ac - b d )] 所以 ac ≡ bd mod n

四川大学电子信息学院

16/73

转同余充要条件 【例1】 通过同余式演算证明560-1是56的倍数,223-1是47的倍数。

解: 实际上是要证明: 560≡1(mod56), 223 ≡ 1(mod47) (1) 有: 560 = ( 5 6 ) 10 = (5 3 ) 2 ) 10 ≡ ( ( (5 3) mod56 )2 ) mod56) 10 (mod56) 而 5 3=125≡13(mod56) 于是 (5 3 )2≡169≡1(mod56) ∴ (5 3 ) 2 ) 10 ≡ 1 (mod56) , 于是有: 56∣560-1。 (2) 有: 223 = (26)3· 5 2 26 = 64 ≡17 mod(47) (26)3 ≡17 3 ≡25mod(47) ∴ (26)3· 5 ≡25 ×32 ≡1 mod(47) 2 于是有: 47∣223 -1

【例2】证明:正整数 N 被 9 整除的充要条件是 N 的各位数字(10进制)的和被9整除。
证明:实际上是要证明正整数 N 与N 的各位数字的和在模9下同余。

设 N = a0 +10a1 + 10 2 a2 +……+ 10 k ak ,将N看成是10的整系数多项式, f (x)= a0 +xa1 +x2 a2 +……+xk ak N记为: N = f (10) ,显然有: f (1) = a0 +a1 + a2 +……+ ak 有 10 ≡ 1mod 9 由模运算性质,有 f (10) ≡ f (1) mod 9 即: N ≡ a0 +a1 + a2 +……+ ak mod 9
四川大学电子信息学院 17/73

定理8:加法的可约律与乘法的消去律 如果 (a+b) ≡ (a+c) mod n,则b ≡ c mod n; (加法的可约律) 例如:(5 + 23) ≡(5 + 7) mod 8, 23 ≡ 7md 8 n (乘法的消去律) 如果 (ab) ≡ (ac) mod n,且 (a, n) = d,则 b ? c mod n a 由同余性质(充要条件),有n | a (b ? c),故 | (b ? c)d 证明: d d a n 又由(a, n) ? d,有( , ) ? 1 d d n n 从而 | (b ? c),再由同余充要条件有 : b ? c mod d d 推论1:如果 (ab) ≡ (ac) mod n,且 (a, n) = 1,则b ≡ c mod n。(消去律) 推论2: 如果 (a, n) =1,则 a ×Zn = Zn 。这里, a×Zn 表示 a 与中每一元素 做模 n 乘法。 乘法逆元的存在性: 如果,(a, n) = 1,则 a 在 mod n下有存在一个 x ( x < n ),使得 a x ≡ 1 mod n, x 称为 a 在模n下的乘法逆元。记为,x = a-1 mod n 有逆运算性质: (a×b )-1= a -1 ×b -1 mod n 证明: 设 t =(a×b )-1mod n,有 t-1 = a×b mod n ,再由模运算性质有: a-1×b-1×t-1 = a-1×b-1 × a×b ≡ 1 mod n a-1×b-1 = t = (a×b )-1mod n
四川大学电子信息学院 ( 返回Euler定理 ) 18/73

用辗转相除法求乘法逆元: (扩展的Euclid算法)
要点: 按前面定理4,任给整数 n > a>0 , ,则存在两个整数 x, y 使得 xa + yn = (a, n) 当(a, n) = 1时,即有 xa + yn = 1 等式两端取模n,有 xa mod n=1 即存在一个 x ,使得 a x ≡ 1 mod n。 如何求 x ? ———— 用辗转相除法求乘法逆元,即扩展的Euclid算法
【 例 】计算550 -1mod1769

1769 = 550×3 + 119, 550 = 119×4 + 74, 119 = 74× 1 + 45, 74 = 45×1 + 29, 45 = 29×1 + 16, 29 = 16×1 + 13, 16 = 13×1 + 3 13 = 3 ×4 + 1
正向迭代过程

1 = 13-3 ×4 (代3) =13-(16-13×1)×4 =13×5-16×4 (代13) = (29-16×1 )×5-16×4 = 29×5 -16×9 (代16) = 29×5 -(45-29×1 )×9 =29×14 - 45×9 (代29) = (74-45×1 )×14-45×9 =74×14-45×23 (代45) =74×14-(119-74×1)×23 = 74×37 -119×23 (代74) = (550-119×4 )×37 -119×23=550×37 -119×171(代119) =550×37-(1769 -550×3 )×171= 550×550 -1769×171
逆向迭代过程

有 x = 550, y = -171

所以 550 -1mod 1769 = 550
19/73

练习计算: 17-1 mod 29 = ?; 256-1 mod 337 = ?; 79 -1mod 256 = ?; 79 -1mod 104 = ?;
12

104

175

79

四川大学电子信息学院

20/73

4.剩余类与完全剩余类
全体整数:Z={0, ±1 , ±2 , ±3……} ,前面已定义: a ∈Z,称与 a 模 n 同余的数的全体为 a 的同余类,显然全体整数模 n 的同余类共 有 n 个,他们分别为n k+0, n k+1, n k+2,… n k+(n -1),( k∈z) ,共 n 类; 若取n=4,整数分为 4 类: C0 = { 4k | k∈Z } C1 = { 4k +1 | k∈Z } C2 = { 4k +2 | k∈Z } C3 = { 4k +3 | k∈Z } 所以,当n > 1时,整数分为 n 类: C0 , C1 ,……,Cn-1 Cj = { nk +j | k∈Z } 称Cj为模n的一个剩余类。 ;j = 0,1,2,……,n-1

若从C0 , C1 ,……,Cn-1类中各取一个数构成集合,该集合则称为模n的一组 完全剩余系。
显然,这样的集合有无数个,而最简单的完全剩余系为: 0, 1, 2, ……, n-1 称为非负最小完全剩余或标准完全剩余系。 如,Z模12的标准剩余系为:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
四川大学电子信息学院 21/73

定理9:设a1,a2 ,……,an是 模n的一组完全剩余系。则
( k, n ) = 1 完全剩余系。 k a1, k a2, ……,k an也是一组

5.费马(Fermat)小定理与欧拉(Euler)定理
(这两个定理在公钥密码体制中起着重要作用)

定义:如果一个模n的剩余类里面的数与n互素,就把它叫做一 个与模数n互素的剩余类。

在与模数n互素的的全部剩余类中,各取一数所组成的集 合叫模n的一组缩系。

22/73

欧拉函数
定义:欧拉函数?(n)是一个定义在正整数集上的函数, ?(n) 的值等于小于n且与 n互素的正整数的个数。
例如: ?(6) = 2,?(7) = 6, ?(8) = 4, 特别,当 p 是一个素数,有 ?( p) = p-1 当 n 是两个素数 p 和 q的乘积,则对n = p q,有

?(n) = ?(p q) = ?(p) ?(q) = (p-1)(q-1)
证明: 考虑模 n 的标准完全剩余系为{0,1,…,( pq-1)},而不与n 互素 的元素包括:p因子集合{p,2p,…,(q-1)p},q因子集合{q,2q,…,(p -1)q}和0。 因此,有: ?(n) = pq-[(q-1)+ (p-1) +1] = pq-(p+ q) +1 = (p-1) (q-1) = ?(p) ?(q) 例如: ?(21)= ?(3×7) =?(3)×?(7)= (3-1) ×(7-1)=2 × 6=12

23/73

定理10:模数n的一组缩系含有?(n) 个数。

定理11: 若a1,……,a ?(n) 是?(n) 个与n互素的整数,则
a1,……,a ?(n) 是模n的一组缩系的充要条件是它们两两对模 n不同余。
(从定义看,定理10,11时显然的)

定理12:若(a,n)=1,x 过模 n 的一组缩系 ( 即 x 取x1,……, x?(n) ,且xi与 n 互素 ), 则 a x也过 n 的一组缩系 。
证明:当 x 过模 n 的一组缩系,则 ax 通过?(n) 个整数, 由于(a,n)=1, ( xi, n )=1 所以, ( a xi, n )=1 i, j =1,2,…. ?(n) 若 a xi= a xj,可得 a xi ≡ a xj mod n 与所设 x 过模 n 的一组缩 系矛盾, 故 a x也过 n 的一组缩系。
四川大学电子信息学院 24/73

费马小定理 定理13 :若 p 是素数,且不能整除a,则有: a p-1 ≡ 1 mod p 或 a p ≡ a mod p 显然, a k (p-1) ≡ 1 mod p ∴ a N = a k (p-1) + r≡ a N mod (p-1) mod p

费马小定理应用举例:
计算 7560 mod 31 = ? 7560 = 7560mod (31-1) = 7(31-1)×18+20 ≡ 720 mod31 ≡ 75×75×75×75 mod31 ≡ 5×5×5×5 ≡ 5 mod31
四川大学电子信息学院 25/73

定理14(Euler定理) :设 n , a∈ Z,且(a,n)=1, 则 a ?(n) ≡ 1 mod n

如, a = 3,n = 10; → ?(10) = 4,34 = 81 ≡1 mod 10 a = 2,n = 11; → ?(11) = 10,210 = 1024 ≡1 mod 11
证明:设 r1,……, r?(n) 是模 n 的一组缩系,则由定理12, ar1,……, ar?(n) 也是模 n 的一组缩系, 故

(ar1)(ar1 )……(ar?(n)) ≡ r1……r?(n) mod n

即 由于

a ?(n) r1……r?(n) ≡ r1……r?(n) mod n ( ri, n ) =1 i=1,2,…. ?(n)



( r1……r?(n) , n ) =1

由定理8的推论1(消去律),有: a ?(n) ≡ 1 mod n

得证
26/73

等价形式:
由 有 a ?(n) ≡ 1 mod n a k?(n)+1 ≡ a mod n ( k∈Z )

Euler定理的推论 : 给定两个素数 p, q,以及整数 n = p q 和 m, 其中0 < m < n, 则对于任意整数k,有下列关系成立: m k?(n)+1 = m k(p-1)(q-1)+1 ≡ m mod n (Euler定理要求(a,n) = 1,而其推论将a的条件放宽,可用 于说明RSA密码算法 )

27/73

6.同余方程(组)与中国剩余定理
定理15: 设 (a,n) = 1,n > 0,则同余式: a x ≡ b mod n 恰有一个解。 而 x = ba?(n) -1 就是其唯一解。 思路:让 x 过模 n 一个完全剩余系,x = b1,b2,….,bn-1, ax= ab1, ab2,…., abn-1, 因为(a,n) = 1,所以 ax 也过一个完全剩余系 故一定有一个 xi,使 a xi = b mod n 故有解(其解可代入证明) 定理16: 设 n > 0,则同余式: a x ≡ b mod n 有解的充要条件是: (a, n)|b

且恰有(a, n)个解。

四川大学电子信息学院

28/73

例: (1) 求 2 x ≡ 179 mod 562 的整数解。
因为(2, 562)=2, 而2 | 179, 故同余式没有整数解。

(2) 求 256 x ≡ 179 mod 337 的整数解。
因为(256, 337) = 1, 所以同余式有一个整数解。 解法1:∵ ( 256, 337 ) = 1 ∴ 256在模337有逆元存在。 256-1 mod 337 = 104 用104 乘以同余方程两边,有 104×256 x ≡ 104×179 mod 337 即 x ≡ 104×179 ≡ 81 mod 337 解法2: 考虑二元一次不定方程:256 x+337 y=179 …….(1)

由不定方程有解的充要条件, 当(256, 337) = 1 ,则一次不定方程(1) 一定有解 。 利用扩展的Euclid算法,不定方程(1)的一组特解为: x0 = 104×179 y0 = -79×179 显然,对式(1)等式两端取 mod337,即为同余式256 x ≡ 179 mod 337 所以得同余式解: x = 104×179 ≡ 81 mod 337
四川大学电子信息学院 29/73

中国剩余定理
例子:(孙子算经)今有物不知其数;三三数之余二;五五数之余三; 七七数之余二。问物几何? 设 x 为所求未知数。原问题为求解同余方程组:

? x ? 2 mod 3 ? ? x ? 3 mod 5 ? x ? 2 mod 7 ?
对此方程组的一般解法,在明朝程大位的“算法统 宗”(1593)里有一首歌谣给出了答案: 三人同行七十稀,五树梅花廿一枝, 七子团圆月正半,除百零五便得知。
其解为: x ≡ 70×2 + 21×3 +15×2 mod 105 = 23 一般应如何求解同余方程组?

四川大学电子信息学院

30/73

普通解法:
? x ? 2 mod 3 ? ? x ? 3 mod 5 ? x ? 2 mod 7 ?
(1) [3,5] = 15, (2) [3,7] = 21, 15mod 7 = 1 → 15×2 mod 7 = 2 21mod 5 = 1 → 21×3 mod 5 = 3

(3) [5,7] = 35,

35mod 3 = 2 → 35×1 mod 3 = 2

显然, 15×2 + 21×3 + 35×1 = 128 是一个解(但还不是最小解) 有:128±k × [ 3, 5,7 ] = 233 +k × 105 ;k = 0, ±1, ±2, ……

所以最小正整数解为:x = 23

四川大学电子信息学院

31/73

定理17(中国剩余定理,CRT-China Residue Theorem ):
设m1, m2, …… mk是 k 个两两互素的正整数, 并记 M = m1 m2?? mk,Mi= M/mi, 则同余方程组:

? x ? b1 (mod m1 ) ? x ? b (mod m ) ? 2 2 ? ?...... ? x ? bk (mod mk ) ?
在模 M 同余的意义下有唯一解: x ≡ M1 M1’ b1+ M2 M2’ b2+……+ Mk Mk’ bk mod M 其中 Mi Mi’ ≡ 1 mod mi

(1)

(2)

四川大学电子信息学院

第 2 周

32/73

定理17(中国剩余定理证明 ):
证明:由于( mi , mj) =1,i≠ j,所以 (Mi , mi) = 1
注意到 M = Mi mi 故 所以当 i≠ j, mi | Mj,即 Mj ≡ 0 mod mi,

M1 M1’ b1+ M2 M2’ b2+……+ Mk Mk’ bk (应用模运算性质)
≡ Mi Mi’ bi ≡ bi mod mi 故(2)为(1)的解 ( 注意: Mi Mi’ ≡ 1 mod mi )

另外,设整数y 也能同时满足式(1),由于(2)式是满足(1)的正整数解, 即
y ≡ x mod m1,y ≡ x mod m2,……,y ≡ x mod mk,

也即, m1 | ( x- y ), m2 | ( x- y ), ……, mk | ( x- y )
由于m1, m2, …… mks两两互素,所以 (m1 m2……mk )| ( x- y ) 所以 x ≡ y mod M 即在模 M 同余的意义下(2)是唯一解。
四川大学电子信息学院
第 2 周

33/73

【举例】 11数剩3,12数剩2,13数剩1,求本数。
解:依题意有,

? x ? 3 mod11 ? ? x ? 2 mod12 ? x ? 1mod13 ?
M =11×12 ×13 =1716,



m1 =11,m2 =12,m3 =13,b1 =3, b2 =2, b3 =1,
此时有:

M1 = 1716 /11=156,M2 = 1716 /12=143,M3 = 1716 /13=132

而M1’ 为一正整数,它满足:M1 M1’ ≡ 1 mod 11,
即1 ≡ M1 M1’ ≡156 M1’ mod 11 ≡2 M1’ mod 11 ,易得 M1’ = 6 (可用扩展Euclid算法求得:M1’ = M1-1 mod m1 = 156-1 mod 11 = 2-1 mod 11 )

同理,可求出:M2’ = 11, M3’ = 7
由CRT,得解:x ≡ b1 M1 M1’ + b2 M2 M2’ + b3 M3 M3’ ≡ 3 ×156 ×6 + 2 ×143 ×11 + 1 ×132 ×7

≡14mod 1716
所以,完全解为: x =14 + 1716 k (k=0,1,2,……)
34/73 四川大学电子信息学院

中国剩余定理的主要应用:
1、求解同余方程组(模M下的唯一解); 2、在模M下可将一个非常大的数N,用一组较小的数组成的 k 元组 (b1,b2,……,bk)来表达。 且在模M下, N与(b1,b2,……,bk) 唯一对应。 3、ZM上元素的运算等价于k 元组 对应元素之间的运算,即如果: A ←→ (a1,a2,……,ak), B ←→ (b1,b2,……,bk) 则 (A + B)mod M ←→ [ (a1 + b1) mod m1,??, (ak + bk) mod mk ] (A-B)mod M ←→ [ (a1 - b1) mod m1,??, (ak-bk) mod mk ] (A×B)mod M ←→ [ (a1×b1) mod m1,??, (ak×bk) mod mk ]

四川大学电子信息学院

35/73

中国剩余定理的主要应用(续)
例: 将973 mod 1813用模数为37和49的两个数表示(1813 = 37×49 )。 解:可取 有: N=973,M=1813, m1 =37,m2 =49, b1 = N mod m1 = 973 mod 37=11 b2 = N mod m2 = 973 mod 49=42

所以

973 ←→ (11,42)

若要计算 973mod1813 + 678mod1813,则可先求出: 678 ←→ (678 mod 37 , 678 mod 49) 即 678 ←→ (12 , 41),应用上面性质可得加法表达为: [ (11 + 12) mod 37, (42 +41) mod 49] = (23,34)

四川大学电子信息学院

36/73

7.离散对数
1)求模下的整数幂 由Euler定理,如果 (a, n)=1,则 a ?(n) ≡ 1 mod n 现考虑一般形式, a m ≡ 1 mod n ; m为一正整数 (1) 如果 (a,n)=1,则至少有一整数m ( m = ?(n) )满足该方程。 定义:满足式(1)的最小正整数 m 为模n 下a 的阶(又称次数)。 例: a =7,n=19,则易求出 7 1 ≡ 7 mod 19 , 7 2 ≡ 11 mod 19,7 3 ≡ 1 mod 19, 即7在模19下的阶为3。 由于7 3k+j ≡ 7 3k×7 j ≡ 7 j mod 19 所以, 7 4 ≡ 7 mod 19 , 7 5 ≡ 7 2 mod 19,……,即从7 4 mod 19 开始, 所求的幂出现循环,循环周期为3,即等于元素 7在模19下的阶。 性质1:a的阶m 整除?(n) ,即 m| ?(n) (注意: (a,n)=1 ) 证:若m不能整除?(n) ,可令 ?(n) = k m+r,其中 0 <r≤ m-1,那么 a ?(n) =a k m+ r =(a m ) k a r mod n ≡ a r mod n ≡ 1 mod n (由Euler定理 ) 即 a r ≡ 1 mod n 与m是模n下a 的阶矛盾。

实际上,任意满足式(1)的整数m一定是a的阶的倍数。
四川大学电子信息学院 37/73

定义:如果 a 的阶等于?(n) ,则称a为n的本原元(又称为素根)。
证明: 因为a,n互素,ak与n互素显然。 设 ai ≡ a j mod n ;0≤ i<j≤ ?(n)-1 2,…,a?(n) a,a 有 1 ≡ aj-i mod n 在模n下互不相同,且均与n互素。 j- i ﹤?(n) 与?(n) 是a 的阶矛盾。 性质2:如果a是n的本原元,则 特别地,如果a是素数 p 的本原元,则 a,a2,…,ap-1 (p-1)个数在模 p 下互不相同,且均与 p 互素。 例: n =9, ?(n) = 6,考虑a=2的情况(显然 (2, 9) =1,但9不是素数)
2 1 mod 9=2, 2 2 mod 9=4, 2 3 mod 9=8,
2 4 mod 9=7, 2 5 mod 9=5, 2 6 mod 9=1, 显然,2模9的下的阶为?(9) = 6,所以2为9的本原元。 注意: 模n下的本原元不具备唯一性。

例如, a = 2、3、10、13、14和15都是 模19的本原元。
但并非所有的整数n都有本原元,只有以下形式的整数才有本原元:

2,4,p?,2p?

其中p为奇素数。
38/73

四川大学电子信息学院

2)离散对数 (1)一般对数的概念 指数函数 y = ax ( a﹥0, a≠ 0 ) 的逆函数称为以 a 为底x的对数,

记为:

y =loga x
loga a = 1,
y

有性质: loga 1= 0,

loga x y= loga x + loga y, loga x = y loga x

(2)离散对数的概念
设 p为一素数,a是 p的本原元,则a,a2,…,ap-1 产生1到 p-1之间的所 有值,且每一值仅出现一次。因此: 对于任意 b∈{1,…,p-1},都存在惟一的 i( 0≤i≤p-2 ),使得 b ≡ a i mod p 则称 i 为模 p下以 a 为底 b 的指数,记为: i = inda, p (b) ;也把这样的指数称为离散对数 显然,指数有性质: (1) inda, p (1) = 0 ; (2) inda, p (a) = 1;
四川大学电子信息学院 39/73

注意: a p-1 ≡ 1 mod p

离散对数的概念(续) 以上定义假定模数 p 为素数,对于非素数指数也有类似 定义。但数b的取值不再是b∈{1,…,p-1}。 指数性质(3): 若 a x ≡ a y mod n,其中a,n互素, a是 n的 本原元,则有: x ≡ y mod ?( n)
(可看成是 a x , a y 分别取离散对数)

证明:因a,n互素,所以 a 在模 n下存在逆元 a-1 , 在 a x ≡ a y mod n两边同乘以 (a-1 ) y, 得 a x- y ≡ 1 mod n

由Euler定理,a ?(n) ≡ 1 mod n ,而a是 n的本原元,知存在 一整数 k,使得 x- y = k ?( n) ,即 ?( n) |(x- y ),
所以,x ≡ y mod ?( n)
40/73

离散对数的概念(续) 由性质(3)可得以下两个性质: 性质(4): inda, p ( x y ) = [inda, p ( x ) + inda, p ( y ) ] mod ?( p) 性质(5): inda, p ( x y ) = [ y×inda, p ( x ) ] mod ?( p)

证明:设x ? a

ind a , p ( x )

mod p,y ? a

ind a , p ( y )

mod p,xy ? a

ind a , p ( xy )

mod p,

由模运算性质得:xy mod p ? ( x mod p) ? ( y mod p) mod p 即:a
ind a , p ( xy )

mod p ? (a

ind a , p ( x )

mod p) ? (a

ind a , p ( y )

mod p) mod p

        a   ?

ind a , p ( x )+ind a , p ( y )

mod p

由性质(3)得:ind a , p ( xy ) ? [ind a , p ( x)+ind a , p ( y )]mod ? ( p)
41/73

由以上性质可见离散对数与一般对数的概念极为相似,下 面再强调给出有关离散对数的定义:
设 p 是素数,a是 p的本原元,即a,a2,…,ap-1在mod p下产生1到 p-1

的所有值,所以对任意 b∈{1,…,p-1},有惟一的 i∈{1,…,p-1}使得
b ≡ a i mod p (1)

称 i 为模 p下以 a 为底 b 的离散对数(指数),记为 i = inda, p (b) (2)

重要特性:当 a、p 和 i 已知时,对式(1)可有快速算法比较容易

地求出 b;但如果已知 a、b和 p,要由式(2)求 i 则非常困难。 尤其是当 p 很大时(如150位以上),求离散对数计算不可行。

四川大学电子信息学院

42/73

8.平方剩余
设p是一素数,a小于p,如果方程x2≡a(mod p) 有解,称a是p的平方剩 余(二次剩余),否则称为非平方剩余。

例如: x2≡1 mod 7 有解 x=1,x=6; 实际上。在模 p 的缩系1, 2≡2 mod 7 有解 x=3,x=4; x 2,….,p-1中,有(p 2≡3 mod 7 无解 ; x -1)/2个模 p 的平方剩余, x2≡4 mod 7 有解 x=2,x=5; 和(p-1)/2个模 p 的非平 方剩余。 x2≡5 mod 7 无解 ; x2≡6 mod 7 无解 。 可见共有3个数(1,2,4)是模7的平方剩余,且每个平方 剩余都有两个平方根(既例中的x)。
定理: 设p是素数,a是一整数,a是p的平方剩余的充要条件是: a (p-1)/2 ≡ 1 mod p a是p的非平方剩余的充要条件是: a (p-1)/2 ≡ -1 mod p 【例如】,p=23,a=5, a (p-1)/2 ≡ 5 11mod p = -1 所以,5不是模23的平方剩余。
四川大学电子信息学院 43/73

勒让德符号
但在 p 很大时,前面定理很难得到实际应用。为此引入勒 让德(Legendre)符号,以便给出一个易于实际计算的方法。 定义:
?a? 设p是素数,a是一整数,符号 ? p ? 的定义如下: ? ? ? ?

称符号

?a? ? ? 为Legendre符号。 ? p? ? ?

?0如果a被b整除 ?a? ? ? ? ? ?1如果a是模p的平方剩余 ? p? ? ?-1如果a是模p的非平方剩余

?1? ? 2? ? 4? 例如: ? ? ? ? ? ? ? ? ? 1 ?7? ?7? ?7? ? 3? ?5? ?6? ? ? ? ? ? ? ? ? ? ?1 ?7? ?7? ?7?

前面定理即可表示为: ? a ? ? a ( p ?1) / 2 mod p ? ? ? p?
四川大学电子信息学院 44/73

Legendre符号性质:
定理: 设p是奇素数,a 和 b都不是 p 的整倍数,则
?a? ?b? (1)若a ? b mod p , 则: ? ? ? ? ? ? p? ? p?

? ab ? ? a ? ? b ? (2) ? ? ? ? ? ? ? ? p ? ? p ?? p ?
?a (3) ? ? p ?
2

? ? ?1 ? ?

?1? (5) ? ? ? 1, ? p?

? -1 ? =(-1)( p ?1) / 2 ? ? p ? ?

? a +p ? ? a ? (4) ? ??? ? ? p ? ? p?

? -1 ? ?当p ? 1mod 4时, ? ?=1 ? p ? ? -1 ? 当p ? 3mod 4时, ? ?=-1 ? p ?
四川大学电子信息学院 45/73

Legendre符号性质(续)
?2? ( p 2 ?1) / 8 (6) ?=(-1) ? ? p? ?2? ?当p ? 1或7 mod 8时, ? ?=1 ? p? ?2? 当p ? 3或5 mod 8时, ? ?=-1 ? p?

(7)如果p,q是互异的奇素数,则 ?p? ? q ? =? ?(-1)( p ?1)( q ?1) / 4 ? ? ?q? ? p? ?p? ?q? ?p? ? q ? ? 若p ? q ? 3mod4,有 ? ?=-? ?,否则 ? ?=? ? ?q? ? p? ?q? ? p?

( Legendre符号的互反率)
四川大学电子信息学院 46/73

Jacobi符号: Jacobi符号是Legendre符号的推广。
a n ? p1a1 p2 2 ...,k k 定义Jacobi符号为 pa 定义: 设n是正整数,且

? a ? ?a? ? a ? ? a ? ? ? ? ? ? ? ? ... ? ? ? n ? ? p1 ? ? p2 ? ? pk ?
其中右端的符号是Legendre符号。

a1

a2

ak

Jacobi符号性质:
定理: 设n是正合数,a和b是与n互素的整数,则 ? ab ? ? a ? ? b ? ?a? ?b? (2) ? ? ? ? ? ? ? (1)若a ? b mod p, 则: ? ? ? ? ? ?n? ?n? ? n ? ? n ?? n ? ? a2 ? (3) ? ? ? 1 ? a +n ? ? a ? ? n ? (4) ? ??? ? ? ?

? n ? ?n?

四川大学电子信息学院

47/73

Jacobi符号性质(续)
?1? (5) ? ? ? 1 ?n?
? -1 ? (6) ? =(-1)( n ?1) / 2 ? ? n ? ?2? ( n 2 ?1) / 8 (7) ?=(-1) ? ?n? ?2? ? ?=1 ?n? ?2? ? ?=-1 ?n?

? -1 ? ?当n ? 1或7 mod 8时, ?当n ? 1mod 4时, ? ?=1 ? n ? ? -1 ? 当n ? 3mod 4时, ? ?=-1 当n ? 3或5 mod 8时, ? n ?

四川大学电子信息学院

48/73

定理:(Jacobi符号的互反率)设m,n均为大于2的奇数,则
? m? ( m ?1)( n ?1) / 4 ? n ? ? ? ? (?1) ? ? ?n? ? m?

?m? ?n? ?m? ? n ? 若m≡n ≡3 mod 4,则 ? ? ? ? ? ?, 否则 ? ? ? ? ? ?n? ?m? ? n ? ?m? 以上性质表明:为了计算Jacobi符号(包括Legendre符号作为

它的特殊符号),并不需要求素因子分解式。例如105虽然不是
? 105 ? 素数,在计算Legendre符号? ? 时,可以先把它看作Jacobi符 ? 317 ?

号来计算,又上述两个定理得

一般在计算 ? ?

m? ? 时,如果有必要,可以用m mod n代替m,而互 ?n? 反率用以减小 ? m ? 的分母。 ? ? ?n? 49/73 四川大学电子信息学院

? 105 ? ? 317 ? ? 2 ? ? ??? ??? ? ?1 ? 317 ? ? 105 ? ? 105 ?

Jacobi符号与Legendre符号本质差别的:
?a? Jacobi符号 ? ? 不表示方程 x2≡a mod n是否有解。 ?n?

如 n = p1· 2,a关于p1和p2都不是平方剩余,即 p

x2≡a mod p1和 x2≡a mod p2都无解。
? a ? ? a ? ? a ? ? a ?? a ? 但由于 ? ? ? ? ? ? ?1 ,所以 ? ? ? ? ? ? ? ? 1 ? n ? ? p1 ? ? p2 ? ? p1 ? ? p2 ? a 2≡a mod n 虽无解,但Jacobi符号 ? ?却为1。 也就是说, x ? ? ?n?

举例:考虑方程 x2≡2 mod 3599,由于3599=59×61,所以方程 等价于方程组

? 2? 由于 ? ? ? ?1 ,所以方程组无解,但Jacobi符号 ? 59 ?

? x 2 ? 2 mod 59 ? ? 2 ? x ? 2 mod 61 ?

? 2 ? (35992 ?1) / 8 ?1 ? ? ? (?1) ? 3599 ? 四川大学电子信息学院

Next…

50/73

下面考虑公钥密码体制中一个非常重要的问题。
设n是两个大素数 p 和 q 的乘积.由上述结论,1到p-1之 间有一半数是模 p 的平方剩余,另一半是模 p 的非平方剩余, 对q也有类似结论.另一方面,a是模n的平方剩余,当且仅当a 既是模p的平方剩余也是模 q 的平方剩余.所以对满足 0<a<n, gcd{a, n}=1
?a? ?a? 的a,有一半满足 ? ? ? 1 ,另一半满足 ? ? ? ?1 。 ?n? ?n? ? a ? ?a? ?a? 而在满足 ? ? ? 1 的 a中,有一半满足 ? ? ? ? ? ? 1 ? p? ?q? ?n?

? a ? ?a? 这些a就是模n的平方剩余;另一半满足 ? ? ? ? ? ? ?1 ? p? ?q?

这些a是模n的非平方剩余。

四川大学电子信息学院

51/73

设a是模n的平方剩余,即存在 x 使得 x2 ≡ a mod n 成立, 因 a 既是模 p 的平方剩余,又是模 q 的平方剩余,所以存在 y、z, 使得

(? y) ? a mod p, (? z ) ? a mod q
2 2

x ? ? y mod p, x ? ? z mod q
因此,由中国剩余定理可求得 a mod n的4个平方根,记为

?u mod n 和 ?w mod n ,且 u ? ? w mod n 。
以上结果表明,已知 n 的分解 n = pq,且a是模n的平方剩 余,就可求得 a mod n的4个平方根。

四川大学电子信息学院

52/73

下面考虑相反的问题,即已知a mod n 的两个不同的平方根

(u mod n, w mod n且u ? ? w mod n),就可分解n。
事实上由 u 2 ? w2 mod n 得 (u ? w)(u ? w) ? 0 mod n ,但n不能整除 u ? w 也不能整除 u ? w ,所以必有

p | (u ? w)


, q | (u ? w)

所以

p | (u ? w)

, q | (u ? w)

gcd(n, u ? w) ? p,gcd(n, u ? w) ? q



gcd(n, u ? w) ? p,gcd(n, u ? w) ? q
四川大学电子信息学院 53/73

因此得到了n的分解式。

定理: 求解方程 x2≡a mod n与分解n是等价的。 第2个重要的结论是:当p≡q ≡ 3 mod 4时,a mod n 的两个不同的平方根u和w的Jacobi符号有如下关系:

?u? ? w? ? ? ? ?? ? ?n? ? m?
证明:由以上讨论知,u,w满足 p|(u+w), q|(u-w) 或 p|(u-w), q|(u+w) 即 u ≡-w mod p,u ≡w mod q 或u ≡w mod p,u ≡-w mod q . 若为第一种情况,
? w ?? w ? ? u ? ? u ?? u ? ? ? w ?? w ? ? ?1 ?? w ?? w ? ? w? ?? ? ? ? ?? ?? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? n ? ? p ?? q ? ? p ?? q ? ? p ?? p ?? q ? ?n? ? p ?? q ?

(证毕) 同理可证第2种情况.
四川大学电子信息学院 54/73

9.群论初步
1) 群的概念
群由一个非空集合G组成,在集合G中定义一个二元运算符“· ”,满足:

(1)封闭性:对任意a, b∈G,有:a· b∈G;
(2)结合律:对任何的a, b, c ∈G,有: a· c=( a· )· a· c); b· b c= (b· (3)单位元:存在一个元素l ∈G(称为单位元),对任意元素,有:

a· a=a; l=l·
(4)逆元:对任意a∈G,存在一个元素a-1∈G(称为逆元),使得: a·-1=a-1· a a=l;把满足上述性质的代数系统称为群,记为{G, · }。

(5)交换律:对任意a, b∈G,有:a· a; b=b·
如果一个群满足交换律,则称其为交换群(或Abel群)。 如果一个群的元素是有限的,则称该群为有限群,否则为无限群。 有限群的阶等于群中元素的个数。
四川大学电子信息学院 55/73

群的概念(续) 定义:a3 = a· a, a0=1, a-n = (a-1)n。 a· 如果群中每一个元素都是某一个元素a∈G的幂,ak∈G ( k为整数),则称该群是循环群。循环群是交换群。在循环群 中,认为元素a生成了群G,或a是群G的生成元。 2)群的性质 群具有以下性质: (1)群中的单位元是惟一的; (2)群中的每一个元素的逆元素是惟一的; (3)(消去律)对任意a, b, c∈G,如果a· = a· b c,则 b = c; 同样,如果 b· = c· a a,则 b = c。
四川大学电子信息学院 56/73

10.有限域 (伽罗华域 ,Galois Field )
1)域和有限域

(书P49)

域有一个非空集合F组成,在集合F 中定义了两个二元运算符:“+”和 “·”,并满足: (1)F关于加法“+”是一个交换群,其单位为“0”,a的逆元为-a; (2)F关于乘法“· ”是一个交换群,其单位为“1”,a的逆元为a-1; (3)对任何a, b, c∈F,如果a· b+c ) = ( b+c) · = a· + a· ( a b c; (4)对任意a, b∈F,如果a· b=0,则a = 0 或 b = 0。 这样的集合就称为域,记为{F,+, · }。 定义“减法”:a-b = a + (-b)。 定义“除法”:a/b = a·-1。 b 如果域F只包含有限个元素,则称其为有限域。有限域中元素的个数称 为有限域的阶。 定理1:每个有限域的阶必为素数的幂。 定理2:对任意素数 p与正整数 n,存在pn 阶域,记为GF(pn)。当 n = 1时, 有限域GF( p)也称为素域。 在密码学中,最常用的域一般为素域GF(p)或阶为2m的GF(2m)域。
四川大学电子信息学院 57/73

2)有限域中的计算

(1)有限域GF(p)(或Fp)
有限域GF(p)定义为整数 {0, 1 ,…, p?1}的集合,相应的运算为模 p 的代数运算,即: 加法:如果 a, b∈GF(p),则 a + b≡ r mod p。 乘法:如果 a, b∈GF(p),则 a · ≡s mod p。 b 例4-24 :
+ 0 1 2 3 4

GF(5)的加法和乘法代数运算如图所示。 (书P50)
0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3 * 0 1 2 0 0 0 0 1 0 1 2 2 0 2 4 3 0 3 1 4 0 4 3

3
4

0
0

3
4

1
3

4
2

2
1

模5的加法
四川大学电子信息学院

模5的乘法
58/73

生成元:
令GF*(p)中所有非零元素的集合,可证明在GF(p)中至少存在一个 元素g,使得GF(p)中任意非零元素可以表示成 g的某次幂的形式,这 样的元素g称为GF(p)的生成元(或本原元)。 即 GF*(p) = { gi : 0≤i ≤p-2},

例4-25: 有限域GF(23)={0,1,2, …,22},5是GF(23)的生成元,5的各
次幂分别是:
(书P50)

50=1 55=20 510=9 515=19

51=5 56=8 511=22 516=3

52=2 57=17 512=18 517=15

53=10 58=16 513=21 518=6

54=4 59=11 514=13 519=7

520=12

521=14

522=1

注:均是mod 23 的结果

a = gi ∈GF*(p)的乘法逆元是: a-1=g-i = g(-i) mod (p-1) mod p 。
如:21= 513 mod 23 ,21-1=5-13mod(23-1) mod 23=59mod 23=11 很容易验证, 21 × 11mod 23 = 231mod 23 = 1
四川大学电子信息学院 59/73

(2)有限域GF(2m) (或 F2 )
m

令f(x)=xm + fm-1 xm-1+…+f2 x2+f1 x+f0 ( fi∈GF(2), 0≤i≤m-1),是GF(2) 上次数为m的不可约多项式,即f(x)不能分解为GF(2)上两个次数小于m 的多项式的积。 例如:(x+1)、 ( x2+ x+ 1)、( x3+ x2+ 1)、( x3+ x+ 1)是不可约多项式, 而( x2+ 1)、 ( x3+ 1)、 ( x3+ x2+ x+ 1)就不是不可约多项式。 有限域GF(2m)由GF(2)上所有次数小于m的多项式组成,即 GF(2m)={am-1xm-1+am-2xm-2+…+a1x+a0} 其中,ai∈ {0,1}。

域元素表示方法:
域元素(am-1xm-1+am-2xm-2+…+a1x+a0)通常用长度为m的二进制串 (am
-1am-2…a1a0)表示,使得:

GF(2m) = {(am-1am-2…a1a0)}

其中,ai∈ {0,1}。
60/73

如 m = 8时,多项式元素{x7+x4+ x3+ x2+ 1}表示为(10011101)。
四川大学电子信息学院

有限域GF(2m) (续) 域元素的运算: 设在有限域GF(2m),有元素A和元素B:

A= (am?1am?2…a1a0), B= (bm?1bm?2…b1b0)
加法:A+B = (am?1am?2…a1a0)+(bm?1bm?2…b1b0) = (cm?1cm?2…c1c0) , 其中,ci = (ai+bi) mod 2。 乘法: A · = (am-1am-2…a1a0) · m-1bm-2…b1b0) B (b = (cm-1cm-2…c1c0) 其中,多项式(cm-1xm-1+…+c2x2+c1x+c0) 是多项式 (am-1xm-1+…+a2x2+a1x+a0) · m-1xm-1+bm-2xm-2+…+b2x2+b1x+b0) (b 在GF(2)上被不可约多项式f (x)除所得的剩余多项式。

这种表示的方法称为多项式基表示法。
四川大学电子信息学院 61/73

GF(2m)的生成元 GF(2m)中包含2m个元素。令GF*(2m)表示GF(2m)中所以

非零元素的集合,可证明在GF(2m)中至少存在一个元素g,
使得GF(2m)中任意非零元素可以表示成 g的某次幂的形式, 这样的元素g称为GF(2m)的生成元(或本原元)。 即: GF*(2m) = { g i : 0≤i ≤2m-2} a = g i ∈GF*(2m)的乘法逆元是: a-1 = g-i = g(-i )mod(2
m-1) 。

四川大学电子信息学院

62/73

例3: 用多项式基表示有限域GF(24)

书P51

解:取多项式f (x)=x4+x+1(即10011),可以验证f (x)是GF(24)上 的不可约多项式,则 GF(24)中的元素为:

(0000) (0001) (0010) (0011) (0100) (0101) (0110) (0111) (1000) (1001) (1010) (1011) (1100) (1101) (1110) (1111)
则有(1011)+(1001) = (0010) (1101) · (1001) = (x3+x2+1)(x3+1) = x6+x5+x2+1=(x4+x+1)(x2+x)+(x3+x2+x+1) = (x3+x2+x+1) mod f(x)=(1111)。 GF*(24)可以由一个元素 a = x ( 即 0010 ) 生成,a的各次幂为: a0=(0001) a1=(0010) a2=(0100) a3=(1000) a4=(0011) a5=(0110) a6=(1100) a7=(1011) a8=(0101) a9=(1010) a10=(0111) a11=(1110) a12=(1111) a13=(1101) a14=(1001)
四川大学电子信息学院

a15=a0=(0001)
63/73

11. 计算复杂性理论
计算复杂性理论提供了一种分析不同密码技术和算法的计算复杂性的 方法,它对密码算法及技术进行比较,然后确定其安全性,是密码安全性 的理论基础,涉及算法的复杂性和问题的复杂性两方面,为密码算法的 “实际”安全提供了依据。 计算复杂性理论研究分析问题的有效解法,提供求解问题所需的运算 次数,从而给出问题求解困难性的数量指标,有助于确定密码算法的安全 强度。因为如果破译密码所花费的时间或存储空间的代价超过了密码本身 所保密内容的价值,破译是没有意义的。

1 ) 算法的复杂性
近代密码算法的破译取决于攻击方法在计算机上编程实现时所需的计 算时间(时间复杂性)和占用的硬件资源(空间复杂性)。 算法的复杂性表征了算法在实际执行时所需计算能力方面的信息,通 常它由该算法所要求的最大时间与存储空间大小来确定。由于算法的不同 实例在时间和空间需求上可能有很大的差异,因此通常研究的是算法的平 均复杂度。
四川大学电子信息学院 64/73

空间复杂性与时间复杂性
如果用n表示问题的大小,或输入的长度,则计算复杂性可用 两个参数来表示: ? 运算所需的时间T(n); ? 运算所需的存储空间S(n); 它们都是n的函数,分别反映算法的时间需求和空间需求。

空间复杂性与时间复杂性往往可以相互转化,例如预先计算明 文、密文对并存储起来,分析时只需查询即可,着就将计算的时间 转化为存储空间。 定义: ? 若对某个常数c,算法的运行时间T = O( n c )( c > 0 ),则称该算法 是多项式阶的; ? 若对某个常数a ( a>1) 和多项式h(n),算法的运行时间 T = O( ah(n) ), 则称该算法是指数阶的。
四川大学电子信息学院 65/73

空间复杂性与时间复杂性(续)
假设一台计算机在1秒钟内可以执行100万条指令,输入规模n=106 。
下表列出该台计算机上执行不同时间复杂度算法所需的运行时间。 算法类型 复杂度 n=106时的 运算次数 时间需求

常数 线性 二次方 三次方 指数

O(1) O(n) O(n2) O(n3) O(2n)

1 106 1012 1018 10301030

1微秒 1秒 10天 27397年 3× 10301016年

当T = O( n3 ),在串行机上执行算法在计算上变得不可行了,但 当采用100万个处理器的机器就可在大约10天内完成计算。 但对于T = O( 2n ),即使我们采用上万亿个处理器并行工作,要 执行这类算法在计算上也是不可行的。 因此,如果破译一个密码体制所需的时间是指数阶的,则它是计 算上安全的。
四川大学电子信息学院 66/73

空间复杂性与时间复杂性(续)
许多密码可以采用穷尽搜索整个密钥空间来破译,即尝试每 个可能的密钥断定它是否可解密为有意义的明文或某个已知明文。 若n=2H(k)是密钥空间的大小,则这种破译法的运行时间为: T=O(n)= O(2H(k)) 。 因此,按密钥量计算,时间复杂度是线性的,但以密钥长度算 它且指数的。

确定性算法和非确定性算法:
如果算法的每一步操作结果都是确定的,这样的算法称为确定性算法, 其计算时间就是完成这些确定步骤所需的时间。 如果算法的某些操作结果是不确定的,则这类算法称为不确定性算法, 不确定性算法的计算时间就是使算法成功的操作序列中,所需时间最少的序 列所需的时间。

四川大学电子信息学院

67/73

2) 问题的复杂性
问题的复杂性并不等同于解决问题的算法的复杂性,问题可以根 据解法的复杂性被分成一些复杂性类型,如图所示。

指数时间类 NPC类

NP类 P类

四川大学电子信息学院

68/73

几个术语(略)
P问题:在多项式时间内可以用确定性算法求解的问题称为P问题。 NP问题:在多项式时间内可以用非确定性算法求解的问题称为NP问题。 NPC的NP完全问题:所有的NP问题都可以通过多项式时间转换为一类称之为 NPC的NP完全问题,这是NP类中困难最大的一类问题。 对于一个NPC问题,不存在任何已知的确定性算法在多项式时间内求解 该问题,所以如果能够找到一个计算序列作为解密算法,那么,密码分析者 在不知道计算序列的情形下求解该问题就成为计算上不可行。 由于NPC问题目前没有找到有效的算法,因此适合用来构造密码体制, 现有的密码算法的安全性都是基于NPC问题的,若想破译一个密码算法就相 当于解一个NPC问题。 估计一个密码系统的实际保密性主要需要考虑的因素有两个: (1)密码分析者的计算能力。这取决于密码分析着所拥有的资源条件,最 可靠的方法是假定分析者拥有目前最好的设备; (2)密码分析者所采用的破译算法的有效性。密码分析者总是在搜寻新的 方法来减少破译所需要的计算两。因此,密码设计者的任务就是尽力设计 出一个理想的或完善的密码系统,如果做不到这一点,就必须保证所设计 的系统要使密码分析者付出足够高的代价(时间、费用等)。
四川大学电子信息学院 69/73

本 章 要 点
1.素数与互为素数 2.一次不定方程 3.模运算与同余式 4.剩余类与完全剩余类 5.费马(Fermat)小定理与欧拉(Euler)定理 6. 同余方程(组)与中国剩余定理 7.离散对数 8.平方剩余 9.群论 10.有限域 11. 计算复杂性理论
四川大学电子信息学院 70/73

作业
书P53:4-3,4-7,4-8
1. 2. 3. 计算:3201mod 11;9541432mod17 求(180,252),并将它表示为180和252这两个数的一个带整系数的线 性组合。 计算下列数值 (1) 7503mod81 (3) 81 mod7503

(2) (-7503)mod81 (4) (-81)mod7503

4.

利用扩展的Euclid算法计算: (1)17-1 mod 101 (2)357-1 mod 1234 (3)3125-1 mod 9987 求下列一次同余式的整数解 (1) 660 x ? 595(mod1385) (3) 3 x ? 10(mod29) (2) 258x ?131(mod348) (4) 47x ?89(mod111)
71/73

5.

四川大学电子信息学院

作业 (续)
6. 写出m = 28,33和35在 Zm 上的所有可逆元。 7. 求解下列同余方程组:

?13 x ? 4(mod 99 ) ? ?15 x ? 56 (mod 101)
8. 韩信点兵,有兵一队,若列成5行纵队,则末行1人;成6行纵队, 则末行5人;成7行纵队,则末行4人;成11行纵队,则末行10人, 求兵 数。 (要求使用中国剩余定理 )

四川大学电子信息学院

72/73

1
4

4

四川大学电子信息学院

73/73


推荐相关:

Ch2 地图的数学基础解析.ppt

Ch2 地图的数学基础解析 - 上节内容回顾 1 什么是地图?地图的特性? 地图


随机数学基础ch2_图文.ppt

随机数学基础ch2 - 第二章 随机变量及其分布 §2.1 随机变量的概念 例1


ch2-数学基础_图文.ppt

ch2-数学基础 - 电子商务安全 第2讲. 信息安全数学基础 电子商务安全 第2讲. 信息安全数学基础 信息论 一、信息论基础 、 1、保密系统的数学模型 信源 ...


ch02-数学基础_图文.ppt

ch02-数学基础 - 信息安全原理与技术 郑心炜 第2章 数学基础 ? 主要知识点 主要知识点: --数论 --代数基础 --计算复杂性理论 --单向函数 2011-6-22 Ch2...


ch2 (数学模型)_1_1(1)_图文.pdf

ch2 (数学模型)_1_1(1) - 控制系统CAD 昆明理工大学自动化系 胡蓉 2009年9月 1 主要内容 ? MATLAB基础知识 ? SISO控制系统的分析 ? SISO控制...


ch2 数据库基础知识 (未完)_图文.ppt

ch2 数据库基础知识 (未完) - 第2章 数据库基础知识 本章知识点 2.1 2.2 2.3 2.4 几个基本概念 概念模型 数据模型 关系模型概述 2.1 几个基本概念 ...


信息安全原理与技术ch02-数学基础.ppt

定理2.62.12不作要求 2013-2-27 Ch2-数学基础 10 模运算


信息安全原理与技术ch02-数学基础 统一版_图文.ppt

信息安全原理与技术郭亚军 宋建华 李莉 清华大学出版社 第2章 数学基础 ? 主要知识点: --数论 --代数基础 --计算复杂性理论 --单向函数 2013-8-7 Ch2-数学...


信息安全原理与技术ch02-数学基础_图文.pdf

信息安全原理与技术ch02-数学基础 - 信息安全原理与技术 郭亚军 宋建华 李莉 清华大学出版社 第2章 数学基础 ? 主要知识点: --数论 --代数基础 --计算复杂性...


ch2 (数学模型转换)_图文.pdf

ch2 (数学模型转换) - 第二章 SISO控制系统的分析 ; 2.1 单输入


信息安全数学基础ch2同余.ppt

信息安全数学基础ch2同余 隐藏>> 信息安全数学基础 2.1 同余


规划数学ch2-2.pdf

规划数学ch2-2 - 第二节 单纯形法 一、基本理论 1.基本概念 1)可行域: 可行解: 最优解: 2)基本解: D= { X | AX = b, X ≥ 0} ?max f = ...


CH2C程序基础.ppt

CH2C程序基础_计算机软件及应用_IT/计算机_专业资料。ch2C语言程序基础 解决...表示比较的数学式 C关系表达式 x≤10 x≥10 x≠10 x = 10 x <= 10 x...


ch2(程序设计基础)new_图文.ppt

ch2(程序设计基础)new - 上课的课件,希望可以帮助到有需要的同学~~~... ch2(程序设计基础)new_管理学_高等教育_...也就是说这些数据类型能进行通常的 数学四...


CH2 数控数学原理a_图文.ppt

CH2 数控数学原理a - 2.1 概述 1.插补的概念 2.评价插补算法的指标


数学复习资料-ch2.doc

数学复习资料-ch2 - 一、选择题 1、 y ? f (x) 在点 x 0 处


随机过程Ch2-基本概念与基本类型_图文.pdf

随机过程Ch2-基本概念与基本类型_数学_自然科学_专业资料。随机过程周丽娟 13977292092 第二章 随机过程的概念与基本类型 ? ? ? ? 随机过程的基本概念 随机过程...


信息安全原理与技术ch02-数学基础.ppt

信息安全原理与技术ch02-数学基础信息安全原理与技术ch02-数学基础隐藏>> 信息安全原理与技术郭亚军 宋建华 李莉 清华大学出版社 第2章 数学基础 ? 主要知识点: ...


Ch2 控制系统的数学模型(1)_图文.pdf

Ch2 控制系统的数学模型(1) - ---automatic control--- 内容回顾 1. 基本内容: 自动控制的一般概念:反馈 控制基本控制方式:开环、闭环、复合 控制系统的...


ch2离散数学_图文.ppt

ch2离散数学 - 第二章 命题逻辑等值演算 主要内容 ? 等值式与基本的等值式

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com