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?

howto express the element y, as far as I know. – H A Helfgott Jun 1 '10 at 19:58existencewith the bound $O(\log ^C p)$ at the moment.. – Ben Green Jun 1 '10 at 20:52