Let's consider a silly-looking question first. Consider Z/pZ. Say I am allowed the two operations x->x+1 and x->2*x. Then, starting from 0, I can express every given element y of Z/pZ in O(log p) steps; moreover, I can figure out how to do it in time O(log p).

The answer is trivial: just lift y to an integer, and express it in base 2.

Now, what happens if we consider x->r*x instead of x->2*x?

(Assume that r has order at least >> log p, as otherwise things don't work.)

That is: can one express every given element y of Z/pZ in O(log p) steps by starting from 0 and using the operations x->x+1 and x->r*x? If so, can one figure out how to express such an element in that way in O(log p) (or O((log p)^c)) steps?

  • $\begingroup$ This looks like a case for the sum-product theorem planetmath.org/encyclopedia/SumProductTheorem.html , but I can't see how to apply it. $\endgroup$ – David E Speyer Jun 1 '10 at 17:26
  • $\begingroup$ He assumes the order of r is $>> \log p$. $\endgroup$ – David E Speyer Jun 1 '10 at 17:53
  • $\begingroup$ The sum-product theorem can't tell you how to express the element y, as far as I know. $\endgroup$ – H A Helfgott Jun 1 '10 at 19:58
  • $\begingroup$ The sum-product theorem would, however, yield a non-constructive solution if only we were allowed the operations (a) (x,y)->x+y, (b) x->r*x. $\endgroup$ – H A Helfgott Jun 1 '10 at 20:06
  • 1
    $\begingroup$ I agree - I don't even see how to get existence with the bound $O(\log ^C p)$ at the moment.. $\endgroup$ – Ben Green Jun 1 '10 at 20:52

Let $r$ be the "base" and $x$ the number to represent.

Let $m = \log_{2} (p) + \epsilon$. Construct the matrix $L$: $$\begin{pmatrix} x & \lambda & 0 & & ... & & 0 \\\\ 1 & 0 & \lambda & & & & 0 \\\\ \bar{r} & & & \lambda & & & \\\\ ... & & & & & & \\\\ \bar{r^m} & & & & & & \lambda \\\\ p & & & & & & 0 \end{pmatrix}$$ where $\bar{r^i}$ is $(r^i \mod p)$. Given a representation: $$x = \sum_{i = 0}^{m} a_i r^i (\mod p)$$ or more precisely: $$x = \sum_{i = 0}^{m} a_i \bar{r^i} - tp$$ where $a_i \in \{0,1\}$, we multiply the matrix from the left by the row: $$\left( \begin{array}{ccc} 1 & -a_0 & -a_1 & ... & -a_m & t \end{array} \right)$$ and get the short row: $$\left( \begin{array}{ccc} 0 & \lambda & -a_0 \lambda & -a_1 \lambda & ... & -a_m \lambda \end{array} \right)$$ since we expect the number of non zero $a_i$'s to be around $\log_2(p)/2$, we expect the norm of this row to be: $$\sqrt{\lambda^2 \sum_{i = 0}^{m} a_i^2} \sim \lambda \sqrt{\log_2(p)/2}$$ Note that: $$|\det(L)|^{1/(m+3)} = (p \lambda^{m+2})^{1/(m+3)}$$ While we want to keep the row short, we want to make other rows long. So we choose: $$\lambda \sim p \sqrt{\log_2(p)/2}$$

Going the other way around, applying the LLL algorithm to $L$, for a few small $\epsilon$, should produce a representation.

This algorithm is heuristic and I am not sure how to prove anything stronger. Try looking for papers on the knapsack problem, since it is quite similar.

| cite | improve this answer | |
  • $\begingroup$ I fail to see how this is a probabilistic solution, as opposed to just a heuristic. I may be missing something. (Also, how do you do LLL modulo p?) A probabilistic solution - in the sense of a probabilistic algorithm that would find the solution quickly with probability 1-o(1) for all or almost all elements y - would be very interesting indeed. $\endgroup$ – H A Helfgott Jun 2 '10 at 16:23
  • $\begingroup$ Aha - this looks interesting now. What we have is a knapsack problem where the (absolute values of the) coefficients have to add up to O(log p) and the linear combination must be exactly y. (If this is formulated over the integers, then, as you have pointed out, we can do this simply by using the basis 1,r,r^2,...,r^m,p.) This is in general an NP-complete problem, if memory serves me well. The question is whether the fact that our numbers are powers of r helps us any. $\endgroup$ – H A Helfgott Jun 2 '10 at 23:47
  • $\begingroup$ @Helfgott: Maybe. Would be nice. But I wouldn't put money on it. $\endgroup$ – Dror Speiser Jun 3 '10 at 5:37
  • $\begingroup$ It's difficult to see how to make anything out of this, really. Do you think that, say, the methods out there for breaking certain specific knapsack-based cryptographic algorithms could be of any help? $\endgroup$ – H A Helfgott Jun 7 '10 at 10:59
  • $\begingroup$ Algorithmically my answer is pretty sound. I would bet that it does solve many instances (I refrain from saying most since I don't really know). As for knapsack, I only know of the problem and its similarity, nothing on actual solutions. $\endgroup$ – Dror Speiser Jun 7 '10 at 19:42

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.