Skip to content

Factoring and Factorials

February 23, 2009


Computing the factorial function fast breaks factoring

images22

Adrien-Marie Legendre was one of the great number theorists of the {19^{th}} 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, {\Gamma(z)}, 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 {n } as:

\displaystyle  n! = 1 \times 2 \times 3 \times \dots \times n.

The exact relationship between them is that {\Gamma(n+1) = n!}: you might ask why the {n+1 } and not {n }? 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 {z},

\displaystyle \Gamma(z)\Gamma(z+1/2) = 2^{1-2z}\sqrt{\pi} \Gamma(2z).

The rationale for calling it the “Duplication Formula” is that the left hand side {\Gamma(z)\Gamma(z+1/2)} is almost a “duplication”. Except for the {1/2} 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 {z} and one at {z+1/2}. 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 {1/2} 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 {1/2}. 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

\displaystyle  \Gamma(z)\Gamma(z) = c 2^{w} \Gamma(2z)

for some constant {c} and some {w} a polynomial in {z}, 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 {n!} is a folk theorem about it’s arithmetic complexity. Say that a function {f(n)} has arithmetic complexity {t(n)} provided there is a arithmetic circuit that computes {f(n)} in {t(n)} steps. As usual an arithmetic circuit starts with the variables and the value {1} , then at each step it performs one of the basic arithmetic operations from {\{ +,-,\times,\div \}} 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 {X = pq} for {p} and {q} random primes in a range {[2^{m},2^{m+1}]}. Then it is hard to find {p} and {q} from just {X} provided {m} 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 {\text{NP} \cap \text{co-NP}} 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:

\displaystyle  \exp \big( c \log^{1/3} X \big)

where {c} is about {2}. (There are some much smaller terms in the exponent, but {\log^{1/3} X} 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 {n!} can be computed by a straight-line arithmetic computation in {O(\log^{c} n)} 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 {n!} is uniform.

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

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

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

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 {X}. The key insight is that this does not change any of the gcd calculations. This depends on the simple fact that {(z,X)} is the same as {(z \bmod X,X)}.

What is The Complexity of Factorials

So what is the complexity of computing {n! }. 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:

\displaystyle \Gamma(z)\Gamma(z+1/2) = 2^{1-2z}\sqrt{\pi} \Gamma(2z).

If the formula was instead

\displaystyle \Gamma(z)\Gamma(z) = c 2^{w} \Gamma(2z)

then there would be a fast algorithm for factorial. Then we would be able to factor. Let {G(n)} be the cost of computing {\Gamma(n)}. Then, such a equation would yield that

\displaystyle  G(n) \le G(n/2) + O(\log^{O(1)} n) .

This implies a fast method of computing {n!}.

Imagine that {\Gamma(2z) = R(z,\Gamma(z),a_{1},\dots,a_{l})} where {R()} is a rational function and each {a_{i}} is an exponential term. That is a term of form {b(z)^{c(z)}} where {b} and {c} are polynomials. If this was true, then {n!} would be easy to compute. Note, this remains true even if the identity only holds true for a dense subset of the natural numbers {S}. That is {S} must satisfy the property that for each {x} there is a {y \in S} so that {\mid x - y\mid} is at most {O(\log^{O(1)} x)}.

Even more. Suppose that {\Gamma^{*}(n)} is a function so that

\displaystyle  (\Gamma^{*}(n),n!)=n!

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 {n!} 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 {f_{n}(x) = (x-1)(x-2)(x-3)\dots(x-n)} defined for each {n }. If we can compute this polynomial in {s} steps, then clearly we can compute {n! } in {s } steps: just set {x=0 }. However, suppose more generally that {g_{n}(x)} is a polynomial with {n } distinct integer roots. If we can efficiently compute {g_{n}(x)} fast then can we still factor fast? The answer is yes under mild conditions on the distinct roots. More on this in the future.

About these ads
18 Comments leave one →
  1. February 28, 2009 2:52 am

    I just realized that this vaguely relates to a miscellaneous approximation I figured out recently for n choose n/2, namely:
    2^n/\sqrt{\frac{\pi}{2}n+\frac{\pi}{4}+\frac{\pi}{16}n^{-1}-\frac{\pi}{32}n^{-2}-o(n^{-2})}

    From this, one can fairly simply find that:
    \Gamma(z)\Gamma(z) = \Gamma(2z)(2^{2z-2})(2z-1)/\sqrt{\pi(z-1)+\frac{\pi}{4}+\frac{\pi}{32}(z-1)^{-1}-\frac{\pi}{128}(z-1)^{-2}-o(z^{-2})} \approx \Gamma(2z)(2^{2z-2})(2z-1)/\sqrt{\pi(z-1)+\frac{\pi}{4}+\frac{\pi}{32}(z-1)^{-1}-\frac{\pi}{128}(z-1)^{-2}}

    It should give a closer and closer relative approximation the higher z goes, adding ~2.5 digits of accuracy whenever z is quadrupled, and it’s accurate to about 13 digits for z near 400. Of course, that probably isn’t nearly enough, since it doesn’t appear to have decreasing absolute error, only relative error. Any thoughts?

    • rjlipton permalink*
      March 1, 2009 8:38 am

      Its a neat idea, but I think that you are right that the error will still be too large. Isn’t strange how close the duplication formula get?

  2. Aram Harrow permalink
    April 21, 2009 1:01 am

    If you could factor efficiently, with either a new algorithm or a quantum computer, would that imply the ability to compute n! mod p efficiently?

    • rjlipton permalink*
      April 21, 2009 10:57 am

      Very cool question. I assume you mean n! mod p is large. I do not see that factoring implies the factorial result. I will do another post on factorials soon, since more to say. But very neat idea.

  3. anonymos permalink
    December 29, 2009 8:50 pm

    This is post a little bit of topic (and a little late ) but when it comes to factorials i like the following little question.

    Take the following set of matrices:

    A(0) = [1]

    A(n+1) =

    2*A(n) I
    I 2*A(n)

    where A(n) is a (2^n)X(2^n) matrix and I is the identidymatrix.

    For every natural number n :

    What is the determinant of (1/2)*( A(n) + I ) ?

    Not a very hard question nor a very helpful result,
    but i still like the answer :-)

  4. Stephen permalink
    July 14, 2011 11:49 am

    Could someone please expand a little more as to how a “true” duplication formula would lead to an efficient algorithm for calculating factorials?

    Thanks…

  5. Carlo Ceccarelli permalink
    September 1, 2011 7:14 pm

    Is not possible to have one exact formula for buplicate the factorials, based only
    in power or multiplication. If m=p1*p2, p1, p2 primes, p1/2 > n > p1,
    n! mod m do not contain p1 but (2*n)! mod m do it.
    But only with multiplication or power with operand p1 , is not possible to obtain (2*n)! mod m. It contain p1: it is factor of m, not recreable from multiplication or power of numbers coprime with m.
    It is true?

  6. August 12, 2012 7:55 pm

    I have few questions:
    1) We know that sum of 1 to n integers can be done in 3 arithmetic operations using n(n-1)/2 on 2logn sized words. Is it known that n! cannot be calculated using constant number of arithmetic operations on O(nlogn) sized words?

    2) Say we have an O(nlogn) x O(nlogn) matrix A. Supposing if we represent n as a vector v and we have a relation A^mv as vector representation of n! would that be an arithmetic circuit to calculate n! operating on O(nlogn) sized words? This will definitely be in O(logn) steps since A^m can be calaculated in O(logn) steps?

    3) If A^mv in 2) can be represented by an arithmetic circuit yielding n! in O(logn) steps, it is not quite clear, why such a circuit would yield a matrix B of size O(logn) x O(logn) such that B^mv represents n!modX for some X of size logn or why such a circuit would yield matrices Bi of size O(logn) x O(logn) for i =1 to O(logn) such that prod_{i}(Bi)v would represent n!modX for some X of size logn?

  7. August 12, 2012 7:58 pm

    Forgot to mention size of m
    I have few questions:
    m is O(n) in following
    1) We know that sum of 1 to n integers can be done in 3 arithmetic operations using n(n-1)/2 on 2logn sized words. Is it known that n! cannot be calculated using constant number of arithmetic operations on O(nlogn) sized words?

    2) Say we have an O(nlogn) x O(nlogn) matrix A. Supposing if we represent n as a vector v and we have a relation A^mv as vector representation of n! would that be an arithmetic circuit to calculate n! operating on O(nlogn) sized words? This will definitely be in O(logn) steps since A^m can be calaculated in O(logn) steps?

    3) If A^mv in 2) can be represented by an arithmetic circuit yielding n! in O(logn) steps, it is not quite clear, why such a circuit would yield a matrix B of size O(logn) x O(logn) such that B^mv represents n!modX for some X of size logn or why such a circuit would yield matrices Bi of size O(logn) x O(logn) for i =1 to O(logn) such that prod_{i}(Bi)v would represent n!modX for some X of size logn?

  8. August 13, 2012 2:15 pm

    It is very easy to come up with such an O(nlogn) x O(nlogn) sized A so that A^mv represents n! Will this be an arithmetic circuit? If so, then BSS conjecture is false that is n! can be done in logn steps on nlogn words using just {+,*}.

    Also even if this is an aithmetic circuit, then even then it may not yield a way to calaculate n!modX any more efficiently than brute force. So may be having an arithmetic circuit calculate n! in logn steps may not suffice to calculate n!modX in logn steps.

  9. December 5, 2012 6:00 pm

    Is division allowed in a straight line pogram? I thought Shamir gave an arithmetic circuit with division?

  10. December 20, 2012 11:11 pm

    what of there is an arithmetic circuit to calculate $n!$ within $\pm \kappa$ error, where $\kappa$ is a constant independent of $n$, in $O(\log^{a}(n))$ steps? Could one pretend to do $n! mod N$ and work gcd of the remainder and $N$ within all possible $\pm \kappa$ error values of the remainder?

  11. February 19, 2013 1:34 pm

    Is calculating n! complete in the sense that if one can calculate n! efficiently product of calculating any another random set of n integers is easy in the BSS model(word model)

    • February 19, 2013 1:37 pm

      Is calculating n! complete in the sense that if one can calculate n! efficiently product of calculating any another random set of n integers is easy in the BSS model(word model)?

  12. February 22, 2013 9:03 am

    Celebrities started getting into the phenomenon of
    this viral video:. As for Freeney, some teams may look to him to get a short-term solution in the 4-3 system.
    The launch of “Ralph” just before the vacations can be an especially wise move as
    more families have plenty of time to get together for activities.

Trackbacks

  1. Factoring Again: No Joking « Gödel’s Lost Letter and P=NP
  2. Papadimitriou and RCT « Gödel’s Lost Letter and P=NP
  3. Sunday Questions - The Quantum Pontiff

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 1,536 other followers