A Most Perplexing Mystery

The discrete log and the factoring problem

Antoine Joux is a crypto expert at Versailles Saint-Quentin-en-Yvelines University. He is also one of the crypto experts at CryptoExperts, having joined this startup company last November. His work is featured in all three of the company’s current top news items, though the asymptotic breakthrough on the exponent of finding discrete logs in small-characteristic fields which we covered last month is not among them. In its place are concrete results on two fields of medium characteristic (between a million and a billion) whose elements have bit-size 1,175 and 1,425. The news release on this concludes (emphasis in original):

[We] recommend to all cryptographic users to stop using medium prime fields.

Today I want to talk about a mystery, which I find the most puzzling problem in all of complexity theory, but which Ken thinks is “only” a sign of youth of the field.

Not the question, not what is the power of quantum computers, not graph isomorphism, nor any other number of great puzzles. The single strangest problem, in my opinion, is the relationship between the discrete log problem and the integer factoring problem.

History shows that every improvement to one of the these problems seems to yield rather quickly a corresponding improvement to the other. This works for quantum and classical algorithms alike—recall that Peter Shor’s famous paper solved both problems at one stroke. As related here:

Historically, it has been the case that an algorithmic advance in either problem, factoring or discrete logs, was then applied to the other. This suggests that the degrees of difficulty of both problems are closely linked, and that any breakthrough, either positive or negative, will affect both problems equally.

The Problems

Let me restate the two problems for comparison, where are primes.

• The discrete log problem is: Given , find the value of .

• The factoring problem is: Given , find the value of .

What possible relationship is there between these problems? One concerns the structure of the finite field modulo some large prime . The other is about the multiplicative structure of the integers.

There is no known reduction from one to the other, at least none known to me. This is the great mystery.

However, they have a common parent. Consider the finite ring of integers relatively prime to , with operations modulo . Every element has an order , meaning a least integer giving (mod ), and this is the period of the powers of . In essence, is the discrete logarithm of in base in this ring. Shor’s algorithm gives a high-enough-to-amplify probability that a randomly chosen has a findable period that helps produce a factor of .

That the same idea works for discrete logarithms in fields indicates that this common parent problem captures at least some techniques that work for both factoring and discrete log. This MathOverflow item points out the importance of this being in turn a case of the hidden-subgroup problem for Abelian groups. Ken feels that only recently is the area finding techniques that really separate the problems from their parent, an indication of the field shedding its youth. This paper by Joux is an example, as we explain next.

The Breakthrough

The new wrinkle—a sign of maturity—is that the improvement in the running time depends on the characteristic of the field, and is greatest when it is fixed. Recall that in a finite field , is the characteristic and is the degree of extension from the prime field . The prime field is the same as the field of integers modulo , but should not be confused with the integers mod , which do not form a field. The idea of characteristic is also a distinction from .

Running times of algorithms for factoring and discrete log have heretofore been expressed in terms of the “-function,” whose general form is defined by

Here we may have . The length of the input is essentially . The backbone of this formula is , while the factor acts as a counterweight. The main focus is the exponent . If taken only thus far, the characteristic seems subservient to the degree in the time, since the formula takes the logarithm of .

The relation between and partly depends on how two phases of the algorithms are balanced, a “sieving phase” in which information about specific field elements is compiled, and a “linear algebra phase” for the main computation. Once other parameters are chosen to effect the balance, the part is often bounded and ignorable, yielding the simpler designation for the formula. The game plan is to improve the axis of the -vs.- tradeoff, to get lower .

The breakthrough by Joux is to do this when is bounded. This is important while bootstrapping the algorithm through extension fields and , where itself is a power making . The result is:

Theorem: For bounded , discrete logarithms in fields of characteristic can be computed in time .

His paper itself emphasizes two new ideas, which we express in terms we’ve described earlier on this blog.

Ingredients

Many “sieving” algorithms for factoring and discrete log begin with what strikes us as the opposite idea to the famous Sieve of Eratosthenes. That sieve works to find primes by crossing off numbers with factors. The newer sieves have the opposite goal: they want to find integers with lots of small factors.

A big reason lots of small factors are useful is that they help build Chinese Remainder representations for large numbers while keeping their own arithmetic simple. More generally put, the small factors help generate a lot of congruences—and the large numbers with those factors serve as common zero-points for those congruences. As a general strategy point, the more small factors with known multiples, the better. Here is where we mention one idea from our old post that is already presumed by Joux:

1. Integers polynomials: As we wrote before, integers share many properties with polynomials over the integers, but polynomials are usually much easier to handle. For example, the analogue of the famous Goldbach conjecture is solved for polynomials but is still open for integers: Every nontrivial polynomial over the integers can be written as a sum of two irreducible polynomials. For another example, the deterministic primality algorithm of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena begins by introducing polynomials over one variable.

   In Joux’s case, polynomials are used to construct extensions of finite fields to begin with. Joux operates further on these extensing polynomials. Adding one or a few variables creates more ways to define small factors. Thus using polynomials already constitutes a way to amplify, but Joux found a new way to carry this further.

2. Amplifying Linearity: If is a polynomial known to split into many small factors, then for any field constant , the linearly transformed polynomial also has this property. This was previously known and exploited as far as it can go. Joux noticed that certain ostensibly-nonlinear transformations could wind up having the same effect. Well, a transformation of the form

   

   is sometimes called a “fractional linear transformation,” and in complex analysis is known as a Möbius transformation. Now is not a polynomial, but it becomes a polynomial again upon multiplication by where is the degree of .

   Joux proves that if you take a polynomial that splits into small factors over the base field , and take any in an extension field such that , then the resulting polynomial over likewise splits into small factors over (though irreducibility and degrees may not be preserved from the corresponding factors of ).

   The amplifying advantage is that whereas the transformation gives at most the size of the field number of new polynomials, the transform gives approximately the cube of that size—after eliminating redundancies and trivialities that happen when are all in the base field , for example. He also employs transforms by ratios of two quadratic polynomials.

3. Seeding More than Sieving: The cubic advantage from the last step is so great that the algorithm can dispense with sieving steps needed to build a base of small factors via search. Instead we can “seed” the base with some polynomials known to have many small factors in advance. Joux starts with the simple case of splitting into linear factors over . A further fact of particular importance is:

Lemma: A polynomial splits (into linear factors) over if and only if

also splits.

The Future

When I saw Dan Boneh at the RSA conference, as I first related here, he felt very confident that Joux’s work would lead soon an improvement in factoring. We will see if these happens, but his feeling needs to be taken quite seriously since he is an expert in computational number theory. I mentioned this to Lance Fortnow the other day and he immediately offered to make a bet with me. We have yet to work out the details, but I believe we will firm up the bet shortly.

Open Problems

Would you like to take sides on the bet? Will factoring get improved too? What about the mystery? Is there even some heuristic that explains why these problems are related, in a more detailed way than their common parentage?