SMS scnews item created by (unknown) at Fri 9 Nov 2007 1706
Type: Seminar
Distribution: World
Expiry: 15 Nov 2007
Calendar1: 15 Nov 2007 1505-1600
CalLoc1: Eastern Ave 310

# 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.


If you are registered you may mark the scnews item as read.
School members may try to .