6.22F2m上椭圆曲线公钥的验证 输入：一个有效的F上椭圆曲线系统参数集合及一个相关的公钥P。 输出：对于给定的椭圆曲线系统参数，若公钥P是有效的，则输出“有效”：否则输出“无效”。 a)验证P不是无穷远点O: b)验证公钥P的坐标xp和yp是域F2中的元素；（即验证xp和yp是长度为m的比特串。） c)在Fm中验证y+xpyp=x+a+b: d)验证nP=O: )若通过了所有验证，则输出“有效”：否则输出“无效”。 注：公钥的验证是可选项。 10
6.2.2 F2 m上椭圆曲线公钥的验证 输入：一个有效的F2 m上椭圆曲线系统参数集合及一个相关的公钥P。 输出：对于给定的椭圆曲线系统参数，若公钥P是有效的，则输出“有效”；否则输出“无效”。 a) 验证P不是无穷远点O； b) 验证公钥P的坐标xP和yP是域F2 m中的元素；(即验证xP和yP是长度为m的比特串。) c) 在F2 m中验证y 2 P +xPyP = x 3 P +ax2 P +b； d) 验证[n]P = O； e) 若通过了所有验证，则输出“有效”；否则输出“无效”。 注：公钥的验证是可选项。 10
附录A (资料性附录) 关于椭圆曲线的背景知识 A.1素域Fp A.1.1素域Fn的定义 设p是一个素数，F,由{0,1,2，·，p-1}中p个元素构成，称F,为素域。加法单位元是整数0，乘法 单位元是整数1，F的元素满足如下运算法则： 一加法：设a,b∈Fp,则a+b=r,其中r=(a+b)modp,r∈0p-1。 一乘法：设a,b∈Fn,则a.b=s,其中s=(ab)modp,s∈[0，p-1。 记F是由F中所有非零元构成的乘法群，由于℉是循环群，所以在F中至少存在一个元素g,使 得F,中任一非零元都可以由g的一个方幂表示，称g为F的生成元（或本原元），即F={g0≤i≤p-2}。 设a=g∈F,其中0≤i≤p-2,则a的乘法逆元为：al=gP-1-i。 示例1：素域F,F={0,1} 的加法表如表A1,乘法表如表A2: 表A1 +01 001 110 表A.2 ·01 000 101 示例2：素域Fi9,Fi9={0,1,2,…,18} Fg中加法的示例：10,14∈F19,10+14=24,24mod19=5,则10+14=5。 Fg中乘法的示例：7,8∈F1g,7×8=56,56mod19=18,则7-8=18。 13是F的一个生成元，则F中元素可由13的方幂表示出来： 130=1.13=13.132=17,133=12.134=4.135=14.136=11.137=10.138=16,139=18 1310=6131=2,1312=7,133=15,1314=5,135=8,136=9,1317=3,1318=1。 A.1.2Fn上椭圆曲线的定义 A.1.2.1概述 F。上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示。 A.1.2.2仿射坐标表示 当p是大于3的素数时，F,上椭圆曲线方程在仿射坐标系下可以简化为y2=x3+ax+b，其 中a,b∈Fp,且使得(4a3+27b2)modp≠0。椭圆曲线上的点集记为E(E)={(x,yk,y∈Fn且满足曲线 方程y2=x3+ax+b}U{O},其中O是椭圆曲线的无穷远点。 E(F)上的点按照下面的加法运算规则，构成一个阿贝尔群： a)0+0=0: b)P=(x,y)∈E(F)八{O},P+O=O+P=P: 11
附 录 A (资料性附录) 关于椭圆曲线的背景知识 A.1 素域Fp A.1.1 素域Fp的定义 设p是一个素数，Fp由{0,1,2,··· , p−1}中p个元素构成，称Fp为素域。加法单位元是整数0，乘法 单位元是整数1，Fp的元素满足如下运算法则： ――加法：设a,b ∈ Fp，则a+b = r，其中r = (a+b) modp，r ∈ [0, p−1]。 ――乘法：设a,b ∈ Fp，则a · b = s , 其中s = (a · b) modp，s ∈ [0, p−1]。 记F ∗ p 是由Fp中所有非零元构成的乘法群，由于F ∗ p 是循环群，所以在Fp中至少存在一个元素g，使 得Fp中任一非零元都可以由g的一个方幂表示，称g为F ∗ p 的生成元(或本原元)，即F ∗ p = {g i |0 ≤ i ≤ p−2}。 设a = g i ∈ F ∗ p ，其中0 ≤ i ≤ p−2，则a的乘法逆元为：a −1 = g p−1−i。 示例1：素域F2，F2 = {0,1} F2的加法表如表A.1，乘法表如表A.2： 表A.1 + 0 1 0 0 1 1 1 0 表A.2 · 0 1 0 0 0 1 0 1 示例2：素域F19，F19 = {0,1,2,··· ,18} F19中加法的示例：10,14 ∈ F19，10+14=24，24mod19=5，则10+14=5。 F19中乘法的示例：7,8 ∈ F19，7×8=56，56mod19=18，则7·8=18。 13是F ∗ 19 的一个生成元，则F ∗ 19 中元素可由13的方幂表示出来： 130 = 1,131 = 13,132 = 17,133 = 12,134 = 4,135 = 14,136 = 11,137 = 10,138 = 16,139 = 18, 1310 = 6,1311 = 2,1312 = 7,1313 = 15,1314 = 5,1315 = 8,1316 = 9,1317 = 3,1318 = 1。 A.1.2 Fp上椭圆曲线的定义 A.1.2.1 概述 Fp上椭圆曲线常用的表示形式有两种：仿射坐标表示和射影坐标表示。 A.1.2.2 仿射坐标表示 当p是大于3的素数时，Fp上椭圆曲线方程在仿射坐标系下可以简化为y 2 = x 3 + ax + b ，其 中a,b ∈ Fp，且使得(4a 3 +27b 2 ) modp ̸= 0。椭圆曲线上的点集记为E(Fp) = {(x,y)|x,y ∈ Fp且满足曲线 方程y 2 = x 3 +ax+b} ∪ {O}，其中O是椭圆曲线的无穷远点。 E(Fp)上的点按照下面的加法运算规则，构成一个阿贝尔群： a) O+O = O； b) ∀P = (x,y) ∈ E(Fp)\{O}，P+O = O+P = P； 11
c)P=(x,y)∈E(F)八{O},P的逆元素-P=(x,-y),P+(-P)=O: d山点P=(,)∈E(F)八{O,B=(,)∈E(E八{O},P=(G3)=B+乃≠O,则 3=22-1-2, y3=(x-x3)-y1, 其中 2-y 若x1卡2 2-1 3x12+a 若1=2且B卡-P。 2y1 示例3：有限域Fg上一条椭圆曲线 F9上方程：y2=x3+x+1,其中a=1,b=1。则Fg上曲线的点为： (0.1),(0.18).(2,7,(2,12),(5,6.(5,13).(7,3),(7,16),(9.6),(9,13),(10,2),(10,17),(13,8),(13,11),(142), (14,17),(15,3),(15,16.(16,3).(16,16) 则E(F9)有21个点（包括无穷远点O)。 a)取P=(10,2),P=(9,6),计算P=P+P: 入=2-”=6-2=4」 -石=9-10==-4三15(m0d19), x3=152-10-9=225-10-9=16-10-9=-3=16(m0d19), 3=15×(10-16)-2=15×(-6)-2=3(mod19 所以P=(16,3). b)取B=(10,2),计算[2]B: 入=3+a=3×10+1_3×5+1==4(mod19), 2y1 2×2 4 x3=42-10-10=-4=15(m0d19), y3=4×(10-15)-2=-22=16(mod19), 所以[2P=(15,16). A.1.2.3射影坐标表示 A.1.2.3.1标准射影坐标系 当p是大于3的素数时，Fp上椭圆曲线方程在标准射影坐标系下可以简化为y2z=x+az2+bz, 其中a,b∈Fp,且4a3+27b2≠0modp。椭圆曲线上的点集记为E(Fp)={(x,y,z)x,y,z∈Fn且满足曲 线方程y2z=x3+axz2+bz}。对于(x1y1,1)和(2，y2,2),若存在某个u∈Fn且u卡0，使得：1=2， 1=y2,1=2,则称这两个三元组等价，表示同一个点。 若z≠0，记X=x/2,Y=y/2,则可从标准射影坐标表示转化为仿射坐标表示：Y2=X3+aX+b: 若z=0,(0,1,0)对应的仿射坐标系下的点即无穷远点0。 标准射影坐标系下，E(F)上点的加法运算定义如下： a)0+0=0: b)P=(x,y,)∈E(F)八{O,P+O=O+P=P: c)P=(x,yz∈E(F)八{O},P的逆元素-P=(ux,-y,uz),u∈F且u≠0，P+(-P)=O: d)设点P=(x1,y1,z1)∈E(Fp)八{O},P=(x2,y2,2)∈E(F)八{O},P=B+B=(x3,y,3)≠O, 若P卡P,则： =x12,2=x231,入=入1-2,4=y12,入5=y21,16=入4-5， 7=入+2,18=z12,9=3,110=3g,21=282话-271g,x3=23入11， y3=1入6（⑦g1-入11）-14入10，z3=210入8： 12
c) ∀P = (x,y) ∈ E(Fp)\{O}，P的逆元素−P = (x,−y)，P+ (−P) = O； d) 点P1 = (x1,y1) ∈ E(Fp)\{O}，P2 = (x2,y2) ∈ E(Fp)\{O}，P3 = (x3,y3) = P1 +P2 ̸= O，则 { x3 = λ 2 −x1 −x2 , y3 = λ(x1 −x3)−y1, 其中 λ = y2 −y1 x2 −x1 , 若x1 ̸= x2, 3x1 2 +a 2y1 , 若x1 = x2且P2 ̸= −P1。 示例3：有限域F19上一条椭圆曲线 F19上方程：y 2 = x 3 +x+1，其中a = 1，b = 1。则F19上曲线的点为： (0,1), (0,18), (2,7), (2,12), (5,6), (5,13), (7,3), (7,16), (9,6), (9,13), (10,2), (10,17), (13,8), (13,11), (14,2), (14,17), (15,3), (15,16), (16,3), (16,16), 则E(F19)有21个点(包括无穷远点O)。 a) 取P1 = (10,2)，P2 = (9,6)，计算P3 = P1 +P2： λ = y2 −y1 x2 −x1 = 6−2 9−10 = 4 −1 = −4 ≡ 15 (mod19), x3 = 152 −10−9 = 225−10−9 ≡ 16−10−9 = −3 ≡ 16 (mod19)， y3 = 15×(10−16)−2 = 15×(−6)−2 ≡ 3 (mod19)， 所以P3 = (16,3)。 b) 取P1 = (10,2)，计算[2]P1： λ = 3x 2 1 +a 2y1 = 3×102 +1 2×2 = 3×5+1 4 = 16 4 = 4 (mod19), x3 = 4 2 −10−10 = −4 ≡ 15 (mod19)， y 3 = 4×(10−15)−2 = −22 ≡ 16 (mod19)， 所以[2]P1 = (15,16)。 A.1.2.3 射影坐标表示 A.1.2.3.1 标准射影坐标系 当p是大于3的素数时，Fp上椭圆曲线方程在标准射影坐标系下可以简化为y 2 z = x 3 + axz2 + bz3， 其中a,b ∈ Fp，且4a 3 + 27b 2 ̸= 0 modp。椭圆曲线上的点集记为E(Fp) = {(x,y,z)|x,y,z ∈ Fp且满足曲 线方程y 2 z = x 3 + axz2 + bz3}。对于(x1,y1,z1)和(x2,y2,z2)，若存在某个u ∈ Fp且u ̸= 0，使得：x1 = ux2， y1 = uy2，z1 = uz2，则称这两个三元组等价，表示同一个点。 若z ̸= 0，记X = x/z，Y = y/z，则可从标准射影坐标表示转化为仿射坐标表示：Y 2 = X 3 +aX +b； 若z = 0，(0,1,0)对应的仿射坐标系下的点即无穷远点O。 标准射影坐标系下，E(Fp)上点的加法运算定义如下： a) O+O = O； b) ∀P = (x,y,z) ∈ E(Fp)\{O}，P+O = O+P = P； c) ∀P = (x,y,z) ∈ E(Fp)\{O}，P的逆元素−P = (ux,−uy,uz)，u ∈ Fp且u ̸= 0，P+ (−P) = O； d) 设点P1 = (x1,y1,z1) ∈ E(Fp)\{O}，P2 = (x2,y2,z2) ∈ E(Fp)\{O}，P3 = P1 +P2 = (x3,y3,z3) ̸= O， 若P1 ̸= P2，则： λ1 = x1z2，λ2 = x2z1，λ3 = λ1 −λ2，λ4 = y1z2，λ5 = y2z1，λ6 = λ4 −λ5， λ7 = λ1 +λ2，λ8 = z1z2，λ9 = λ 2 3，λ10 = λ3λ9，λ11 = λ8λ 2 6 −λ7λ9，x3 = λ3λ11， y3 = λ6(λ9λ1 −λ11)−λ4λ10，z3 = λ10λ8； 12
若P=P,则： 1=3x+az,2=2y1z1,3=y7,入4=入3x131,=,入6=-814 x3=26,y3=11(414-16)-25入3,3=2入50 A.1.2.3.2 Jacobian加重射影坐标系 F。上椭圆曲线方程在Jacobian加重射影坐标系下可以简化为y2=x+axz+bz5。其中a,b∈F。, 且4a3+27b2≠0modp。椭圆曲线上的点集记为E(F)={(x,y,zx,yz∈F,且满足曲线方程y2=x3+ az4+b}。对于(m,y1,)和(2，y2,z2),若存在某个u∈F,且u≠0，使得：x1=2x,y1=y2,1=uz2, 则称这两个三元组等价，表示同一个点。 若z≠0，记X=x/z2,Y=y/z3,则可从Jacobian加重射影坐标表示转化为仿射坐标表示：Y2= X3+aX+b: 若z=0,(1,1,0)对应的仿射坐标系下的点即无穷远点0。 Jacobian加重射影坐标系下，E(Fp)上点的加法运算定义如下： a)O+0=0: b)P=(xy,z∈E(E)八{O},P+O=O+P=P: c)P=(x,z∈E(F)八{O},P的逆元素-P=(2x,-y,uz),u∈Fn且u≠0，P+(-P)=O: d)设点B=(x1,y1,z)∈E(F)八{O},B=(,y2,2)∈E(E)八{O},P=B+B=(3,3,3)≠O, 若P卡P,则： 21=x1,2=x2,=入1-2,4=y1,15=y2z,76=入4-，37=入1+22： 8=入4+25，x3=18-入723,1g=723-2x3,y3=(1g入6-入8入)/2,3=z12入3： 若P=P,则： 入1=3+az1,，2=4x1y,入3=8y1,x3=入3-22，为=1(22-x3)-入3，z3=2y131。 A.1.3Fn上椭圆曲线的阶 F(p为大于3的素数)上一条椭圆曲线的阶是指点集E(Fn)中元素的个数，记为#E(Fp)。由Hasse定 理知：p+1-2p/2≤#E(Fp)≤p+1+2p/2。 在素域Fp上，若一条曲线的阶#E(F)=p+1,则称此曲线为超奇异的，否则为非超奇异的。 A2二元扩域F2 A.2.1二元扩域F2m的定义 由2m个元素构成的有限域F2是F的m次扩张，称为m次二元扩域。F2m可以看成F2上维数为m的向 量空间，也就是说，在F中存在m个元素o,1,…,nm-1,使得Va∈F2m,a可以唯一表示为：a=ao0 +a1C1+…+am-1m-1,其中a:∈E,称{o,a1,,nm-}为F3m在E2上的一组基。给定这样一组基，就 可以由向量(ao,a1,…,am-i)来表示域元素。F.在F上的基有多种选择，域元素的加法在不同的基下 的运算规则是一致的，都可以通过向量按分量异或运算得到：域元素的乘法在不同的基下有不同的运 算规则（如用多项式基表示和用正规基表示时其运算规则就不一致）。 A.2.1.1多项式基 设F上m次不可约多项式fx)=xm+fm-1xm-1+…+fxr2+fx+f6(其中f∈F,i=0,1,…,m-1)是 二元扩域F的约化多项式。F2由F上所有次数低于m的多项式构成，即： Fm={am-m-1+am-2xm-2+…+a1x+aola∈E,i=0,l,…,m-1}。 多项式集合{m-1,m-2,…,x,1}是F作为向量空间在F上的一组基，称为多项式基。 13
若P1 = P2，则： λ1 = 3x 2 1 +az2 1，λ2 = 2y1z1，λ3 = y 2 1，λ4 = λ3x1z1，λ5 = λ 2 2，λ6 = λ 2 1 −8λ4， x3 = λ2λ6，y3 = λ1(4λ4 −λ6)−2λ5λ3，z3 = λ2λ5。 A.1.2.3.2 Jacobian加重射影坐标系 Fp上椭圆曲线方程在Jacobian加重射影坐标系下可以简化为y 2 = x 3 + axz4 + bz6。其中a,b ∈ Fp， 且4a 3 + 27b 2 ̸= 0 modp。椭圆曲线上的点集记为E(Fp) = {(x,y,z)|x,y,z ∈ Fp且满足曲线方程y 2 = x 3 + axz4+bz6}。对于(x1,y1,z1)和(x2,y2,z2)，若存在某个u ∈ Fp且u ̸= 0，使得：x1 = u 2 x2，y1 = u 3 y2，z1 = uz2， 则称这两个三元组等价，表示同一个点。 若z ̸= 0，记X = x/z 2，Y = y/z 3，则可从Jacobian加重射影坐标表示转化为仿射坐标表示：Y 2 = X 3 +aX +b； 若z = 0，(1,1,0)对应的仿射坐标系下的点即无穷远点O。 Jacobian加重射影坐标系下，E(Fp)上点的加法运算定义如下： a) O+O = O； b) ∀P = (x,y,z) ∈ E(Fp)\{O}，P+O = O+P = P； c) ∀P = (x,y,z) ∈ E(Fp)\{O}，P的逆元素−P = (u 2 x,−u 3 y,uz)，u ∈ Fp且u ̸= 0，P+ (−P) = O； d) 设点P1 = (x1,y1,z1) ∈ E(Fp)\{O}，P2 = (x2,y2,z2) ∈ E(Fp)\{O}，P3 = P1 +P2 = (x3,y3,z3) ̸= O， 若P1 ̸= P2，则： λ1 = x1z 2 2，λ2 = x2z 2 1，λ3 = λ1 −λ2，λ4 = y1z 3 2，λ5 = y2z 3 1，λ6 = λ4 −λ5，λ7 = λ1 +λ2， λ8 = λ4 +λ5，x3 = λ 2 6 −λ7λ 2 3，λ9 = λ7λ 2 3 −2x3，y3 = (λ9λ6 −λ8λ 3 3 )/2，z3 = z1z2λ3； 若P1 = P2，则： λ1 = 3x 2 1 +az4 1，λ2 = 4x1y 2 1，λ3 = 8y 4 1，x3 = λ 2 1 −2λ2，y3 = λ1(λ2 −x3)−λ3，z3 = 2y1z1。 A.1.3 Fp上椭圆曲线的阶 Fp(p为大于3的素数)上一条椭圆曲线的阶是指点集E(Fp)中元素的个数，记为#E(Fp)。由Hasse定 理知：p+1−2p 1/2 ≤ #E(Fp) ≤ p+1+2p 1/2。 在素域Fp上，若一条曲线的阶#E(Fp) = p+1，则称此曲线为超奇异的，否则为非超奇异的。 A.2 二元扩域F2 m A.2.1 二元扩域F2 m的定义 由2 m个元素构成的有限域F2 m是F2的m次扩张，称为m次二元扩域。F2 m可以看成F2上维数为m的向 量空间，也就是说，在F2 m中存在m个元素α0, α1, ···, αm−1，使得∀α∈F2 m，α可以唯一表示为：α = a0α0 + a1α1 + ··· + am−1αm−1，其中ai∈F2，称{α0, α1, ···, αm−1}为F2 m在F2上的一组基。给定这样一组基，就 可以由向量(a0, a1, ···, am−1)来表示域元素α。F2 m在F2 上的基有多种选择，域元素的加法在不同的基下 的运算规则是一致的，都可以通过向量按分量异或运算得到；域元素的乘法在不同的基下有不同的运 算规则(如用多项式基表示和用正规基表示时其运算规则就不一致)。 A.2.1.1 多项式基 设F2上m次不可约多项式f(x)=x m + fm−1x m−1 +···+ f2x 2 + f1x+ f0 (其中fi ∈ F2,i = 0,1,··· ,m−1 )是 二元扩域F2 m的约化多项式。F2 m由F2上所有次数低于m的多项式构成，即： F2 m = {am−1x m−1 +am−2x m−2 +···+a1x+a0|ai ∈ F2,i = 0,1,··· ,m−1}。 多项式集合{x m−1 ,x m−2 ,··· ,x,1} 是F2 m作为向量空间在F2上的一组基，称为多项式基。 13
域元素am-1m-1+am-2xm-2+…十a1x十a相对多项式基可以由长度为m的比特串(am-1am-2…a1ao) 来表示，所以 F2m={(am-1am-2…a1ao)la:∈F2,i=0,1,…,m-1} 乘法单位元1由(00.01)表示，零元由(00.00)表示。域元素的加法和乘法定义如下： 一加法运算 (am-1am-2…a1ao),(bm-1bm-2…b1bo)∈F3m,则(am-1am-2…a1a0)+(bm-1bm-2b1bo）=(cm-1cm-2 …c1co),其中c=a,⊕b,i=0,1,…,m-1,亦即，加法运算按分位异或运算执行。 一乘法运算 ∀(am-1am-2…a1ao）,(bm-1bm-2…b1bo)∈F2w,则(am-1am-2…a1ao)-(bm-1bm-2…b1bo）=(rm-1rm-2 n1ro）,其中多项式(rm-1m-1+rm-2m-2+…+r1x+0)是(am-1xm-1+am-2m-2+…+a1x+ao(bm-1xm-1十 bm-2xm-2+…+b1x+bo)在FE3上modf(x)的余式。 注意，F恰包含2m个元素。记F是由F2中所有非零元构成的乘法群，F是循环群，在F.中至 少存在一个元素g,使得F中任一非零元都可以由g的一个方幂表示，称g为F的生成元（或本原元）， 即：F={g|0≤i≤2m-2}。设a=g∈F,其中0≤i≤2m-2,则a的乘法逆元为：a-l=g2-1-i。 示例4：二元扩域F的多项式基表示 取F上的一个不可约多项式fx)=x+x2+1,则F中的元素是： (00000),(00001),(00010),(00011),(00100),(00101),(00110), (00111),(01000),(01001),(01010),(01011),(01100),(01101), (01110),(01111),(10000),(10001),(10010),(10011),(10100), (10101),(10110),(10111),(11000),(11001),(11010),(11011), (11100),(11101),(11110),(11111). 加法：(11011)+(10011)=(01000) 乘法：(11011)(10011)=(00100) (x2+x3+x+1)(x+x+1)=x8+x3+x+x3+x2+1 =(x+x2+1)(x3+x2+1)+x2 三x2(modf(x) 即x2是(x+x+x+1)(x+x+1)除以f(x)的余式。 乘法单位元是(00001)，a=x是F的一个生成元，则a的方幂为： a°=(00001)，a=(00010),c2=(00100),c3=(01000),c4=(10000,c=(00101), a=(01010),a2=(10100),c8=(01101),c°=(11010)，a0=(10001),c=(00111), a2=(01110),a3=(11100),o4=(11101),a5=(11111),o6=(11011),ax7=(10011), 018=(00011),a9=(00110,c20=(01100),ca21=(11000),c22=(10101),c23=(01111), 024=(11110),2=(11001),026=(10111),c2”=(01011),c28=(10110),029=(01001), 0t30=(10010),a31=(00001）. A.2.1.2三项式和五项式基 A.2.1.2.1概述 三项式基(TPB)和五项式基(PPB)是特殊的多项式基。 A.2.1.2.2三项式基 F上的三项式是形如m+x+1的多项式，其中1≤k≤m-1。 F2的一个三项式基表示是由F2上一个m次不可约三项式决定的，只有某些特定的m值存在这样的 三项式。上述示例4即为F,的三项式基表示。 对192≤m≤512，表A.3给出了存在m次不可约三项式的每一个m值：并对每个这样的m,给出了 最小的k,使得三项式"+x+1在F上是不可约的。 14
域元素am−1x m−1 +am−2x m−2 +···+a1x+a0 相对多项式基可以由长度为m的比特串(am−1am−2 ···a1a0) 来表示，所以 F2 m = {(am−1am−2 ···a1a0)|ai ∈ F2,i = 0,1,··· ,m−1} 乘法单位元1由(00···01)表示，零元由(00···00)表示。域元素的加法和乘法定义如下： ――加法运算 ∀(am−1am−2 ···a1a0)，(bm−1bm−2 ···b1b0)∈F2 m，则(am−1am−2 ···a1a0) + (bm−1bm−2 ···b1b0) = (cm−1cm−2 ···c1c0)，其中ci = ai ⊕bi，i = 0,1,··· ,m−1，亦即，加法运算按分位异或运算执行。 ――乘法运算 ∀(am−1am−2 ···a1a0)，(bm−1bm−2 ···b1b0)∈F2 m，则(am−1am−2 ···a1a0)·(bm−1bm−2 ···b1b0) = (rm−1rm−2 ··· r1r0)，其中多项式(rm−1x m−1+rm−2x m−2+···+r1x+r0)是(am−1x m−1+am−2x m−2+···+a1x+a0)·(bm−1x m−1+ bm−2x m−2 +···+b1x+b0) 在F2上mod f(x)的余式。 注意，F2 m恰包含2 m个元素。记F ∗ 2 m是由F2 m中所有非零元构成的乘法群，F ∗ 2 m是循环群，在F2 m中至 少存在一个元素g，使得F ∗ 2 m中任一非零元都可以由g的一个方幂表示，称g为F ∗ 2 m的生成元(或本原元)， 即：F ∗ 2 m ={g i |0 ≤ i ≤ 2 m −2}。设a = g i ∈ F ∗ 2 m，其中0 ≤ i ≤ 2 m −2，则a的乘法逆元为：a −1 = g 2 m−1−i。 示例4：二元扩域F2 5的多项式基表示 取F2上的一个不可约多项式f(x) = x 5 +x 2 +1，则F2 5中的元素是： (00000)，(00001)，(00010)，(00011)，(00100)，(00101)，(00110)， (00111)，(01000)，(01001)，(01010)，(01011)，(01100)，(01101)， (01110)，(01111)，(10000)，(10001)，(10010)，(10011)，(10100)， (10101)，(10110)，(10111)，(11000)，(11001)，(11010)，(11011)， (11100)，(11101)，(11110)，(11111)。 加法：(11011)+(10011)=(01000) 乘法：(11011)·(10011)=(00100) (x 4 +x 3 +x+1)·(x 4 +x+1) = x 8 +x 7 +x 4 +x 3 +x 2 +1 = (x 5 +x 2 +1)·(x 3 +x 2 +1) +x 2 ≡ x 2 (mod f(x)) 即x 2是(x 4 +x 3 +x+1)·(x 4 +x+1)除以f(x)的余式。 乘法单位元是(00001)，α = x是F ∗ 2 5的一个生成元，则α的方幂为： α 0 = (00001)，α 1 = (00010)，α 2 = (00100)，α 3 = (01000)，α 4 = (10000)，α 5 = (00101)， α 6 = (01010)，α 7 = (10100)，α 8 = (01101)，α 9 = (11010)，α 10 = (10001)，α 11 = (00111)， α 12 = (01110)，α 13 = (11100)，α 14 = (11101)，α 15 = (11111)，α 16 = (11011)，α 17 = (10011)， α 18 = (00011)，α 19 = (00110)，α 20 = (01100)，α 21 = (11000)，α 22 = (10101)，α 23 = (01111)， α 24 = (11110)，α 25 = (11001)，α 26 = (10111)，α 27 = (01011)，α 28 = (10110)，α 29 = (01001)， α 30 = (10010)，α 31 = (00001)。 A.2.1.2 三项式和五项式基 A.2.1.2.1 概述 三项式基(TPB)和五项式基(PPB)是特殊的多项式基。 A.2.1.2.2 三项式基 F2上的三项式是形如x m +x k +1的多项式，其中1 ≤ k ≤ m−1。 F2 m的一个三项式基表示是由F2上一个m次不可约三项式决定的，只有某些特定的m值存在这样的 三项式。上述示例4即为F2 5的三项式基表示。 对192 ≤ m ≤ 512，表A.3给出了存在m次不可约三项式的每一个m值；并对每个这样的m，给出了 最小的k，使得三项式x m +x k +1在F2上是不可约的。 14