Navigating $\mathbb{Z}/p\mathbb{Z}$

Question

$\newcommand{\Z}{\mathbb{Z}}$Let's consider a silly-looking question first. Consider $\Z/p\Z$. Say I am allowed the two operations $x\mapsto x+1$ and $x\mapsto 2x$. Then, starting from $0$, I can express every given element $y$ of $\Z/p\Z$ 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\mapsto rx$ instead of $x\mapsto 2x$?

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

That is: can one express every given element $y$ of $\Z/p\Z$ in $O(\log p)$ steps by starting from 0 and using the operations $x\mapsto x+1$ and $x\mapsto rx$? 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.