Path: utzoo!attcan!utgpu!watmath!thunder!water!wlrush
From: wlrush@water.waterloo.edu (Wenchantress Wench Wendall)
Newsgroups: ont.events,uw.talks,uw.cs.grad
Subject: THEORY SEMINAR
Keywords: Professor Jeffrey Shallit, Dept. of Computer Science,
Message-ID: <2566@water.waterloo.edu>
Date: 3 Aug 89 11:40:23 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 51

Dartmouth University, will speak on 
``Randomized Algorithms and Randomized Reductions in Number Theory.''


DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

THEORY SEMINAR

                    -Friday, August 11, 1989

Professor  Jeffrey  Shallit, Dept. of Computer Science,
Dartmouth   University,   will  speak  on  ``Randomized
Algorithms   and   Randomized   Reductions   in  Number
Theory.''

TIME:                 2:00 p.m.

ROOM:                 DC 1302

ABSTRACT

In  this  talk,  I'll survey the role of the randomized
algorithm  and  the  randomized  reduction  in  proving
results in number-theoretic complexity.

Rabin  and  Solovay & Strassen first showed the utility
of  randomized algorithms in proving numbers composite.
Many other problems in number theory, for which no fast
deterministic  algorithm  is  known,  turn  out  to  be
solvable   in  random  polynomial  time.  I'll  discuss
several new examples, including Pollard's algorithm for
quadratic  congruences,  and representations as sums of
squares (joint work of Michael Rabin and myself).

Gary  Miller  showed the value of randomized reductions
in  proving  that  certain  functions  from  elementary
number  theory are "hard".  (By a "hard" problem I mean
one  that  is  at least as hard as factoring. This is a
number-theoretic  analogue  of  NP-hardness.) I'll show
that  several classical problems, such as the Euler phi
function,  and  the sum of divisors function, fall into
this  class.  An amusing consequence is that there is a
BPP  algorithm  to  tell  if  a  number  is  perfect or
multiperfect.   This is joint work with Gary Miller and
Eric Bach.

Finally,   I'll   discuss  the  relationship  of  these
reductions  with  the  recent  elliptic curve factoring
algorithm of Hendrik Lenstra.