今例:模8的运算 加法表 乘法表 +01234567 01234567 001234567 000000000 1[12345670 101234567 22345670 202460246 334567012 303614725 445670123 404040404 556701234 505274163 7012345 606420642 0123456 70 65432 逆元表 W0123456 W07654321 W 3
16 ❖例：模8的运算 加法表 乘法表 逆元表 ＋ 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 0 2 2 3 4 5 6 7 0 1 3 3 4 5 6 7 0 1 2 4 4 5 6 7 0 1 2 3 5 5 6 7 0 1 2 3 4 6 6 7 0 1 2 3 4 5 7 7 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 7 2 0 2 4 6 0 2 4 6 3 0 3 6 1 4 7 2 5 4 0 4 0 4 0 4 0 4 5 0 5 2 7 4 1 6 3 6 0 6 4 2 0 6 4 2 7 0 7 6 5 4 3 2 1 w 0 1 2 3 4 5 6 7 -w 0 7 6 5 4 3 2 1 w-1 - 1 - 3 - 5 - 7
模算术运算 o(a1 op a2)mod n =[(ar mod n )]op(a2 mod n)] mod n (a+b)mod n =(a mod n+ b mod n)mod n (a-b ) mod n=(a mod n-b mod n)mod n (ab)mod n =(a mod n. b mod n )mod n ②如果a= b mod n且c= d mod n,则 a+c=(b+d)mod n a-C=(b-d)mod n aC=(bd)mod n ③如果aC= bd mod n且c= d mod n,gcd(n)=1,则a= b mod n ■例:3*2=1*2mod4且2=2mod4,但3≠1mod4 密码学导论一中国科学技术大学
模算术运算 ① (a1 op a2 ) mod n =[(a1 mod n )] op (a2 mod n)] mod n ▪ (a+b) mod n = (a mod n + b mod n) mod n ▪ (a-b) mod n = (a mod n - b mod n) mod n ▪ (a•b) mod n = (a mod n • b mod n) mod n ② 如果 a=b mod n且 c=d mod n，则 ▪ a+c=(b+d) mod n ▪ a-c=(b-d) mod n ▪ a•c=(b•d) mod n ③ 如果ac=bd mod n且c=d mod n，gcd(c,n)=1，则a=b mod n ▪ 例： 3*2=1*2 mod 4 且 2=2 mod 4, 但3≠1 mod 4 密码学导论--中国科学技术大学 17
模运算的性质 令剩余类集( Residues) 定义比n小的非负整数集合为zn:Zn={0,1,(-1) (1)模η的完全剩余类集( Complete Set of Residues mod n): 如果对每个整数a,在集合{「2,rn}中恰有一个余数,使 得 a mod n=,则称{r1,r2…,rn}为模n的完全剩余类集, 0,1,…,n-1形成模n的完全剩余类集。 (2)模n的缩剩余类集( Reduced set of residues mod n) 全剩余集的子集,其中的元素都和n互素(包括1) 令例:n=10, 模n的完全剩余集是{0,1,2,…,9} 模n的缩剩余集是{1,3,7,9} 密码学导论一中国科学技术大学
模运算的性质 ❖ 剩余类集(Residues) ▪ 定义比n小的非负整数集合为Zn： Zn ={0,1,…,(n-1)} (1) 模n的完全剩余类集(Complete Set of Residues mod n)： 如果对每个整数a，在集合{r1 ,r2 ,…,rn}中恰有一个余数ri，使 得 a mod n=ri，则称{r1 ,r2 ,…,rn}为模n的完全剩余类集， {0,1,…,n-1}形成模n的完全剩余类集。 (2) 模n的缩剩余类集(Reduced set of Residues mod n)：完 全剩余集的子集，其中的元素都和n互素（包括1） ❖例：n=10， ▪ 模n的完全剩余集是{0, 1, 2,…,9} ▪ 模n的缩剩余集是 {1, 3, 7, 9} 密码学导论--中国科学技术大学 18
三、有限域GF() alois fie/ds 令有限域在密码学中扮演重要角色 ☆有限域的元素个数是一个素数的幂p,n为正整数,一般 记为GF(p),即 Galois fields,模pn 令关注两种特殊情形 n=1时的有限域,即GF(p) p为2时的有限域,即GF(2) 令最简单的有限域是GF(2),代数运算简述如下 +01 01 W -WW 001 000 00 110 101 111 加 乘 求逆 密码学导论一中国科学技术大学
三、有限域GF(p) Galois Fields ❖ 有限域在密码学中扮演重要角色 ❖ 有限域的元素个数是一个素数的幂pn , n 为正整数，一般 记为GF(pn )，即Galois fields, 模pn . ❖ 关注两种特殊情形 ▪ n=1时的有限域，即GF(p) ▪ p为2时的有限域，即GF(2n) ❖ 最简单的有限域是GF(2)，代数运算简述如下： + 0 1 0 1 w -w w-1 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 1 加 乘 求逆 密码学导论--中国科学技术大学 19
(1)伽罗瓦域GF(p) 当模数是素数p,每个整数a∈[1p-1]与p互素,因而都有唯的 模p的乘法逆。这一组模p的整数,加上算术运算,被称为有限域 一伽罗瓦域 GF(p)的空间是模p的完全剩余类Z:01…p-1} 令例,GF(⑦)上的运算 加法表 乘法表 逆元表 0123456×0123456W0123456 001234560[0000000W[0654321 23456010123456W1-145|2|3|6 2234560120246135 3345601230362514 44560 2340415263 5560123450531642 6601234560654321 密码学导论一中国科学技术大学
（1）伽罗瓦域 GF(p) ▪ 当模数是素数p，每个整数a∈[1,p-1]与p互素，因而都有唯一的 模p的乘法逆。这一组模p的整数，加上算术运算，被称为有限域 —伽罗瓦域 ▪ GF(p) 的空间是模p的完全剩余类Zp：{0,1, … , p-1} ❖ 例，GF(7)上的运算 密码学导论--中国科学技术大学 20 加法表 乘法表 逆元表 ＋ 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1 w 0 1 2 3 4 5 6 -w 0 6 5 4 3 2 1 w-1 - 1 4 5 2 3 6