Computational Algebra Seminar: Williams -- Pseudopowers and Primality Proving

Speaker: Hugh Williams (Calgary)
Title: Pseudopowers and Primality Proving
Time & Place: Thursday 15 November, 3-4pm, Eastern Ave Seminar Rm 310

Abstract:
The so-called pseudosquares can be employed in very powerful
machinery for the primality testing of integers N.  In fact, assuming
reasonable heuristics (which have been confirmed for numbers to 280)
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, which naturally leads to the question of whether anything
can be achieved for r > 3.  In this paper we show how these earlier
results can be extended to all prime values of r.