修改的Jacobi序列的二进制复杂度的一个下界

摘要

设p,q为两个满足gcd(p-1,q-1)=d的不同素数,D,i=0,1,…,d-1,为Whiteman广义割圆类,满足Z*pq=∪d-1i=0Di.本文给出了基于广义割圆陪集D*0=∪d/2-1i=0D2i和D*0=∪d/2i=0D2i+11的高斯周期,作为高斯周期的一个应用,本文计算出修改的Jacobi序列的二进制复杂度的一个下界.结果表明,对于周期为N=pq的修改的Jacobi序列,其二进制复杂度至少是pq-p-q-1,这表明修改的Jacobi序列的二进制复杂度超过序列周期的一半,从而可以抵抗带进位移位寄存器的有理算法.