On the Efficiency of a Polynomial Irreducibility Test
David R. Musser · Journal of the ACM · 1978
An important part of a previously given algorithm for factonng integral polynomials (D R Musser, Multivariate polynomial factonzation, J ACM 22, 2, April 1975) is a test for irreducibility based on mod p factonzations for several different prime mtegers p This paper analyzes the average efficiency of this test by determining the mean number of primes required to establish irreducibility of a random input polynomial.Tables are given showing this mean as a function of the degree of the mpnt polynomial, for degrees ranging up to 200 These tables were constructed in part usmg a Markov chain model of the behavior of the irreducibility test algonthm, and m part usmg an efficient simulation of the algorithm.The results show that the mean number of pnrnes grows very slowly with the degree and is less than 5 for all degrees up to 200 The Markov chain model and simulation model exploit an mterestmg correspondence between the factor structure of random polynomials over fmlte fields and the cycle structure of random permutations KEY WORDS AND PHRASES polynomial factoring, irreducibility test, average computing time, Markov chain, combinational enumeration CR CATEGORIES 5.25, 5 39, 5 7 n = 10 and that modulo p = 2 we obtain three irreducible factors of A(x) of degrees 2, 2, 6.Then Dp = {0, 2, 4, 6, 8, 10}.If the modulo q --3 irreducible factors have degrees 3, 3, 4 then Dq --{0, 3, 4, 6, 7, 10} and Dp N Dq --{0, 4, 6, 10}.If the modulo r --5 irreducible factors have degrees 2, 3, 5 then Dr = {0, 2, 3, 5, 7, 8, 10} and D, N Dq N Dr = {0, 10}, proving A(x) nrreducible.This "degree compatibility testing" method was included by the author in a computer algorithm for factoring integral polynomials described m [12,6,13].The modulo p factofizations are performed using the "distinct degree factorization" algorithm described in [11, p. 389] and [5].This algorithm produces only a partial factorization, but yields enough information to determine the degrees of all irreducible factors.One of Berlekamp's algorithms [ 1,2] for complete factorization could also be used.The maximum time required General permission to make fair use in teachmg or research of all or part of this matenal is granted to individual readers and to nonprofit hbranes acting for them provided that ACM's copyright notice is given and that reference Is made to the publication, to ItS date of issue, and to the fact that reprmtmg pnvfleges were granted by permission of the Association for Computmg Machmery.To otherwise repnnt a figure, table, other substantial excerpt, or the entire work requires specific permission as does republication, or systematic or multiple reproduction.