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?