Number Theory Home | Number Theory Seminar | ArithmeTexas | Department Home
University of South Carolina
Title:Irreducibility and gcd algorithms for sparse polynomials
Abstract:Let f(x) be a polynomial with integer coefficients. Let n be the degree of f, let r be its number of terms and let H be its height (the largest absolute value of a coefficient). A sparse polynomial is one in which r is small compared to n (a more precise definition will not be necessary). Our main objective is to describe algorithms that run fast with r and H being fixed. Known algorithms, such as the L^3 algorithm for factoring and the Euclidean algorithm for gcd's, run in time that are polynomial in n. We describe algorithms that run in time that are polynomial in log n. The results are from recent joint work with Andrew Granville and Andrzej Schinzel. As time permits, we will discuss some practical aspects of the above theoretical results.