10th May 2005,  Amy Johnston<br>

<b>
On the difficulty of prime root computation in certain finite cyclic
groups </b><br><br>

The best known algorithm for computing square roots in Z_P where P is
prime requires that P=3 mod 4. This algorithm, extended to any finite
cyclic group, requires the order of the group not be divisible by 4. If
4 divides the order then more complicated algorithms are required.
Hidden within these algorithms are discrete logarithm computations on
elements of order 2.<br><br>

The square root algorithm can be extended to compute q-th roots for any
prime q. The algorithm is trivial if q divides the order of the group
at most once. However, if q^2 divides the order of the group discrete
logarithms on elements of order q are required. This algorithm is the
only general purpose root computation technique known and suggests that
the discrete logarithm problem and q-th root problems for these groups
may be equivalent. <br><br>

This talk will address the relationship between these two problems.