x^n-1在F_q上的素因子分解

The Canonical Factorization of the Polynomial x^n-1 on F_q

序列的线性复杂度是衡量流密码系统安全性的重要指标之一。近年来随着对向量流密码的研究,多重序列的联合线性复杂度引起了广泛关注。通过给出q模n的乘法阶s=oq(n)的简便算法,对素因子分解中各次因子的个数进行了研究。在研究过程中应用集合论中有限集的计数法—容斥原理计算多项式的素因子分解中各次因式的个数,得到了整齐且便于应用的结论。这是对多重序列的联合线性复杂度的期望、方差及计数问题进行研究的理论基础。

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectored stream cipher systems, the joint linear complexity of multi-sequences has been investigated. In this paper, the algorithm of simples s = Oq（n） is given. By this result, the author studies the canonical factorization of x^n - 1 on Fq, and obtains the number of all monic polynomials with same degrees for the canonical factorization of x^n - 1 on Fq using Inclusion-Exclusion Principle. These results are the foundation for counting of the joint linear complexity of multi-sequences withal expectation and variance.