Abstract: 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-1, 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 polynomials, 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.

Key words: probabilistic algorithm, polynomials factorization, Miller-Rabin primality test, finite field, number field

摘要： 通过将Miller-Rabin素性检测的思想拓展到多项式域，随机二分搜索可应用到多项式分解中。并以此为基础，分别针对有限域和代数数域改进了两种概率性算法。第一种算法在有限域上每次分解模素数的多项式的失败概率最多为1/4；第二种算法在代数数域上每次分解模素理想[P]的多项式的失败概率最多为1/2，当代数数域为偶数次扩展或者P|(p)满足p为素数且4|p-1的形式时，失败概率至多为3/8。和原有算法相比较降低了失败概率。这两种算法都在分解之前进行了素性判断，这一特性可用于生成不可归约多项式。在讨论代数数域情况时，给出了完整的多项式运算的时间复杂证明，弥补了代数数域内多项式计算理论模型上的空白。

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