16

While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post:

If, for every $n$, there exists a relation of the form $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$ where $m = poly(n)$, and each of the $a_k$, $b_k$ and $c_k$ are $poly(n)$ in bit length, then factoring has polynomial sized circuits.

In other words, the $(2^n)!$, which has an exponential number of bits, can potentially be represented efficiently.

I have a few questions:

  • Could someone provide a proof of the above relation, tell me the name and/or provide any references?
  • If I were to give you $n$, $m$ and each of the $a_k$, $b_k$ and $c_k$, could you provide me a polynomial time algorithm to check the validity of the relation (i.e. is it in $NP$)?
user834
  • 2,806
  • 21
  • 27
  • 4
    Doesn't that blog post actually claim the converse? That is, if equations of the above form $(2^n)! = \sum \cdots$ have solutions in general, then factoring has polynomial-sized circuits. – mikero May 02 '12 at 19:30
  • 3
    I think you actually wrote the converse of what Dick Lipton wrote. He says that if such an equation exists for every $n$, then factoring has polynomial size circuits. So the implication is that if factoring is non-uniformly hard (for infinitely many $n$) then equations of the above form do not exist (for infinitely many $n$). – Sasho Nikolov May 02 '12 at 19:33
  • @mikero, SashoNikolov, you both are correct, my apologies. I have edited my question. – user834 May 02 '12 at 19:42
  • 1
    note that "polynomial time algorithm" usually means a uniform algorithm. Lipton's post only asserts the existence of a polysize circuit family for factoring. – Sasho Nikolov May 02 '12 at 19:44
  • 1
    Note that in order for this property to be true, $a_k$, $b_k$ and $c_k$ should be $poly(n)$ in bit size /as stated on Lipton's blog/, and $poly(2^n)$ as integers. Your definition is not clear. – Gopi May 03 '12 at 12:55
  • @Gopi, of course you're right. I tried to make the wording a bit more clear and failed to state it correctly. This has been fixed. – user834 May 03 '12 at 17:32
  • One could imagine a test mod $p < 2^n$, where we know $(2^n)! = 0 \ (\mod p)$ and we can confirm that efficiently to the right. If we choose $p$ randomly, we can get a probability of the relation being correct, though this is nowhere near efficient enough. Maybe someone can use this as a starting point for a deterministic/efficient probabilistic test? – user834 May 04 '12 at 17:16
  • One can also choose primes, $q$, slightly larger than $2^n$ and use Wilson's to confirm $(2^n)!$ is what it should be mod $q$. – user834 May 07 '12 at 00:22

1 Answers1

8

I’ll comment on why a relation as in the question $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$ (for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can.

The first observation is that a relation as above (and more generally, the existence of poly-size arithmetic circuits for $(2^n)!$) gives a poly-size circuit for computing $(2^n)!\bmod x$ for $x$ given in binary: simply evaluate the sum modulo $x$, using exponentiation by repeated squaring.

Now, if we could compute $y!\bmod x$ for arbitrary $y$, we could factor $x$: using binary search, find the smallest $y$ such that $\gcd(x,y!)\ne1$ (which we can compute using $\gcd(x,(y!\bmod x))$). Then $y$ must be the smallest prime divisor of $x$.

If we only can do powers of $2$ for $y$, we can still try to compute $\gcd(x,(2^n)!)$ for every $n\le\log x$. One of these will be a nontrivial divisor of $x$, except for the unfortunate case when there is an $n$ such that $x$ is coprime to $(2^n)!$, and divides $(2^{n+1})!$. This is equivalent to saying that $x$ is square-free, and all its prime factors have the same bit-length. I don’t know what to do in this (rather important, cf. Blum integers) case.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
  • If the relation holds (for all $n$), then perhaps it also holds (with a different choice of $a_k$, $b_k$ and $c_k$) when one replaces $2$ with another (small) prime, $p$. One could presumably search until a $p$ is found such that $x$ is coprime to $(p^n)!$ and not $(p^{n+1})!$ – user834 May 06 '12 at 06:24