clarke@csri.toronto.edu (Jim Clarke) (02/17/89)
THEORY SEMINAR - Friday, March 3, 10 a.m. in Room SF 4102
(SF = Sandford Fleming Building, 10 King's College Road)
Victor Shoup
University of Wisconsin-Madison
"Removing Randomness from Computational Number Theory"
In recent years, randomization techniques have been used with much success
to design probabilistic polynomial time algorithms for problems for which
no deterministic polynomial time algorithms are known. 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 polyno-
mial time algorithms, these algorithms are often not as fast as some proba-
bilistic 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 prob-
lems. That is, we would like to know if there are problems for which 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 irreducible poly-
nomials of specified degree over finite fields. We present results that
narrow the gap between the known deterministic and probabilistic complexi-
ties of these problems. One of our results is a deterministic polynomial
time reduction from the latter problem to the former, giving rise to a
deterministic algorithm for constructing irreducible polynomials that runs
in polynomial time for fields of small characteristic. We also give a new
deterministic factoring algorithm that is faster than previously known al-
gorithms for this problem.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke