Factoring and Factorials

Computing the factorial function fast breaks factoring

Adrien-Marie Legendre was one of the great number theorists of the century. He proved a whole host of amazing results. One wonders what he would think of the applications and consequences of his work over a century later. One of his great discovers is the Duplication Formula for the Gamma Function. The Gamma function, , is a function defined for all complex numbers that agrees with the factorial function at the natural numbers. In a sense you should think of the Gamma function as a generalization of the factorial function. The factorial function is, of course, defined for natural numbers as:

The exact relationship between them is that : you might ask why the and not ? There is an interesting story here, but I am not the right one to tell it, so for us we will just have to accept it. See this for more details from our friends at Wikipedia.

So what is the duplication formula and why is it connected to factoring? I will explain. The formula is this: for all complex ,

The rationale for calling it the “Duplication Formula” is that the left hand side is almost a “duplication”. Except for the the formula would have exactly two occurrences of the Gamma function at the same value. Hence, the name the “Duplication Formula”. However, the two Gamma functions are evaluated at slightly different values: one at and one at . This small difference is not, in my opinion, exactly a duplication: perhaps it should be called the “Almost Duplication Formula”. My guess is that this name would not be nearly as cool and exciting.

So what is the connection between the Duplication Formula and factoring? We will see shortly that if the formula where a real duplication formula, then we could factor in polynomial time. Thus, Legendre came within a of having discovered a formula that would be able to factor fast, would break modern factoring based crypto-systems like RSA, and generally would be a huge result. Alas, there is that small but critical . It barely misses. As agent Maxwell Smart on the old TV show “Get Smart” used to say, “missed by that much”. More precisely, if the formula was instead

for some constant and some a polynomial in , then factoring would be easy. The rest of this post is an explanation of why this is true.

Factoring with Factorials

One of the curious properties of is a folk theorem about it’s arithmetic complexity. Say that a function has arithmetic complexity provided there is a arithmetic circuit that computes in steps. As usual an arithmetic circuit starts with the variables and the value , then at each step it performs one of the basic arithmetic operations from on a pair of previous values. The answer is, of course, the last value computed.

One of the major assumptions of modern cryptography is that factoring of integers is hard. For cryptography one usually needs a less general assumption: Suppose that for and random primes in a range . Then it is hard to find and from just provided is large enough. Note, often there are additional constraints placed on the primes, but these will not affect our discussion.

By “hard” we can mean that there is no polynomial time algorithm or even that there is no circuit of polynomial size. The problem with this assumption is many-fold. First, the problem of factoring is in so that it is unlikely to be NP-complete. Second, the best algorithms for factoring are “sub-exponential”. For example, the the approximate running time of the Number Field Sieve is:

where is about . (There are some much smaller terms in the exponent, but is the main term.) Thus, if factoring was NP-hard, there would be dire consequences for complexity theory. In another post I will discuss the factoring assumption further. For now I just will remark that at a conference a few years ago Avi Widgerson spoke on the uses of the factoring asumption and Michael Rabin spoke on the possibilities that factoring could be easy.

I find, like many others, this problem to be extremely interesting. In this post I want to point out an old but interesting connection between factoring and factorials. In later posts I will discuss the current best approaches to factoring and the potential for better methods in the future. For now we will concentrate on the connection with the factorial function. Here is the folk theorem:

Theorem 1 If can be computed by a straight-line arithmetic computation in steps, then factoring has polynomial size circuits.

We have stated the theorem as a non-uniform result. If you want a uniform bound then you need to make the stronger assumption that the arithmetic circuit for is uniform.

The proof of this folk theorem is simple. Suppose that you wish to factor some non-zero number that is composite. For any number define the number as . (As usual is the greatest common divisor (gcd) of and .) We claim that has the following key property: either or or is a proper factor of . This follows directly from the definition of the gcd.

Now we will use this function and binary search to get a proper factor of . Once we have such a factor we can get all the factors by applying the method again. The binary search works as follows: set and . Note, that the interval has the following property: and that . The latter follows since cannot be ; thus, if it is less than we have a proper factor. In general we will always have an interval so that and .

Suppose we have such an interval. We claim that cannot equal Assume by way of contradiction that . Since it follows that and . Thus, must equal which is impossible. So . Let be the number that is closest to the mid-point between and Check whether or not is a proper factor of . If it is not then there are only two cases. In the first the gcd is . In this case go to the interval . In the second case the gcd is , in this case go to the interval . Since this process stops eventually it must find a proper factor of .

There is one missing, but critical point. We cannot afford to compute the factorials used in the above procedure. They will be too big. So we simply use the arithmetic circuit to do all the above computations, but do all of them modulo . The key insight is that this does not change any of the gcd calculations. This depends on the simple fact that is the same as .

What is The Complexity of Factorials

So what is the complexity of computing . Since currently factoring is believed to be hard clearly it must be hard to compute this. But is it really hard?

Let’s recall the Duplication Formula:

If the formula was instead

then there would be a fast algorithm for factorial. Then we would be able to factor. Let be the cost of computing . Then, such a equation would yield that

This implies a fast method of computing .

Imagine that where is a rational function and each is an exponential term. That is a term of form where and are polynomials. If this was true, then would be easy to compute. Note, this remains true even if the identity only holds true for a dense subset of the natural numbers . That is must satisfy the property that for each there is a so that is at most .

Even more. Suppose that is a function so that

for the natural numbers. Then, computing this function fast would be enough. Note, the point of this generalization is that you cannot use some simple growth argument to show that there is no real duplication formula formula–at least I do not see one.

Open Problems

Can we prove that cannot satisfy any such equation? I think that this might be hard, but it would certainly be interesting to have such a result. While it would not be a general lower bound on factoring, having a result that there is no real “duplication formula” would at least show that there is no easy way to factor. On the other hand having no such lower bound shows how little we know about factoring. Those who believe that factoring is hard should be worried that we cannot even dismiss the possibility that such a factoring method may exists.

Another direction will be discussed in a future post. The approach is to look not at the factorial function directly but indirectly via a polynomial. Consider the polynomial defined for each . If we can compute this polynomial in steps, then clearly we can compute in steps: just set . However, suppose more generally that is a polynomial with distinct integer roots. If we can efficiently compute fast then can we still factor fast? The answer is yes under mild conditions on the distinct roots. More on this in the future.