中国科学技术大学：《密码学导论》课程教学资源（PPT课件讲稿）第4章 数论基础（主讲：李卫海）

x3+x2+1 x3+x2+1 +(x2+x+1 X+X+ X X X +X +1 X+1 (x2+X+ 2 2 X+I/X+X +1 X +X +1 X+X X x2+x+1 X +X X +1 +X+1

26 ( ) 3 2 2 3 x x 1 x x 1 x x + + + + + + ( ) 3 2 2 3 2 4 3 5 4 2 5 x x 1 x x 1 x x 1 x x x x x x x x 1 + +  + + + + + + + + + + 2 3 2 3 2 2 x 1 x 1 x x 1 x x x x 1 x 1 x + + + + + + + + ( ) 3 2 2 3 x x 1 x x 1 x x + + − + + +

有限域GF(2)上的多项式计算 令有助于二进制计算机实现 令有限域GF(2 系数对2取模运算 最高次数小于n 多项式对n次素多项式取模运算 令非零元素有逆 可以用扩展 Euclidean算法求逆 密码学导论一中国科学技术大学

有限域GF(2 n )上的多项式计算 ❖ 有助于二进制计算机实现 ❖ 有限域GF(2n ) ▪ 系数对2取模运算 ▪ 最高次数小于n ▪ 多项式对n次素多项式取模运算 ❖ 非零元素有逆 ▪ 可以用扩展Euclidean算法求逆 密码学导论--中国科学技术大学 27

素多项式 ☆任何多项式可以写为:f(x)=q(×)g(×)+r(x) r(x)称为余式 r(×)=fx)modg(×) ☆若不存在余式,则称g(x)整除f(x),g()fx) 令若f(X)除了它本身和1外,不存在其它因式,则称f(×)是不 可约多项式,或既约多项式、素多项式 ☆系数在GF(p)中,以素多项式取模的多项式构成一个域 密码学导论一中国科学技术大学

素多项式 ❖ 任何多项式可以写为：f(x)=q(x)g(x)+r(x) ▪ r(x)称为余式 ▪ r(x)=f(x) mod g(x) ❖ 若不存在余式，则称g(x)整除f(x)，g(x)|f(x) ❖ 若f(x)除了它本身和1外，不存在其它因式，则称f(x)是不 可约多项式，或既约多项式、素多项式 ❖ 系数在GF(p)中，以素多项式取模的多项式构成一个域 密码学导论--中国科学技术大学 28

令例:以(x3+x+1)为模的多项式运算 001 X x2+X+1 X+1 2 +X+1 0 X+1 2 X+X X X+1 x2+xx2+x+1 X2+ x+1「x+1 10×2+x+1x2+Xx2+1x2 x2x2x2+1×2+xx2+x+10 X+1 x2+1 x2+x+1x2+X 0 X+1 X'+X x2+Xx2+X+1 X2+ 1 X+1 0 x2+x+1×2+x+1×2+x +1 X+1 1 0 X X+1 x2+1x2+Xx2+x+1 0 0 0 0 0 0 00 1 000000000 X X+1 x2+1 +xx2+x+1 X+X X+1 x2+x+1x2+1 X+1 x+1x2 +1×2+x+1 1 x+1x2+x+1x2+ x2+1 x2+1 2 X+X+ X+X X+X x2+Xx2+x+11x2+1x+1Xx2 x2+x+1 0×2+X+1x2+1×1x2+Xx2

29 ❖ 例：以(x3+x+1)为模的多项式运算 + 0 1 x x+1 x 2 x 2+1 x 2+x x 2+x+1 0 0 1 x x+1 x 2 x 2+1 x 2+x x 2+x+1 1 1 0 x+1 x x 2+1 x 2 x 2+x+1 x 2+x x x x+1 0 1 x 2+x x 2+x+1 x 2 x 2+1 x+1 x+1 x 1 0 x 2+x+1 x 2+x x 2+1 x 2 x 2 x 2 x 2+1 x 2+x x 2+x+1 0 1 x x+1 x 2+1 x 2+1 x 2 x 2+x+1 x 2+x 1 0 x+1 x x 2+x x 2+x x 2+x+1 x 2 x 2+1 x x+1 0 1 x 2+x+1 x 2+x+1 x 2+x x 2+1 x 2 x+1 x 1 0  0 1 x x+1 x 2 x 2+1 x 2+x x 2+x+1 0 0 0 0 0 0 0 0 0 1 0 1 x x+1 x 2 x 2+1 x 2+x x 2+x+1 x 0 x x 2 x 2+x x+1 1 x 2+x+1 x 2+1 x+1 0 x+1 x 2+x x 2+1 x 2+x+1 x 2 1 x x 2 0 x 2 x+1 x 2+x+1 x 2+x x x 2+1 1 x 2+1 0 x 2+1 1 x 2 x x 2+x+1 x+1 x 2+x x 2+x 0 x 2+x x 2+x+1 1 x 2+1 x+1 x x 2 x 2+x+1 0 x 2+x+1 x 2+1 x 1 x 2+x x 2 x+1

计算上的考虑 令系数是0或1,多项式可以用一个比特串表示 加法即比特串的异或运算 乘法即比特串的移位及异或运算 ■多项式取模的运算:重复用既约多项式减掉最高次项 令例:在GF(23)中 (x2+1)可以表示为1012,(x2+x+1)可以表示为11 加法:(x2+1)+(x2+X+1)=X 101④111=010 乘法:(X+1)x(x2+1)=x3+x2+x+1; 0112×1012=(1012)<<1:(1012)<<0=1111 多项式取模:(x3+x2+x+1)mod(x3+x+1)=x2 11112mod10112=1111210112=100 密码学导论一中国科学技术大学

计算上的考虑 ❖ 系数是0或1，多项式可以用一个比特串表示 ▪ 加法即比特串的异或运算 ▪ 乘法即比特串的移位及异或运算 ▪ 多项式取模的运算：重复用既约多项式减掉最高次项 ❖ 例：在GF(23 )中， ▪ (x2+1)可以表示为1012 ，(x2+x+1)可以表示为1112 ▪ 加法：(x2+1) + (x2+x+1) = x ； 1012⊕1112 = 0102 ▪ 乘法：(x+1)×(x2+1) = x3+x2+x+1 ； 0112×1012 = (1012 )<<1⊕(1012 )<<0 =11112 ▪ 多项式取模：(x3+x2+x+1) mod (x3+x+1) = x2 11112 mod 10112 = 11112⊕10112= 1002 密码学导论--中国科学技术大学 30