Factoring polynomials using fewer random bits (Q912919)

Let F be a field of q elements, \(q=p^ n\), p a prime. Two new probabilistic algorithms for factoring polynomials over F that make efficient use of random bits are presented. The first algorithm, based on an algorithm of Berlekamp, factors a polynomial of degree d using \(d \log_ 2 p\) random bits and produces in polynomial time a complete factorization with a probability of failure of no more \(1/p^{(1- \epsilon)d/2},\) \(0<\epsilon <1\). The second algorithm is based on a method of Cantor and Zassenhaus. It also uses \(d \log_ 2 p\) random bits and fails to produce a complete factorization with probability of failure no more than \(1/q^{(1-\epsilon)d/4}\).