Removing Randomness From Computational Number Theory

In recent years, many probabilistic algorithms (i.e., algorithms that can toss coins) that run in polynomial time have been discovered for problems with no known deterministic polynomial time algorithms. Perhaps the most famous example is the problem of testing large (say, 100 digit) numbers for primality. Even for problems which are known to have deterministic polynomial time algorithms, these algorithms are often not as fast as some probabilistic algorithms for the same problem. Even though probabilistic algorithms are useful in practice, we would like to know, for both theoretical and practical reasons, if randomization is really necessary to obtain the most efficient algorithms for certain problems. That is, we would like to know for which problems there is an inherent gap between the deterministic and probabilistic complexities of these problems. In this research, we consider two problems of a number theoretic nature: factoring polynomials over finite fields and constructing irred..