基于Miller-Rabin素性检测的多项式分解算法  

Algorithms to Factorize Polynomials Based on Miller-Rabin Primality Test

作　　者：孙荣辛[1] 田园[1] 

机构地区：[1]大连理工大学国家示范性软件学院,辽宁大连116620

出　　处：《计算机科学与探索》2014年第12期1474-1484,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金~~

摘　　要：通过将Miller-Rabin素性检测的思想拓展到多项式域,随机二分搜索可应用到多项式分解中。并以此为基础,分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为1/4;第二种算法在代数数域上每次分解模素理想P的多项式的失败概率最多为1/2,当代数数域为偶数次扩展或者P|(p)满足p为素数且4|p-1的形式时,失败概率至多为3/8。和原有算法相比较降低了失败概率。这两种算法都在分解之前进行了素性判断,这一特性可用于生成不可归约多项式。在讨论代数数域情况时,给出了完整的多项式运算的时间复杂证明,弥补了代数数域内多项式计算理论模型上的空白。By extending Miller-Rabin primality test to the fields of polynomials, random binary search comes into use for factorizing polynomials. On the basis of this method, two separate probabilistic algorithms are improved in each case of finite fields and algebraic number fields. The first one factorizes polynomials modulo prime over finite fields with the failure probability 1/4 at most. The second one factorizes polynomials modulo prime ideal P over number fields with the failure probability 1/2 at most. When the number field is of evendegree or P｜（ p） where p is a prime and 4/p , the failure probability is 3/8 at most. Failure probability of two advanced algorithms is reduced in the comparison with original algorithms. The algorithms do irreducibility test before factorizing polyno-mials, a useful feature which can be utilized to efficiently generate irreducible polynomials. In the case of algebraic number fields, a complete demonstration of algorithm complexity is shown, which fills the gap of the theoretical model of computing polynomials over algebraic number fields.

关 键 词：概率性算法 多项式分解 Miller-Rabin素性检测 有限域 代数数域 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]