Irreducibility testing of lacunary 0,1-polynomials

A reciprocal polynomial g(x)∈Z[x] is such that g(0)≠0 and if g(α)=0 then g(1/α)=0. The non-reciprocal part of a monic polynomial f(x)∈Z[x] is f(x) divided by the product of its irreducible monic reciprocal factors (to their multiplicity). This paper presents an algorithm for testing the irreducibility of the non-reciprocal part of a 0,1-polynomial (a polynomial having each coefficient either 0 or 1). The algorithm runs in time O(2rrlogrlogn) where r is the number of non-zero terms of the input polynomial and n is its degree. Thus, the algorithm efficiently handles lacunary (or sparse) 0,1-polynomials.