On the Difficulty of Prime Root Computation in Certain Finite Cyclic Groups

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.