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

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