The International Computer Science Institute
                     is pleased to present a talk:

                   Monday, June 15, 1992  11:00 a.m.

                               ERIC BACH
                      Computer Sciences Department
                        University of Wisconsin
                              Madison, WI

           ``Statistical Evidence for Small Generating Sets''

           For an integer n, let G(n) denote the smallest  x  such
      that  the  primes  <=  x  generate  the multiplicative group
      modulo n.  We offer heuristic arguments and  numerical  data
      supporting the idea that G(n) <= (log 2)^{-1} log n loglog n
      asymptotically.  We believe that the coefficient 1/log 2  is
      optimal.   Finally,  we show the average  value of  G(n) for
      n <= N is at least (1 + o(1)) loglog N logloglog N, and give
      a heuristic argument  that this is also an upper bound. This
      work gives additional evidence, independent of the ERH, that
      primality  testing  can  be done in deterministic polynomial
      time; if our bound on G(n) is correct,  there  is  a  deter-
      ministic  primality  test  using  O(log n)^2 multiplications
      modulo n.

                  (Joint work with Lorenz Huelsbergen)

        This talk will be held in the Main Lecture Hall at ICSI.
          1947 Center Street, Sixth Floor, Berkeley, CA 94704
       (On Center between Milvia and Martin Luther King Jr. Way)