基于余数系统与置换多项式的高速长周期伪随机序列生成方法

A Method of Generating High Speed and Long Period Pseudo-random Sequence Based on Residue Number System and Permutation Polynomial

低复杂度长周期数字伪随机序列在现代加密、通信等系统中具有广泛的应用。该文提出一种基于余数系统和有限域置换多项式的伪随机序列生成方法。该方法基于中国剩余定理将多个互质的小周期有限域随机序列进行单射扩展生成长周期数字伪随机序列,置换多项式的迭代计算在多个并行的小动态范围有限域上进行,从而降低了硬件实现中迭代环路的计算位宽,提高了生成速率。该文还给出构建长周期伪随机序列的置换多项式参数选择方法和中国剩余定理优化方法,在现有技术平台下可轻易实现2^(100)以上的序列周期。同时,该方法具有极大的迭代多项式选择自由度,例如仅在q≡2(mod3)且q≤503的有限域上满足要求的置换多项式就有10905种。硬件实现结构简单,基于Xilinx XC7Z020芯片实现2^(90)的随机序列仅需20个18 kbit的BRAM和少量逻辑资源,无需乘法器,生成速率可达449.236 Mbps。基于NIST的测试表明序列具有良好的随机特性。

Low complexity and long period pseudo-random sequence is widely used in data encryption and communication systems. A method of generating pseudo-random sequence based on Residue Number System （RNS） and permutation polynomials over finite fields is proposed. This method extends several short period sequences into a long period digital pseudo-random sequence based on Chinese Remainder Theorem （CRT）. Several short period sequences are generated by corresponding permutation polynomials over small finite fields paralleUy, thereby reducing the bit width in hardware implementation and increased the generation speed. In order to generate long period sequences, a method to find the permutation polynomial and the the optimazition procedure for CRT are also proposed in this paper. Based on most of current hardware platforms, the proposed method can easily generate the pseudo-random sequence with period over 2^100. Meanwhile, this method has large space to select polynomials. For example, 10905 permutation polynomials can be used when q - 2（mod3） and q _〈 503. Based no Xilinx XCTZ020, it only costs 20 18 kbit BRAMs and a small amount of other resources （no multiplier） to generate a pseudo-random sequence whose period over 2oo, and the generation rate is over 449.236 Mbps. The results of NIST test show that the sequence has good random property and encryption performance.