基于多项式商之和的伪随机序列的线性复杂度

基于多项式商之和的伪随机序列的线性复杂度 Linear Complexity of Pseudorandom Sequences Based on Summation of Polynomial Quotients 吴晨煌 WU Chenhuang 1 first-author 陈智雄 CHEN Zhixiong 1 莆田学院数学学院 莆田学院数学学院 School of Mathematical Sciences,Putian University School of Mathematical Sciences,Putian University 探讨t（t≥1）个不同的多项式商之和定义的序列H（u）≡∑it=1ai uwi-uwip p（modp）的线性复杂度.一方面,给出了作为p元序列的（H（u））u≥0的线性复杂度准确值;另一方面,结合有限域Zp上的d阶乘法特征χ,定义d元序列（su）u≥0:0≤su<d,exp（2πisu/d）=χ（H（u））,χ（0）=1证明了当d为素数且dmodp2为本原元时,序列（su）u≥0具有"高"的线性复杂度.同时,应用指数和估计,给出了（su）u≥0（此时d可以为合数）的线性复杂度轮廓的一个下界. We discuss the linear complexity of the sequences H（u）≡∑it=1ai uwi-uwip p（modp）defined by the summation of t（t≥1）different polynomial quotients.On one hand,we get the exact values of linear complexity of the pary sequences（H（u））u≥0.On the other hand,combining with the multiplicative characterχof order dof the finite field Zp,we define the d-ary sequences（su）u≥0:0≤su <d,exp（2πisu）d=χ（H（u））,χ（0）=1If dis prime and dis a primitive element modulo p2,we prove that（su）u≥0has"high"linear complexity.Moreover,using certain exponential sum estimate,we give a lower bound on the linear complexity profile of（su）u≥0for any prime or composite d. 序列密码 多项式商 费马商 伪随机序列 线性复杂度 stream cipher polynomial quotients Fermat quotients pseudorandom sequences linear complexity 10.14188/j.1671-8836.2014.02.012 TN918.1 国家自然科学基金资助项目（61373140,61170246）;福建省教育厅资助项目（JK2013044,JA12291,JB12179）;莆田学院教改项目（JG2012020） 2014-02-01 2021-04-01 2 60