(2)伽罗瓦域GF(2n 系数是二进制0和1的多项式,最高不超过n1次项 一个元素a可被表示成一个位矢量,长度为n,(an1…,a1,ao),每 个长度为n的矢量都对应着GF(2)中的不同元素 例如二进制数110012在GF(25)中可以记作x4x3+1 如何计算? 密码学导论一中国科学技术大学
（2）伽罗瓦域 GF(2n ) ▪ 系数是二进制0和1的多项式，最高不超过n-1次项 ▪ 一个元素a可被表示成一个位矢量，长度为n，(an-1 ,…,a1 , a0 )，每 一个长度为n的矢量都对应着GF(2n)中的不同元素 ▪ 例如二进制数110012在GF(25 )中可以记作x 4+x3+1 ▪ 如何计算？ 密码学导论--中国科学技术大学 21
四、多项式计算 令多项式 f(x) a,x+an1X+…+a1X+a b=∑ aX 令三种多项式运算 使用代数基本规则的普通多项式运算 2.系数在z中的多项式运算; 3.系数在GF(2)中,且多项式被定义为模一个n次多项m(x:有 限域GF(2)上的计算 密码学导论一中国科学技术大学
四、多项式计算 ❖ 多项式 ❖ 三种多项式运算： 1. 使用代数基本规则的普通多项式运算； 2. 系数在Zp中的多项式运算； 3. 系数在GF(2)中，且多项式被定义为模一个n次多项式m(x)：有 限域GF(2n)上的计算 ( ) n n n 1 i n n 1 1 0 i i 0 f x a x a x a x a a x − − = = + + + + = 密码学导论--中国科学技术大学 22
普通多项式运算 ◆加法和减法规则:对应项系数的加或减 ◆乘法规则:各项相乘 令例:令f(×)=x3+x2+2和g(x)=x2-x+1 fx)+g(x)=X3+2x2-X+3 f(x)-g(x)=X3+X+1 f(×)×g(x)=X5+3x2-2X+2 f(x)/g(x)=X+ 密码学导论一中国科学技术大学
普通多项式运算 ❖加法和减法规则：对应项系数的加或减 ❖乘法规则：各项相乘 ❖ 例：令f(x) = x3 + x2 + 2和g(x) = x2 - x + 1 ▪ f(x) + g(x) = x3 + 2x2 - x + 3 ▪ f(x) - g(x) = x3 + x + 1 ▪ f(x) ×g(x) = x5 + 3x2 - 2x + 2 ▪ f(x) / g(x) = x + 2 ……x 密码学导论--中国科学技术大学 23
x3+x2+2 2 X +X 2 X-X+ X一X ⅹ3+2x2-x+3 X +X+1 X +X X+2 X-X+l/X+X +2 X+X +2 X-X-+Ⅹ 4 X -X X +X +2X 22 x2-x+2 x2-2x+2 3x2-2x+2
24 ( ) 3 2 2 3 2 x x 2 x x 1 x 2x x 3 + + + − + + − + ( ) 3 2 2 3 x x 2 x x 1 x x 1 + + − − + + + ( ) 3 2 2 3 2 4 3 5 4 2 5 2 x x 2 x x 1 x x 2 x x 2x x x 2x x 3x 2x 2 + + − + + + − − − + + + − + 2 3 2 3 2 2 2 x 2 x x 1 x x 2 x x x 2x x 2 2x 2x 2 x + − + + + − + − + − +
系数在2n中的多项式运算 ☆系数进行模p运算 令模可以是任意素数,一般取2,此时 所有系数为0或1 ■例:令f(x)=x3+x2+1和g (X)=x2+x+1 f(×)+g(×)=x3+x f(x)×g(x)=5+X+1 密码学导论一中国科学技术大学
系数在Zp中的多项式运算 ❖系数进行模p运算 ❖模可以是任意素数，一般取2，此时 ▪ 所有系数为0或1 ▪ 例：令 f(x) = x3 + x2 + 1和 g(x) = x2 + x + 1 f(x) + g(x) = x3 + x f(x) ×g(x) = x5 + x + 1 密码学导论--中国科学技术大学 25