Galois field Computations : Implementation of a Library and a study of the Discrete Logarithm Problem

Abstract

Computation over finite fields (also called Galois fields) is an active area of research in number theory and algebra, and finds many applications in cryptography, error control coding, and combinatorial design. In this thesis, we describe our computational experience in this area. Our work consists of two parts. In the first part, we build a comprehensive library for working over finite fields. In the second part, we make a detailed study of the discrete logarithm problem (DLP) over prime fields. We have developed a computational library of functions written in C for a wide range of problems that are of theoretical and practical interest in finite field computations. We call this library the Galois Field Library or GFL for short. GFL provides routines for field arithmetic and for manipulation of univariate polynomials and matrices over finite fields. It allows the user to work on finite fields of any characteristic and any cardinality. It is based on a set of routines for doing arbitrary-precision integer arithmetic and is portable, fast, and memory-efficient. We have carried out extensive testing and benchmarking of GFL. We demonstrate the programming techniques with GFL through some small and simple examples. We also provide an exhaustive list of functions currently provided by GFL. We compare the performance of GFL with those of three other libraries, namely, LiDIA, NTL, and ZEN. Computing discrete logarithms over a prime field Fp is a very difficult problem for which no polynomial-time algorithms are known. The best algorithms known till date are based on the index calculus method and take time subexponential in log p. We concentrate on three variants of the index calculus method, namely the basic method, the linear sieve method, and the cubic sieve method. The sieve methods test a set of deterministically generated integers for smoothness over a predetermined set of small primes. The analysis of running times of these methods is based on the heuristic assumption that these deterministically generated integers behave as random integers. We start our study of the DLP by showing that the actual distribution of these integers is not random in the sense that these integers do not follow uniform distribution. To prove our claim, we find out the arithmetic mean and the cumulative statistical distribution of these integers. We find that the average bit-length of these test integers is smaller than the expected bit-length of a sample of integers chosen following the uniform distribution. We then describe our implementation details and heuristic modification schemes for the three methods mentioned above. In the basic method, our heuristic scheme reduces the number of discrete exponentiations. We also make trial divisions faster by adopting two strategies: maintaining a list of remainders and sieving. For the linear sieve method, our heuristic generates a set of integers smaller on average than the integers checked for smoothness in the original method. This increases the chance of getting smooth integers, but decreases the ratio of the number of relations to the number of elements in the factor base. Finally, for the cubic sieve method, we increase the sieving interval by a heuristic strategy. This allows us to build a larger factor base without any significant increase in the running time. We also describe efficient implementation techniques for the sieve methods and establish the superiority of the cubic sieve method over the linear sieve method for a special class of primes. We conclude our study of the DLP by an analytic study of the congruence X? = Y?Z (mod p) subject to the condition X ? Y ? Z. This congruence plays an important role in the cubic sieve method. We estimate that the total number of solutions of the congruence for a prime p is O(p²). We also show that under certain heuristic assumptions, the expected number of solutions of the congruence with 1 ? X, Y, Z ? p? for 1/3 ? a < 1/2 is n(p²?). Small-scale experiments reveal that apart from constant factors, our estimate tallies with the experimental values quite closely.