What on earth is “index calculus”?

If you are not an expert on mathematical aspects of public key cryptography you might wonder: What on earth is this method called “index calculus”? In fact, when I started my doctorate, I heard people speaking about that from time to time, and I had no clue what the method was all about. I thought that a method with such a strange name must be very, very complicated.

With this entry, I want to convince you that it is not really very complicated at all, and even its name makes sense.

The name

So, let’s start with the name. All kind of things are called “index” in mathematics, and given that we compute in groups here, it is natural to assume that “index” refers to the index of a subgroup in a group here. That’s what I thought for quite some time at least.

Well, it’s not so. In fact, “index” is the original term for “discrete logarithm” in the “classical” setting.

In the Disquisitiones Arithmeticae by Carl Friedrich Gauss from 1801, the following definition can be found.

Let p be a prime, let B be a primitive root modulo p, and let A be some natural number prime to p. Then any non-negative integer e with Be congruent to A modulo p is called index of A modulo p with respect to the basis B.

He then says that all indices of one number (with respect to a fixed modulus and base) are congruent to each other modulo p-1, and that these indices are going to be regarded as equivalent.

Let us call always call the smallest non-negative integer satisfying the definition the index, and let us denote the index by indBA. Analogously to the usual logarithm, we have indBA1 + indBA2 ≡ indB(A1 + A2) modulo p-1.

The index played an important role in explicit computations in the 19th century. And just as one used tables of logarithms, one used tables of indices or discrete logarithms in the modern terminology. Clearly, such a table can be restricted to indices of numbers below the modulus p.

The definition of an index be generalized for all numbers modulo which there exists a primitive root. These are the numbers 1,2,4,pk and 2pk for a prime p and a natural number k. A book consisting of such tables was published in 1839 by Carl Gustav Jacob Jacobi: the Canon Arithmeticus. It contains tables of indices modulo all prime powers below 1000. Let us mention how the tables were computed: First, for each index, the corresponding number was computed, by iteration. Then this table was “inverted” to obtain the table of indices. (By the way: Jacobi published the book, but the computations were done by many people. I once read or heard that some of the computations were done by Dirichlet’s wife, for example.)

We have thus clarified what the first part of the term “index calculus” means. And the second part? Does it have anything to do with “calculus”? Well, no. Here “calculus” is used in the original meaning of algorithmic method. So, it’s an algorithmic method to compute indices. But it’s not just any method but a particular approach.

The basic ideas

To motivate the approach, we make some observations on tables of indices. For these observations, please consider for the moment the “old” times where people made concrete computations by hand and printed tables.

The basic question is this: Let a particular prime p and a primitive root be fixed. Does one then really need a full table of indices modulo p?

The answer is “no”, provided one is willing to perform some computations if one is given a particular natural number and is asked for the index.

Namely:

1. Let’s assume that we can factor quickly any number below p. This is clearly the case for much larger numbers than 1000, which was the bound in the tables by Jacobi. Then we only need the indices of primes below p.

2. It suffices to have a sufficiently large table of indices of prime numbers below a particular bound. For this, let’s assume we have a table of indices below a bound S, and let A be an arbitrary number prime to p whose index we want to determine. We now consider C = A · Bi mod p for i=1,2 … until we have found a number which splits into primes below the bound S. Then we can look up the indices of the primes involved in the factorization of C and compute the index it. The index of A is then indBC -i. So, to determine the index of A we compute A · Bi mod p until this slits “over the table”. (By the way: Here and in the following I use “mod” as an operator, like is done in programming languages.)

Nowadays one employs two terms here: The bound S is called the smoothness bound, the set of primes below S is called the factor base and a number which splits into primes below S (that is, over the factor base), is called S-smooth of simply smooth.

Given this approach, one now is faced with the task to produce a table of all indices for a particular modulus and base below some bound. One way to perform this computation is to compute all indices as done by Jacobi and to only print a partial table. But is there a more efficient method?

Indeed there is, and it is based on relation generation and linear algebra. The basic idea is as follows:

Let’s say the factor base consists of the primes P1 … Pn.

We now consider powers of B modulo p.

Say we have Bi mod p = P1r1 … Pnrn. (This is called a “relation”.)

Then we have this “relation of indices”: i ≡ r1 indB P1 + … + rn indB Pn modulo p-1.

If we now have at least n such relations, we might try to determine the unknown indices by a linear algebra computation modulo p-1. Note here that this a bit more complicated than usual in linear algebra because p-1 is not a prime (except if p=3 of course but then question to determine a table of indices is not too complicated …).

So, this is the “index calculus” method in a classical description. Below I am going to present a slightly different method for the task to compute just one index, not a table of indices.

Now a bit of history: As far as I know, the method is due to Maurice Kraitchik. It appeared in one of his books Théorie des Nombres from 1922. Kraitchik liked to do explicit computations, and his books are written from that perspective. He demonstrates the method with an example. Interestingly, he even used the method of “large prime” variation. Here, one allows up to one prime larger than the smoothness bound in each relation. If one has two relations with the same large prime, one subtracts them and obtains a relation over the factor base.

In the 1968 Alfred Edward Western and Jeffrey Charles Percy Miller published tables of indices computed with the relation generation and linear algebra method. For quite some time, the index calculus method was then incorrectly attributed to Western and Miller or (by Miller) to Western. The term “index calculus” is due to Andrew Odlyzko. (He writes: “We will refer to it as the index-calculus algorithm.”) It is also interesting to note that the method is much older than the ρ-method or the baby-step-giant-step method.

Possible generalizations and a variant

One can say that up to now, we wanted compute discrete logarithms in the groups Fp*. In principle, one can substitute this group by any finite group. We fix a particular class of explicitly given finite groups.

The discrete logarithm problem for the given class of groups is then: Given a group G from the fixed class and a,b in G with a in the group generated by b, compute e with be = a.

Particular classes of groups of interest are:

Fp*, p prime,

Fq*, q a prime power,

E(Fq) for an elliptic curve E over Fq,

– The degree 0 divisor class group of a smooth, projective curve over a finite field (or — what is the same — of a function field in one variable) over a finite field.

We restrict ourselves to abelian groups and now write the group law additively. As said, the input is a group G and a,b in G with a in the group generated by b.

A variant of the index calculus method as described above to compute just the desired discrete logarithm (rather than a table of indices) is as follows:

“Direct” index calculus

1. Compute the group order N := #G.

2. Fix a so-called “factor base” F = {p_1, p_2, …}, which is a subset of G.

3. Compute more than #F so-called “relations” j rij pj = αi a + βi b. Store these in a “relation matrix” R = ((rij)).

4. Compute a non-trivial vector γ over Z/nZ with γ R = 0.

One now has i γi αi a + ∑i γi βi b = 0. Thus if i γi αi is invertible in Z/NZ, one has a = – (∑i γi βi) / (∑i γi αi) b.

Then problem is then solved.

To my information, this approach is due to Pierrick Gaudry, and it first appeared in his work on index calculus in the class groups of hyperelliptic curves. Needless to say, an application of this method depends on several subalgorithms. For example, for the “classical” application in Fp*, one can choose the factor base as the set of primes below a bound S, the so-called “smoothness bound”. Then one can generate relations by choosing αi and βi uniformly randomly modulo p-1 and by performing trial division with factor base elements. Note here that for computations in the group Fp*, the addition in the algorithm has to be substituted by multiplication in this group.

The complexity theoretic perspective

Since about the 1960’s, an additional focus on computational problems has emerged: Rather than being interested in explicit computations, one is now also interested in proven results on asymptotic running times. It seems to be extremely hard to obtain any interesting proven upper bounds with deterministic algorithms. But for randomized algorithms, one can obtain nice results. These results can be stated in two ways which are in fact equivalent. The first way is: One states that one has a Las Vegas algorithm which operates in a given time. Here the output is always correct but the algorithm might fail with a probability of up to 1/2. Or one states an upper bound on the expected running time of the algorithm. Note here that “expected running time” refers only to the internal randomization of the algorithm. There is no averaging on the input set.

A classical theorem is:

With a randomized algorithm, the classical discrete logarithm problem can be solved in an expected time of exp((√2 + o(1)) · (log(p) · log log(p))1/2).

This result, of course based on the index calculus method, is due to Carl Pomerance. It can also be found in a work by Enge and Gaudry in which they give a general framework for index calculus algorithms. The algorithm by Pommerance is based on the original index calculus method whereas the algorithm by Enge and Gaudry is essentially based on the “direct” approach presented above. In both works, the algorithms are slightly more complicated in order that a proven upper bound on the expected running time can be achieved.

In their general framework, Enge and Gaudry assume that one has an explicit homomorphism from a free abelian mononoid to the group, like for example the homomorphism from the natural numbers prime to to Fp*. (The natural numbers are a free abelian monoid on the prime numbers.) Just as prime numbers are natural numbers and not elements of Fp*, the factor base elements are then generators of the free abelian monoid. This general framework can then for example also be applied to computations of discrete logarithms in multiplicative groups of finite fields of small characteristic and to degree 0 divisor class groups of complete, non-singular curves of not too small genus over finite fields. In the former case, one substitutes prime numbers with irreducible polynomials and in the latter case one substitutes them with prime divisors.

In contrast to the general framework by Enge and Gaudry, in the “direct approach” presented above the factor base elements are group elements. This variant is useful for applications of the index calculus method to elliptic curves over extension fields. This will be the content of my next entry.


— Claus Diem

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s