密码理论- UESTC 证明:在等式 n+1=C1anC2n1t…Cna1 n+2C1an+1C2an④…④Cna2 两边分别乘以x,xn+1,,再求和,可得 A(x)(al+a,X+. t+anx-) =C[A()(a+a2X+.t+an-jxn-2 +C2x2|A(x)(a1+a2X+.,+an2x"3)+…+Cnx"A(x) 移项(1+cx+…+cm1xn+cnx)A(x) 整理=( a1+a2x+.+anx)+c1x(a1+a2X…a1￥2) +C2x2(a+a2X+..tan-2x n-3) 3)++Cn1a
密码理论---UESTC 证明： 在等式 an+1=c1an c2an-1 … cna1 an+2=c1an+1 c2an … cna2 … 两边分别乘以x n ,xn+1 ,…，再求和，可得 A(x)-(a1+a2x+…+anx n-1 ) =c1x[A(x)-(a1+a2x+…+an-1x n-2 )] +c2x 2 [A(x)-(a1+a2x+…+an-2x n-3 )]+…+cnx nA(x) (1+c1x+…+cn-1x n-1+cnx n )A(x) =(a1+a2x+…+anx n-1 )+c1x(a1+a2x+…+an-1x n-2 ) +c2x 2 (a1+a2x+…+an-2x n-3 )+…+cn-1x n-1a1 移项 整理
密码理论- UESTC 移项(1+c1x+…+cm1xn1+cnx")A(x) E# =(a+a2x+ ta, -)+ x(a+a2X+.+an-jx -2 +c2x2(a1+a2x+…,+an2x3)+…,+Cn1xla1 p(x)4(x)=∑(cnx"∑a1x)=(x) 证毕。 注意:A(x)=0(x) degp(x)≤n-1
密码理论---UESTC (1+c1x+…+cn-1x n-1+cnx n )A(x) =(a1+a2x+…+anx n-1 )+c1x(a1+a2x+…+an-1x n-2 ) +c2x 2 (a1+a2x+…+an-2x n-3 )+…+cn-1x n-1a1 移项 整理 。 p x A x c x a x x n i i j j j n i n i 证 毕 = = − − = − = 1 1 1 ( ) ( ) ( ) ( ) deg ( ) 1 ( ) ( ) : ( ) − = x n p x x A x 注 意
密码理论- UESTC 定理22p(x)q(x)的充要条件是G(px)CcG(q(x) 证明(1)必要性:若px)qx),可设q(x)=p(x)r(x), 因此 p(x) o(x)r(x)o(x)r(x) p(x) p(x)(x) g(x) 所以若{a}∈G(p(x),则{a;}∈G(q(x),即G(p(x) CG(a(x))
密码理论---UESTC 定理2.2 p(x)|q(x)的充要条件是G(p(x)) G(q(x))。 证明 (1)必要性：若p(x)|q(x)，可设q(x)=p(x)r(x)， 因此 所以若{ai }∈G(p(x))，则{ai }∈G(q(x))，即G(p(x)) G(q(x))。 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) q x x r x p x r x x r x p x x A x = = =
密码理论- UESTC (2)充分性:若G(p(x)cG(q(x), vp(x),3{a1}∈G(p(x)以为生成函数 p(x) v以(x)=1,3{a1}eG(p(x)以为生成函数 G(p(x)cG(q(x)…{t;}∈G(q(x) r(x),使{a的生成函数=r(x) q( rlr ()d=(r).(r)b (x)d )r(x) 故p(x)|q(x 上述定理说明可用n级LFSR产生的序列,也可用级 数更多的LFSR来产生
密码理论---UESTC 上述定理说明可用n级LFSR产生的序列，也可用级 数更多的LFSR来产生。 ( )| ( ). , ( ) ( ) ( ) ( ) ( ) ( ) 1 ( ) ( ) ( ), { } ( ( )) ( ( )), { } ( ( )) ( ) 1 ( ) 1, { } ( ( )) ( ) ( ) ( ), { } ( ( )) ( ( )) ( ( )), p x q x q x p x r x q x r x p x q x r x r x a G p x G q x a G q x 。 p x x a G p x 。 p x x x a G p x G p x G q x i i i i 故 使 的生成函数 以 为生成函数 以 为生成函数 若 = = = = (2)充分性：
密码理论- UESTC 定义22设p(x)是GF(2)上的多项式,使p(x)(xP-1)的 最小p称为p(x)的周期或阶
密码理论---UESTC 定义2.2 设p(x)是GF(2)上的多项式，使p(x)|(xp -1)的 最小p称为p(x)的周期或阶