Question

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?

Answer 1

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.