Analysis of Rabin's Polynomial Irreducibility Test

摘要

We give a precise average-case analysis of Rabin's algorithm for testing the irreducibility of polynomials over finite fileds. The main technical contriution of the paper is the study of the probability that a random polynomial of degree n contains an irreducible factor of degree dividign several maximal divisors of the degree n. We proivde upper and lower bounds for this porbability. Our method generalizes to other algorithms that deal with similar divisor conditions. In particular, we analyze the average-case behavior of Rabin's variants presented by von zur Gathen & Shoup and by Gao & Panario.