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$
8
  • 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, 2012 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$ May 2, 2012 at 19:33
  • $\begingroup$ @mikero, SashoNikolov, you both are correct, my apologies. I have edited my question. $\endgroup$
    – user834
    May 2, 2012 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$ May 2, 2012 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, 2012 at 12:55

1 Answer 1

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$
1
  • $\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, 2012 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.