基于三项式本原多项式的σ-LFSR实现方案

基于三项式本原多项式的σ-LFSR实现方案 An Implementation Scheme of σ-LFSR Based on Trinomial Primitive Polynomial 王泽辉 WANG Zehui 1 first-author 中山大学数学与计算科学学院 中山大学数学与计算科学学院 School of Mathematics and Computational Science,Sun Yat-sen University School of Mathematics and Computational Science,Sun Yat-sen University 在系数属于有限域的多项式环即有限环上,给出确定型的不可约多项式和本原多项式.利用这些多项式构造一个高效算法,可获得最长周期的输出序列,确定序列的每个值仅耗费2（lbp）次模p加法.给出了一种基于三项式本原多项式的σ-LFSR实现方案.理论分析和计算机模拟结果显示,该σ-LFSR发生器具有优良的随机性并且便于软硬件的实现.结论可用于建立序列密码的新型高效密码体制. Deterministic irreducible polynomial and primitive polynomial over finite rings,i.e.polynomial rings with coefficients in finite fields,are obtained.With these polynomials,an efficient algorithm for obtaining the longest period of output stream is constructed.It is proved that the algorithm needs only 2（lb p） times additions modulo p for determining every value of the output stream.An implementation scheme of σ-LFSR based on trinomial primitive polynomial is given.The theoretical analysis and the computer simulation results show that this σ-LFSR generator has good randomness and can be implemented easily in both software and hardware.This approach can be used to construct new efficient cryptosystems for stream ciphers. σ-LFSR 三项式 不可约多项式 本原多项式 序列密码 快速算法 σ-LFSR trinomial irreducible polynomial primitive polynomial stream cipher quick algorithm TN918.1 广东省自然科学基金资助项目（7003624） 2008-05-01 2021-04-01 5