Navigating Z/pZ 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?
 A: 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.
