Skip to content

A Most Perplexing Mystery

May 6, 2013


The discrete log and the factoring problem

Unknown

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 {\mathsf{P}=\mathsf{NP}} 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 {p,q} are primes.

  • The discrete log problem is: Given {y=a^{x} \bmod p}, find the value of {x}.

  • The factoring problem is: Given {y=p\cdot q}, find the value of {p,q}.

What possible relationship is there between these problems? One concerns the structure of the finite field modulo some large prime {p}. 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 {y = pq}, with operations modulo {y}. Every element {a} has an order {x}, meaning a least integer {x > 0} giving {a^x = 1} (mod {y}), and this is the period of the powers of {m}. In essence, {x} is the discrete logarithm of {1} in base {a} in this ring. Shor’s algorithm gives a high-enough-to-amplify probability that a randomly chosen {a} has a findable period {x} that helps produce a factor of {y}.

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 {\mathbb{F}_{p^k}}, {p} is the characteristic and {k} is the degree of extension from the prime field {\mathbb{F}_p}. The prime field is the same as the field {\mathbb{Z}_p} of integers modulo {p}, but {\mathbb{F}_{p^k}} should not be confused with the integers mod {p^k}, which do not form a field. The idea of characteristic is also a distinction from {\mathbb{Z}_{pq}}.

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

\displaystyle L_Q(\beta,c) = \exp((c+o(1))(\log Q)^\beta(\log\log Q)^{1-\beta}).

Here we may have {Q = p^k}. The length of the input is essentially {n = O(\log Q) = O(k\log p)}. The backbone of this formula is {\exp(cn^\beta)}, while the {(\log\log Q)^{1-\beta}} factor acts as a counterweight. The main focus is the exponent {\beta}. If taken only thus far, the characteristic {p} seems subservient to the degree {k} in the time, since the formula takes the logarithm of {p}.

The relation between {c} and {\beta} 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 {c} part is often bounded and ignorable, yielding the simpler designation {L(\beta)} for the formula. The game plan is to improve the axis of the {c}-vs.-{\beta} tradeoff, to get lower {\beta}.

The breakthrough by Joux is to do this when {p} is bounded. This is important while bootstrapping the algorithm through extension fields {\mathbb{F}_{q^k}} and {\mathbb{F}_{q^{2k}}}, where {q} itself is a power {p^\ell} making {p^\ell \approx k}. The result is:

Theorem: For bounded {p}, discrete logarithms in fields of characteristic {p} can be computed in time {L(1/4 + o(1))}.

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 {\longrightarrow} 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 {g(x)} is a polynomial known to split into many small factors, then for any field constant {a}, the linearly transformed polynomial {g(ax)} 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

    \displaystyle h(x) = \frac{ax+b}{cx+d}.

    is sometimes called a “fractional linear transformation,” and in complex analysis is known as a Möbius transformation. Now {g(h(x))} is not a polynomial, but it becomes a polynomial {g'} again upon multiplication by {(cx+d)^D} where {D} is the degree of {g}.

    Joux proves that if you take a polynomial {g} that splits into small factors over the base field {\mathbb{F}_q}, and take any {a,b,c,d} in an extension field {\mathbb{F}_{q^k}} such that {ad \neq bc}, then the resulting polynomial {g'} over {\mathbb{F}_{q^k}} likewise splits into small factors over {\mathbb{F}_{q^k}} (though irreducibility and degrees may not be preserved from the corresponding factors of {g}).

    The amplifying advantage is that whereas the {g(ax)} transformation gives at most the size of the field number of new polynomials, the {g'} transform gives approximately the cube of that size—after eliminating redundancies and trivialities that happen when {a,b,c,d} are all in the base field {\mathbb{F}_q}, 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 {x^q - x} splitting into linear factors over {\mathbb{F}_q}. A further fact of particular importance is:

Lemma: A polynomial {x^{n+1} + a x^{n} + b x + c} splits (into linear factors) over {\mathbb{F}_p} if and only if

\displaystyle  x^{(n+1)} + x^{n} + b a^{-n} x + c a^{-n-1}

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?

About these ads
25 Comments leave one →
  1. May 6, 2013 7:50 pm

    Just a thought, more loose than lucid most likely —

    There is another kind of “discrete logarithm” that I used to call the “vector logarithm” of a positive integer n. Consider the primes factorization of n and write the exponents of the primes in order as a coordinate tuple (e_1, \ldots, e_k, 0, 0, 0, \ldots), where e_j = 0 for any prime p_j not dividing n and where the exponents are all 0 after some finite point. Then multiplying two positive integers maps to adding the corresponding vectors.

  2. May 7, 2013 1:16 pm

    have always wondered about this vaguely myself somewhat, the discrete log/factoring link (but of course not on this same level of sophistication!) wondering if there is some [complexity theory?] problem equivalent yet less complex than the hidden subgroup problem that is rather involved to state, and moreover while there are remarkable/at other times exotic individual cases [eg barringtons thm, or the symmetric group] — its never seemed to me that group theory is highly central or fundamental to TCS. this seems somewhat surprising, given its paramount importance in theoretical math, that there is not some deeper link. maybe a missing important bridge thm? have long suspected there could maybe be a link to automated theorem proving, eg/ie maybe a group structure in automated proofs, etc., or maybe some key link to certain types of languages/grammars, etc.

    • May 7, 2013 9:08 pm

      Groups are inversely related to complexity. Any time you have symmetry in a problem space it reduces the complexity of the problem — finding one solution in an orbit gives you all the rest by way of relatively simple transformations.

      • Javaid Aslam permalink
        May 8, 2013 2:54 pm

        And yet nobody seems to work on or care to read an application of group theory to NP=?P issue.

    • May 8, 2013 11:02 am

      By the way, the inverse relationship between symmetry and diversity — that we see, for example, in the lattice-inverting map of a Galois correspondence — is a variation on an old theme of logic called the “inverse proportionality of comprehension and extension”.

      C.S. Peirce, in his probings of the “laws of information”, found this principle to be a special case of a more general formula, saying that the reciprocal relation holds only when the quantity of information is constant.

      Here is a reading —

      Peirce (1867), “Upon Logical Comprehension and Extension”

    • May 13, 2013 2:00 pm

      Here are my ongoing if slightly sporadic notes on Peirce’s information theory and its relation to the logic of science —

      Information = Comprehension × Extension

  3. May 7, 2013 7:25 pm

    In the post “Factoring Could be Easy” of this blog an idea is described, which could more or less be stated as:

    If n! mod m could be calculated in polynomial time for integers n,m then Factoring is in P.

    Isn’t this a nice example of a technique which would work essentially for both factoring and discrete log?

    As “equally” a fast way of testing if

    (a^1 – y)*(a^2 – y)*…*(a^n – y) = 0 mod p

    would let you calculate y = a^x mod p efficiently.

  4. May 7, 2013 10:09 pm

    dude… huh?! wow!! thx for the reaction/musing, but…. have no idea where you got this idea. any refs? it strikes me unfortunately, as not “not even wrong” but as spectacularly wrong! there is an extraordinary, staggering inherent/fundamental complexity in group theory eg given that the classification of the finite simple groups took something like ~1Century, dozens of mathematicians and 1000s of pages! also the monster group is an extraordinary object surely with some deeper meaning/link in TCS…. theres gotta be something to all this…. but it would seem in TCS we’re still “flying blind” in a big way….

    • May 8, 2013 12:33 pm

      oops fyi threaded this wrong! its in reply to this comment asserting “Groups are inversely related to complexity.”….

    • May 8, 2013 1:28 pm

      Well, I do love a good spectacle, but here I am just using the word complexity to describe what we might otherwise call a measure of diversity or variety in a problem space, the extent to which we have to treat problem instances as isolated cases without any class or rule that relates them to others.

  5. Javaid Aslam permalink
    May 8, 2013 2:57 pm

    ” … Lance Fortnow the other day and he immediately offered to make a bet …”.

    I wonder how much of bet Lance would be willing to make on NP[FP] = #P.

  6. curiousfellow permalink
    May 9, 2013 2:49 am

    If $n!$ in $log^{c}(n)$ is to factoring $N: N > n > \sqrt{n}$, then $X$ is discrete logarithm over $\mathbb{F}_{p}: p$ satisfies some property of $X$. What is $X$?

  7. Serge permalink
    May 9, 2013 7:54 pm

    Logarithms were invented to simplify multiplications, so it seems just natural that they be also involved in factoring, the inverse of multiplication.

    However, I’d be interested to know if the aforementioned bet went as far as the polynomiality of factoring…

  8. asdf permalink
    May 12, 2013 10:34 pm

    In ‘Applied Cryptography’ p.262, Bruce Schneier wrote: “Computing discrete logarithms is closely related to factoring. If you can solve the discrete logarithm problem, then you can factor. (The converse has never been proven to be true.)”

    • asdf permalink
      May 16, 2013 8:28 am

      The base is a generator. So the log is the totient of the modulus. Knowing that the latter is the product of two primes p and q, the log will then be (p-1)(q-1). So yes, you can factor with the discrete log. Got this solution while waking up. In fact, I’m typing this from my bed in California. I hope it’s not the kind of nonsense I can come up with in the morning. At least, I’ll have the feeling of having solved a mystery for a couple of hours. Not sure anyone reads these old threads anyway.

      • asdf permalink
        May 16, 2013 8:31 am

        I mean, the log of 1.

      • asdf permalink
        May 16, 2013 9:29 am

        Well, that’s if we’re given the generator. It is supplied in the discrete log problem, but not in the factoring problem. So it all depends on the complexity of finding a generator for the modulus’ multiplicative group. I have no idea if it’s in P. I guess I’ll have to read Schneier’s bibliography.

      • asdf permalink
        May 16, 2013 3:26 pm

        Well it would be nice if we had uniqueness of the log of x. We don’t, but I guess the solution Schneier alluded to could be along these lines. What’s clear to me however is that there’s no abyssmal disconnect between the two problems; far from it.

  9. Anthony permalink
    June 19, 2013 1:42 pm

    Further progress on the discrete log:
    “A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic”

    http://arxiv.org/abs/1306.4244

Trackbacks

  1. Information = Comprehension × Extension : 1 | Inquiry Into Inquiry
  2. Graduate Student Traps | Gödel's Lost Letter and P=NP
  3. The Winner Is… | Gödel's Lost Letter and P=NP
  4. Elliptic Curve Diffie-Hellman | Math ∩ Programming

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

Follow

Get every new post delivered to your Inbox.

Join 2,022 other followers