On the Factorization of Lacunary Polynomials

University South Carolina Research Foundation, Columbia SC

Investigators

Abstract

Filaseta 0207302 The investigator and his collaborator Douglas Meade develop and implement efficient algorithms for irreducibility testing and factorization of polynomials with small Euclidean norm. In addition, they classify through similar algorithms all cases where reducibility occurs with Euclidean norm bounded by some prescribed amount. Issues relating to the complexity and parallel implementation of such algorithms are considered. Both factoring and, more generally, computational mathematics have played a vital role in cryptography. The importance of algorithms in such applications continues to increase as technology advances. This project deals with factoring polynomials of high degree from both a theoretical and computational point of view. The work has application in cryptography and in complexity theory, which deals with the question of how much work is needed to solve certain kinds of problems.