Indices — The Discrete Logarithm

note

This is Lab 12 from Clint by Hugh Montgomery, edited by Codex and Elad Zelingher. All rights reserved to Hugh Montgomery.

Suppose that $g$ is a primitive root of the prime number $p$. If $(a,p)=1$ then there is a number $\nu$ such that $g^\nu\equiv a\pmod p$; moreover, the value of $\nu$ is uniquely determined modulo $p-1$. This $\nu$ is called the index of $a$ with respect to the primitive root $g$. In symbols we write $\nu=\operatorname{ind}_g a$ when the value of $p$ has already been specified. By way of analogy, any positive real number $x$ can be written uniquely in the form $e^y$ where $y=\ln x$. Thus $\operatorname{ind}_g a$ is a discrete analogue of $\ln x$.

For a given prime $p<10^4$, the program IndTab displays a table of the indices of the reduced residue classes modulo $p$. If there are more values than can be displayed on a single page, then you may use the pagination controls to move around in the table. Initially, $g$ is the least positive primitive root of $p$, but you are free to switch to a different primitive root. The program will prevent you from choosing a base that is not a primitive root. The program also provides a table of the powers of $g$, which is obtained by selecting “Powers.” To return to the table of indices from the table of exponentials, select “Indices.” These tables may be used in the manner of tables of logarithms and exponentials, to find the solutions of multiplicative congruences.

For example, to find the solutions of the congruence $x^3\equiv12\pmod{97}$, we take $g=5$, and write $x\equiv5^\mu\pmod{97}$. From IndTab we discover that $\operatorname{ind}_5 12=42$. That is, $12\equiv5^{42}\pmod{97}$. Hence the initial congruence may be rewritten as $5^{3\mu}\equiv5^{42}\pmod{97}$. This is equivalent to asserting that $3\mu\equiv42\pmod{96}$. From LinCon we discover that this is equivalent to $\mu\equiv14\pmod{32}$. That is, $\mu\equiv14$, $46$, or $78$ modulo $96$. Returning to the IndTab program, we enter $p=97$ again, and then select “Powers” to switch to the table of exponentials, i.e. powers of the primitive root 5. From this table we deduce that $5^{14}\equiv48\pmod{97}$, that $5^{46}\equiv31\pmod{97}$, and that $5^{78}\equiv18\pmod{97}$. Hence the desired solutions are $x\equiv48$, $31$, and $18$ modulo $97$. As a check, one may use the program Power to verify that $48^3\equiv31^3\equiv18^3\equiv12\pmod{97}$.

If the actual roots of the congruence $x^3\equiv12\pmod{97}$ are not needed, but only the number of roots, then one may proceed more simply, using Euler's criterion (Corollary 2.38 on p. 101 of NZM) and the program Power: Since $12^{96/(3,96)}=12^{32}\equiv1\pmod{97}$, it follows that the given congruence has exactly $(3,96)=3$ solutions.

Problem 1

Use the program IndTab to find the solutions of the congruence $x^4\equiv693\pmod{1093}$.

Problem 2

Use IndTab to find all solutions of the congruence $x^5\equiv693\pmod{1093}$.

Problem 3

Use IndTab in the manner above to show that the congruence $x^7\equiv693\pmod{1093}$ has no solution. At what point in the argument does it become apparent that there is no solution? Use Theorem 2.37 of NZM to provide a simpler proof that this congruence has no solution.

Problem 4

Use IndTab to find all solutions of the congruence $x^{10}\equiv475\pmod{9973}$.

Problem 5

Use IndTab to find all $x$ such that $2^x\equiv133\pmod{9973}$.

Problem 6

With $p=9973$, use IndTab to determine the value of $\operatorname{ind}_{103}877$.

The program IndTab is restricted to $p<10^4$ because the entire table is computed at the outset, and held in active memory (RAM). We have efficient means to compute powers, and efficient means to locate the least positive primitive root $g$, and thus we can easily compute values of $g^\mu\pmod p$ as $\mu$ runs over any given interval. What seems to be hard is to calculate values of $\operatorname{ind}_g a$ for a general $a$. Indeed, methods of encryption have been proposed whose security depends on the supposition that evaluating indices is computationally difficult. This computational snag is often referred to in the literature as the problem of the discrete logarithm.

The program IndTab first constructs a list of the values $g^\nu$ (i.e., exponentials), and then uses it to form a table of the indices. Thus $\operatorname{ind}a$ is found for each $a$ (mod $p$), but the amount of work is proportional to $p$. A first step toward improving on this has been suggested by Shanks: Suppose that you wish to calculate $\operatorname{ind}_g x\pmod p$. Let $s$ be a base to be described later; we want to find $i$ and $j$ so that $g^{is+j}\equiv x\pmod p$. To this end, use the extended Euclidean algorithm (i.e., the program LinCon) to find $\overline g$ so that $g\overline g\equiv1\pmod p$. Construct a table of the values $x\overline g^j$ (mod $p$) for $0\leq j<s$. Then, for $i=0,1,\ldots$, compute $g^{is}$ (mod $p$), and look to see if the number computed is found in the table. When it is found, we have the desired values of $i$ and $j$, and $\operatorname{ind}_g x=is+j$.

When searching for a particular value of $g^{is}$ in the table, it would be very slow to inspect all $s$ values. Instead, we sort the table of values $x\overline g^j\pmod p$ by size, into increasing order. (A useful algorithm for sorting, called HeapSort, is discussed later in this laboratory.) Then one can search for a specified value in the table by binary subdivisions. To motivate the choice of $s$, we consider the amount of work required. The time required to construct the table is $O(s)$, but the time required to sort it is a little greater, $O(s\log s)$. Searching by binary subdivision takes $O(\log s)$ steps, and we expect that it will be necessary to conduct $\approx p/s$ such searches. Thus the total amount of work is proportional to

$$\left(\frac ps+s\right)\log s.$$

This is minimized by taking $s\approx\sqrt p$, and then the time involved is $O(p^{1/2}\log p)$, a little slower than proving that $p$ is prime by trial division. Thus we see that Shanks' algorithm is not very fast for big $p$, although it represents a big improvement over $O(p)$.

In practice, the parameter $s$ above is constrained also by the amount of available memory. For example, the program Ind calculates $\operatorname{ind}_g x\pmod p$ by Shanks' method for $p<10^9$; for $p<10^8$ it takes $s$ to be the integer nearest $\sqrt p$, but for larger $p$ it takes $s=10000$ so that the data fits into one 64K segment of memory. (Each entry of the table occupies 4 bytes, and a companion table 2 bytes each, so the tables require 60K of memory.) To witness Shanks' algorithm in action, apply IndDem with $g=2$, $a=45$, $p=101$. Also try $g=2$, $a=3$, $p=1093$.

For more information concerning algorithms used to calculate indices see the following papers.

• D. Coppersmith, A. M. Odlyzko, R. Schroeppel, “Discrete logarithms in GF($p$),” Algorithmica 1 (1986), 1–15.
• D. M. Gordon, “Discrete logarithms in GF($p$) using the number field sieve,” SIAM J. Discrete Math. 6 (1993), 124–138.
• B. A. LaMacchia, A. M. Odlyzko, “Computation of discrete logarithms in prime fields,” Des. Codes Cryptogr. 1 (1991), 47–62.
• K. S. McCurley, “The discrete logarithm problem,” Cryptology and computational number theory (Boulder, 1989), Amer. Math. Soc., Providence, 1990, pp. 49–74.
• A. M. Odlyzko, “Discrete logarithms in finite fields and their cryptographic significance,” Advances in Cryptography (Proc. 1984 EUROCRYPT Workshop), Springer-Verlag, New York, 1985, pp. 224–314.

Problem 7

Use PrimRoot to find a primitive root $g$ modulo $p=123456791$. Use the program Ind to determine $\operatorname{ind}_g57085185\pmod p$. For example, use Ind with $g=17$, $a=57085185$, and $p=123456791$. Use this information to find all roots of the congruence $x^5\equiv57085185\pmod{123456791}$.

Problem 8

The program Ind searches for a specified value $x$ among the powers of $g\pmod p$. It is essential that $(g,p)=1$, but it is not necessary that $p$ be prime or that $g$ be a primitive root. Is 3 a power of 2 modulo 123456791? That is, does the congruence $2^\nu\equiv3\pmod{123456791}$ have a solution? Use Ind with $g=2$, $a=3$, and $p=123456791$. Here the modulus is prime, but the base is not a primitive root. Note that the program returns only the least non-negative solution. The period of the solutions is $p-1$ if $g$ is a primitive root (mod $p$), but it is smaller in other cases. Find all $\nu$ (mod 123456790) such that $2^\nu\equiv3\pmod{123456791}$. (Hint: Use the program Order to determine the order of 2 (mod 123456791).) Confirm that Ind still works when $p$ is composite by using $g=2$, $a=23$, and $p=91$. Use $g=2$, $a=17$, and $p=123456791$. What happens?

Problem 9

Assume that $p=1234567897531$ is prime. Use the programs GCD and Power to determine the number of roots of the congruence $x^{77}\equiv13\pmod{1234567897531}$. (Theorem 2.37 of NZM is relevant here.) Note that you do not have any tool available to find these roots, since $p$ is so large. Such tools do exist; for example one might elaborate on the technique developed in the next laboratory. Alternatively, the polynomial $x^{77}-13$ can be factored quickly (mod $p$), for example by the method of D. G. Cantor and H. Zassenhaus, “A new algorithm for factoring polynomials over finite fields,” Math. Comp. 36 (1981), 587–592.

We now consider the problem of sorting numbers by size. While not a number-theoretic problem, we find it useful (as above) to be able to sort numbers with reasonable efficiency. Suppose that $a_1,a_2,\ldots,a_n$ are $n$ distinct numbers that we want to sort into increasing order. First, in Bubble Sort, one passes repeatedly through the list, transposing pairs that are found to be out of order, until a pass discloses no transpositions. This takes time $O(n^2)$, which is terrible! Never use Bubble Sort!

So how much faster can we hope for? We derive a lower bound. When two elements $a_i$ and $a_j$ are compared, the set of all possible orderings is divided into two classes, those with $a_i>a_j$ and those with $a_i<a_j$. After $k$ such comparisons have been made, the set of all possible orderings has been divided into at most $2^k$ classes. If $2^k<n!$ then there is a class containing two different orderings. Consequently, if the original ordering of our $a_i$ is one of these orderings, then we have not yet distinguished it from all other possible orderings, and at least one more comparison is necessary. Thus for any sorting algorithm there is an ordering of the $a_i$ that gives rise to more than $(\log n!)/\log2$ comparisons. Since $n!>(n/e)^n$, the worst-case running time of any sorting algorithm is $\gg n\log n$. This lower bound is of the correct order of magnitude, since we have algorithms that run in $O(n\log n)$ time.

Among the possible methods that one might consider, we confine our attention to HeapSort, invented by J. W. J. Williams. This method runs in $O(n\log n)$ time, with the worst case only about 20% longer than the average. It is very easy to understand and to program, and requires little memory. In HeapSort, we think of the $a_i$ as forming a binary tree, in which $a_i$ has subordinates $a_{2i}$ and $a_{2i+1}$, as long as these indices do not exceed $n$. Conversely, if $i>1$ then $a_i$ reports to its superior, $a_{\lfloor i/2\rfloor}$. The situation for $n=28$ is depicted below:

If $a_i$ is smaller than one of its underlings then we exchange $a_i$ with the larger of $a_{2i}$ and $a_{2i+1}$. We repeatedly demote a particular entry until it majorizes its subordinates. (Executives above their level of competence are demoted.) We begin at the bottom of the table (high indices), and work up. Thus in the example above, we would compare $a_{14}$ with $a_{28}$, and exchange them if $a_{14}$ is the smaller. Then we compare $a_{26}$ with $a_{27}$ to determine which is the larger, and then compare that one with $a_{13}$. We demote $a_{13}$ if one of the numbers under it is larger. We continue with this, until $a_i\geq a_{2i}$ and $a_i\geq a_{2i+1}$ whenever the indices lie between 1 and $n$. Such a configuration we call a heap.

Once the heap has been formed, it is clear that $a_1$ is the largest number in the entire collection. We swap $a_1$ with $a_n$. This destroys the heap property, so we demote the new $a_1$ until it is restored. At this point we have a heap of $n-1$ numbers, and $a_n$ is ignored at the bottom. The new entry $a_1$ is the largest member in the heap (second largest, overall), so we exchange $a_1$ and $a_{n-1}$. At this point both $a_{n-1}$ and $a_n$ have reached their final resting places. We demote the new $a_1$ until we again have a heap, and then again the top of the heap is retired. Continuing in this manner, with successively smaller heaps, we eventually have no heap left, and $a_1\leq a_2\leq\cdots\leq a_n$.

For extremely large collections (such as the Manhattan telephone directory), it is important to sort as quickly as possible. In such cases it may be worth using the more complicated QuickSort algorithm. For a detailed discussion of sorting, see D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, 1973. In particular, HeapSort is described on pp. 145–149, 153–158.

Problem 10

The program HSortDem demonstrates the HeapSort algorithm. Choose the number $n$ of integers to be sorted, and witness the process. How does the number of comparisons compare with the lower bound derived above?