ANALYSIS OF BEN-OR POLYNOMIAL IRREDUCIBILITY TEST

We give a precise average-case analysis of Ben-Or's algorithm for test ing the irreducibility of polynomials over finite fields. First, we st udy the probability that a random polynomial of degree n over F-q cont ains no irreducible factors of degree less than m, 1 less than or equa l to m less than or equal to n. The results are given in terms of the Buchstab function. Then, we compute the expectation and variance of th e smallest degree among the irreducible factors of a random polynomial . The analysis of Ben-Or's algorithm readily follows from this expecta tion. We also compute the probability of a polynomial being irreducibl e when it has no irreducible factors of degree less than m, ism I n. T his probability is useful in the analysis of same algorithms for facto ring polynomials over finite fields. (C) 1998 John Wiley & Sons, Inc.