ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

Pseudopowers and Primality Proving

Speaker: Hugh Williams
Date, Time: Fri, 09 Nov 2007 14:00

Primes of 100 bits are very useful in verification of certain digital signatures. The so-called pseudosquares can be employed in very powerful machinery for the primality testing of such 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.

Back to the top of this page