Pseudopowers and Primality Proving
Hugh Williams (University of Calgary)
MSI Computational Mathematics Seminar SeriesDATE: 2007-11-05
TIME: 11:00:00 - 12:00:00
LOCATION: John Dedman G35
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
The so-called pseudosquares can be employed in a very powerful machinery for the primality testing of large integers N. In fact, assuming reasonable heuristics (which have been confirmed for numbers to 2^80) they can be used to provide a deterministic primality test in time O((log N)^(3+o(1)), which some believe to be best possible. In the 1980s D.H. Lehmer posed a question tantamount to whether this could be extended to pseudo r-th powers. Very recently this was accomplished for r=3. In fact, the results obtained indicate that r=3 might lead to a more powerful algorithm than that for r=2. This naturally leads to the question of whether anything can be achieved for r > 3. The extension from r=2 to r=3 relied on properties of the arithmetic of the Eisenstein ring of integers Z[\zeta_3], including the Law of Cubic Reciprocity. In this talk I will present a generalization of our earlier result for any odd prime r. The generalization is obtained by studying the properties of Gaussian and Jacobi sums in a cyclotomic ring of integers, which are the tools from which the r-th power Eisenstein Reciprocity Law is derived, rather than from the law itself. While r=3 seems to lead to a more efficient algorithm than r=2, we show that extending to any r > 3 does not appear to lead to any further improvements.
BIO:
http://math.ucalgary.ca/~williams/
