On the Difficulty of Prime Root Computation in Certain
Finite Cyclic Groups
by Anna M. Johnston
Abstract:
Public key cryptography is a relatively new branch of
cryptography, with the first cryptosystems published in the 1970s.
Despite its youth, much of our modern information infrastructure
relies on public key cryptography for efficient security.
Public key cryptosystems are built on computationally infeasible
mathematical problems. The two most common problems are factoring
large composite integers and computing discrete logarithms. It is
well known that the problems of factoring a composite integer N,
and computing a square root modulo N, are equivalent, with several
cryptosystems designed from this hard problem. A lesser known
equivalency exists between the discrete logarithm and qth root
problems. Public key cryptosystems have been based on the
difficulty of the qth root problem, including a key exchange
provably secure against the man-in-the-middle attack.
If q is prime integer, and G is a finite cyclic group such that
q^2 divides the order of G, then computing a qth root in G appears
to be equivalent to computing a discrete logarithm of an element
of order q. No known qth root algorithms for groups G exist which
do not require discrete logarithm computation. Earlier work
proved that if a 'well-behaved' qth root algorithm existed, then
discrete logarithms of elements of order q in these groups could
be computed with 2log_2(q) calls to the qth root algorithm.
All known qth root algorithms in G can be reduced to a single
algorithm, described in the thesis. It requires a single
logarithm computation whenever q^2 divides the order of the group.
However, one specialized algorithm is known which does not require
a discrete logarithm computation: Cipolla's algorithm. This
algorithm only works if G is the multiplicative group of a finite
field. If Cipolla's algorithm were more efficient than discrete
logarithm computation this would show that with current technology
the qth root problem is easier than the discrete logarithm problem
in finite fields. If it was 'well-behaved' then it would give an
efficient discrete logarithm algorithm when combined with earlier
work. However in its current form Cipolla's algorithm is
computationally more expensive than finding a discrete logarithm
using exhaustion and does not have the 'well-behaved' property
needed to find discrete logarithms.
Cipolla's algorithm was originally designed to compute square
roots when large powers of 2 divided the order of the group and
has not been analyzed for larger primes. If the algorithm could
be modified such that its computational requirements were less
than a discrete logarithm or it were given the 'well-behaved'
property needed to compute a discrete logarithm, then the balance
between the two problems would be upset, a least in the
multiplicative groups of finite fields.
We will show that Cipolla's algorithm does not upset the balance
of the qth root and discrete logarithm problems. If the
computational requirements could be minimized with respect to q,
then this implies pre-knowledge of the qth root. While Cipolla's
algorithm itself gives no further insight into the qth root or
discrete logarithm problems, the research indicates new directions
for future work on these problems.