周期二元序列的线性复杂度及其稳定性分析

摘要

密码学意义上强的序列不仅应该具有高的线性复杂度而且其线性复杂度必须稳定,k-错线性复杂度用来反应线性复杂度的稳定性.本文基于xpm2n-1在GF(2)上具有明确的分解式,研究了pm2n-周期二元序列的线性复杂度和k-错线性复杂度之间的关系,然后说明了同时使得线性复杂度和k-错线性复杂度都达到最大值的pm2n-周期二元序列是存在的.这里p是一个奇素数,2是模p2的本原根.%Cryptographically strong sequences should not only have a high linear complexity, but also altering a few terms should not cause a significant decline of the linear complexity. This requirement leads to the concept of the k-error linear complexity of periodic sequences.Based on the explicit factorization of xpm2n - 1 over GF(2), this correspondence focuses on the relationship between the linear complexity and the k-error linear complexity of the pm2n-periodic binary sequences, where p is an odd prime number, 2 is a primitive root modulo p2. Then we establish the existence of pm2n-periodic sequences which simultaneously achieve the maximum value of the linear complexity and the k-error linear complexity.