1线性同余产生器.ppt

1 线性同余产生器 线性同余产生器：伪随机序列产生器 Xn = (aXn-1+b) mod m Xn为序列中第n个数，Xn-1为序列中第n-1个数 变量a，b和m为常数 X0为密钥或种子 最大周期：m-1 不能用于密码学 2 线性反馈移位寄存器 移位寄存器：一个二进制位序列。需要1位时，所有位都向右移动一位，空出的最左边一位由寄存器中其他位的一个函数来计算。 移位寄存器的输出为1位，通常是最低位。 周期为输出序列开始重复之前的长度。 反馈移位寄存器：由一个移位寄存器和一个反馈函数组成。 线性反馈移位寄存器（LFSR）：反馈函数为寄存器中特定位的异或。 这些位的列表称为一个选择序列。 具有特定选择序列的LFSR会遍历所有的2n-1个内部状态，为最大周期的LFSR。 用1111对4位的LFSR初始化 重复之前的内部状态：1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110 输出序列：1111010110010001… m序列：最大周期的LFSR产生的输出序列。 最大周期的LFSR的选择序列构成的多项式加上常数1为模2的本原多项式，多项式的阶为移位寄存器的长度。 n阶本原多项式：一个不可约多项式，能整除x2n-1+1，但对任意整数d，满足d整除2n-1，多项式不能整除xd+1。 用本原多项式x32+x7+x5+x3+x2+x+1构造最大周期的LFSR： 7.4 多项式的周期 线性递归序列, 线性反馈移位寄存器生成的序列的周期以有限域上多项式的周期为基础. 7.5 有限域的构造 有限域有两类, 一类是阶为素数的, 也就是素域. 另一类是素域的真扩张. 阶相同的有限域是同构的. 素域的构造通常采用整数模一个素数的剩余类环. 为证明相应的结果, 我们需要欧氏整环上的欧几里德算法及其扩展算法. * bn bn-1 … b4 b3 b2 b1 反 馈 函 数 反馈移位寄存器 bn bn-1 … b4 b3 b2 b1 线性反馈移位寄存器 输出位 b4 b3 b2 b1 4位的LFSR 输出位 b32 … b7 b6 b5 b4 b3 b2 b1 32位的最长周期的LFSR 输出位 *