Computing powers [of numbers]
The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity mt by performing about Log[t] multiplications and building up the sequence
FoldList[#12 m#2 &, 1, IntegerDigits[t, 2]]
(related to the Horner form for the base 2 representation of t). Given two numbers x and y their product can be computed in base k by (FromDigits does the carries)
FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k]
For numbers with n digits direct evaluation of the convolution would take about n2 steps. But FFT-related methods reduce this to about n Log[n] steps (see also page 1142). And this implies that to find a particular digit of mt in base k will take altogether about t Log[t]2 steps.
One might think that a more efficient approach would be to start with the trivial length t digit sequence for ct in base c, then to find a particular base k digit just by converting to base k. However, the straightforward method for converting a t-digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as
FixedPoint[Flatten[Map[If[# < k, #, With[{e = Ceiling[Log[k, #]/2]}, {Quotient[#, ke], With[{s = Mod[#, ke]}, If[s 0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] &, #]] &, {x}]
The pictures below show stages in the computation of 320 (a) by a power tree in base 2 and (b) by conversion from base 3. Both approaches seem to require about the same number of underlying steps. Note that even though one may only want to find a single digit in mt, I know of no way to do this without essentially computing all the other digits in mt as well.