16
$\begingroup$

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$)?
$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – mikero May 2 '12 at 19:30
  • 3
    $\begingroup$ 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$). $\endgroup$ – Sasho Nikolov May 2 '12 at 19:33
  • $\begingroup$ @mikero, SashoNikolov, you both are correct, my apologies. I have edited my question. $\endgroup$ – user834 May 2 '12 at 19:42
  • 1
    $\begingroup$ note that "polynomial time algorithm" usually means a uniform algorithm. Lipton's post only asserts the existence of a polysize circuit family for factoring. $\endgroup$ – Sasho Nikolov May 2 '12 at 19:44
  • 1
    $\begingroup$ 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. $\endgroup$ – Gopi May 3 '12 at 12:55
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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})!$ $\endgroup$ – user834 May 6 '12 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.