Analysis of Ben-Or's polynomial irreducibility test

✍ Scribed by Daniel Panario; Bruce Richmond

• Book ID: 101270713
• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 235 KB
• Volume: 13
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199810/12)13:3/4<439::aid-rsa13>3.0.co;2-u

✦ Synopsis

We give a precise average-case analysis of Ben-Or's algorithm for testing the irreducibility of polynomials over finite fields. First, we study the probability that a random polynomial of degree n over ‫ކ‬ contains no irreducible factors of degree less than m, q 1 F m F n. The results are given in terms of the Buchstab function. Then, we compute the expectation and variance of the smallest degree among the irreducible factors of a random polynomial. The analysis of Ben-Or's algorithm readily follows from this expectation. We also compute the probability of a polynomial being irreducible when it has no irreducible factors of degree less than m, 1F m F n. This probability is useful in the analysis of some algorithms for factoring polynomials over finite fields.