phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (03/03/84)
UofT Department of Computer Science Seminar Schedule for
the week of March 5th, 1984
Tuesday, March 6th, 3:00 P.M., GB244: Professor Eric Bach,
Computer Science Division, University of California, Berkeley:
"What to do until the witness comes: Explicit bounds for
primality testing and related problems".
ABSTRACT: Many analyses of number-theoretical algorithms use the
following result:
Assuming the Extended Riemann Hypothesis, if G is a proper
multiplicative subgroup of the integers modulo n, then the least
positive integer x outside G is 0(Log n)^2.
However, this cannot be applied to problems such as prime testing
unless the 0-estimate is replaced by something concrete. This talk
is about the new "effective" versions of the above theorem. Not
only is the above-mentioned x small asymptotically (<( log n)^2 ),
but this estimate converges quickly, so that one has, for instance,
x < = 2 ( log n)^2 for n > = 1000.
The first part of this talk will concern subgroups and their relevance
to prime testing. In the second part, I will show, in an intuitive
way, why the ERH has the algorithmic implications that it does.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{decvax,linus,ihnp4,uw-beaver,allegra,utzoo}!utcsrgv!phyllis
CSNET: phyllis@toronto
(416) 978 6985