x_n_1在F_q上的素因子分解

x_n_1在F_q上的素因子分解 第 26 卷 第 3 期 上海第二工业大学学报Vol.26 No.3 2009 年 9 月JOURNAL OF SHANGHAI SECOND POLYTECHNIC UNIVERSITY Sept. 2009 文章编号: 1001-4543(2009)03-0200-03 n x 1在 F上的素因子分解 q 李旭红 (中原工学院理学院～郑州 450000 ) 摘 要:序列的线性复杂度是衡量流密码系统安全性的重要指标之一。近年来随着对向量流密码的研究，多重序列 的联合线性复杂度引起了广泛关注。通过给出 q 模 n 的乘法阶 s , o(n) 的简便算法，对素因子分解中各次因子的 q 个数进行了研究。在研究过程中应用集合论中有限集的计数法—容斥原理计算多项式的素因子分解中各次因式的个 数，得到了整齐且便于应用的结论。这是对多重序列的联合线性复杂度的期望、方差及计数问题进行研究的理论基 础。 关键词:流密码;有限域;乘法阶;素因子分解 中图分类号:TN918.4 文献标识码:A 0 引言 简单快捷地得到多项式在有限域上的素因子分解对于编码理论以及有限域上线性递归关系的研究有着 [1–3]重要的作用。特别是近年来随着对向量流密码的研究，多重序列的联合线性复杂度的相关问题引起了广 n 泛关注。多项式 x 1 在有限域 F 上的素因子分解中各次因式的个数是对多重序列的联合线性复杂度的期q 望、方差及计数问题进行研究的理论基础。一直以来多项式的素因子分解都是一个难点，文献[4–5]中给出 了多项式素因子分解的典型 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，但是计算复杂度比较高。 不过，在对序列问题的研究中，我们发现对于 多重序列的计数问题以及联合线性复杂度的期望与方差 等问题来说，其实不需要知道多项式素因子分解的具体结果，而只需要知道它的素因子分解中各次因子的 个数就可以了。这就是本文研究的出发点。本文除了采用了信息论中较专业方法外还用到了集合论中集合 的计数方法，以期拓宽并简化密码学的研究方法。 1 q 模 n 的乘法阶 [4–5] 一般来说 q 模 n 的乘法阶 s , o(n) 的计算比较困难，特别是 n 较大时 。在此，我们给出了 s 的简化 q 算法及其理论基础。 定理 1 设多项式 f( x), f( x) F[ x], f(0) , 0, f(0) , 0, ord( f( x)) , d, ord( f( x)) , d, 则若有 1 1 2 1 1 2 2 2 q f( x) | f( x) ，必有 d| d 1 2 1 2 。 ddd1 2 2 证明 ord( f ( x)) , d , f ( x) | x 1, ord( f ( x)) , d , f ( x) | x 1, 又由 f ( x) | f ( x) 得f ( x) | x 1 。1 1 1 2 2 2 1 2 1 ( [4 ] )d 2 f( x) | x 1 , d| d定理得证。而 1 1 2 。 推论 1 设 n, n为正整数， q 为素数幂， gcd(n, q) , 1, 令 s, o(n), s, o(n), 若 n| n，则必有 s| s。 1 2 2 1 q 1 2 q 2 1 2 1 2 定理 2 设 n 为大于 1 的正整数， q 为素数幂，且 gcd(n, q) , 1, s , o(n), 则 q k 2 sk 11 1) 若 n , r ， r 为奇素数， k 为正整数， s , o (r), r | q 1, 则 s , r s 。1 q 1 2) 若 n , r, r, gcd(r, r) , 1 ，令 s, o(r), s, o(r) ，则 s , lcm(s, 1 2 1 2 1 q 1 2 q 2 1 s) 。 2 类似地，若 n , rr…r, gcd(r, r) , 1(i , j) ，令 s, o(r), 则 s , lcm(s, s,…, s) 。 1 2 k 12 k i j i q i 收稿日期:2009-04-22; 修回日期:2009-07-05 作者简介:李旭红(1980—)，女，河南郑州人，讲师，硕士学位，主要研究领域为 序列密码。 证明 (1) 对 k 进行归纳证明。 当 k , 1 时，结论显然成立。 当 k , 2 时，由 s, o(r) ，知 r | q 1 ，又因为 r 为奇素数，且 r | q 2 ss 1 q 11 1 ，所以存在与 r 互素的常数 c ， ss1 1 使得 q 1 , cr, 即 q, cr ， 1, 于是 rsr 0 0 1 1 r r 2 r r1 q, (1 ， cr ), c(cr )， c(cr )， … ， c(cr ), 1 ， cr ， … ， cr r r r 2 rs 3 rs2 1 显然有 r | q 1 ，又由 c 与 r 互素，知 r | q 1 。于是，由 q 模 n 的乘法阶的定义得 结论成立。 rs , o (r ) 1 q k 1 k k k r r sr r k ， k ，1 r s ( ) 1 1 1 假设对于 k ， 1 q , (1 ， cr) , 1 ， cr ， … ， (cr) 则有 r | q 1 ，而由 c 与 r 互素，所以 k ，1 k r s, o(r ) 。综上知命题成立。 1 q s1 , s , o (r ) , r | q 1 1 q 1 1 , ss s 2 (2) s , o (r ) , r | q 1 , r | q 1, r | q 1 , s | s, s | s , lcm(s , s ) | s 事实上，lcm(s , s ) , s 。否, 2 q 2 2 1 2 1 2 1 2 1 2 , s s , o(rr) , rr| q 1q 12 12 , , d d d d ss 12则，设 lcm(s, s) , d , 则 d? s, 且有s| d , s| d , q 1 | q 1, q 1 | q 1 , r| q 1, r| q 1 ，又由 1 2 1 2 1 2 d gcd(r, r) , 1 ，于是得 rr| q 1 ，而又由 s , o(rr) ，所以有 s? d。 1 2 12 q 12 综上即得 d , s , lcm(s, s) 。 1 2 n 2 x 1在 F上的素因子分解中各次因子的个数 q 在这一部分中总假定 gcd(n, q) , 1 。 n 定理 3 若 x 1 在 F 上的素因子分解中含有 d 次因子，则必有 d | s ，其中 s , o (n) 。q q n 证明 设 f( x) 为 x 1 在 F上的素因子分解中的任一 d 次因式，则由 f( x) 的不可约性知它在 F上的 d q d q 分裂域为 F , 即 F 是包含 f( x) 的全部根的最小有限域。 d d d q q s s s qq q s n 1 n n ( [1] ) ，所以 x 1 的 又由 s , o (n), n | q 1, 知 x 1| x 1, 于是 x 1| x x, 而 x x 的分裂域为 Fs q q 全部根落入 F 中，则 F 为 F 的子域，即有 F F , 于是得 d | s 。 s d s ds q q q q q n [4] 引理 1x 1 在 F 上的素因子分解中 1 次因子的个数为 gcd(n, q 1) 。q 1 t n dd ，其中 t C 定理 4 x 1 在 F 上的素因子分解中，若 d | s, 则 d 次因子的个数为 C , gcd(n, q 1) q d t d t 为阶数等于 t 的分圆陪集的个数。 d , 1, C [4] 证明 首先已知定理中所述的 d 次因子的个数与阶数为 d 的分圆陪集的个数相等。设 1， t(1i k ) 为 d 的小于 d 的全部因子，即1 , t, … , t, d , td ( 1?i ? k )。 ?? i 1 k i i i 令 A , x : x , xq(mod n), x : n | x(q 1)(i , 1, t ,…, t , d ) 。,, ,, 1 k i d 事实上A , gcd(n, q 1) ，这是因为i n d d x , xq(mod n) , n x(q 1) , x d gcd(n, q 1) n n d 而x , x , l , 其中 l , 0,1,…, gcd(n, q 1) 1 。d d gcd(n, q 1) gcd(n, q 1) 上海第二工业大学学报2009 年 第 26 卷 202 t dtt t1 k1 B, , ，而通过分析 A 与 令 B, {x : x A , x A , j , t} ，于是 BA B B A … B t j d d t 1t , d ,t |d ? 1 d d t ddt ttt , d C , t C t C 。 ，于是有 BA 即C B的结构可知，有 B, gcd(n, q 1) , t C d d 1?t , d ,t|d t d d , 0 。 推论 若 d | s ，则 C 27 例 求 x 1 在 F 上的素因子分解中各次因子的个数。4 3 2 1 解 已知 n , 27 , 3, q , 4 ，于是 s , o (3) , 1, 3| 4 11 4 2 27 由定理 2(1)得 s , o (27) , 3,1 , 9 ，则 x 1 在 F 上的素因子分解中只可能有 1 次，3 次和 9 次因式。利4 4 用引理 1 和定理 4 计算可得 1 次，3 次，9 次因式的个数分别为 3，2，2。 3 结论 本文采用简单的方法得到了整齐好用的结果，而这些结果是对任意周期多重序列的联合线性复杂度与 序列的个数之间的关系，以及对联合线性复杂度的期望与方差进行研究的理论基础。 参考文献: [1] FU H, NIEDERREITERIS. The expectationand varianceof the joint linear complexityof random periodic multi-sequence[J]. Journalof Complexity, 2005,21:804– 822 [2] RUEPPEL R A. Analysis and Design of Stream Ciphers[M]. Berlin:, 1986.Springer [3] WANGL P, NIEDERREITER H. Enumeration results on the joint linear complexity of multi-sequences[J]. Finite Fields Appl.,637. 2006,12:613– [4] LIDL R, NIEDERREITER H. Finite Fields[M]. MA:Addison-Wesley Publishing1983. Compan y. [5] ROMAN S. Coding and Information Theory[M]. Berlin: Springe1998.r-Verlag, [6] KUMANDURI R, ROMERO C. Number Theory with Computer Applications[M]. New Jersey:, Prentice1998. -Hall n The Canonical Factorization of the Polynomial x 1 on F q LI Xu-hong ( College of Science，Zhongyuan University of Technology, Zhengzhou 450000, P. R.China) Abstract: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 n simples s = o(n) is given. By this result , the author studies the canonical factorization of x 1 on F, and obtains the number of all qqn monic polynomials with same degrees for the canonical factorization of x 1 on F using Inclusion-Exclusion Principle. These results q are the foundation for counting of the joint linear complexity of multi-sequences withal expectation and variance. Keywords:stream ciphers; finite fields; order of q mod n ; canonical factorization.