Roedy Green <(E-Mail Removed)> wrote:

(snip on BigInteger, powers, and roots)

> What are the bounds on z and n?

> Here are some noodlings of an idea:

> z ^ 6

> prime factors of 6 are 2 and 3.

> so compute this as (z * z) ^3
Well, there is a standard method, that traces back to the

Chinese Remainder Theorem and works off the binary representation.

http://en.wikipedia.org/wiki/Binary_exponentiation
In some cases it isn't quite as good as factoring the power, but

mostly close enough.

> e.g. 2^6 = 64

> ( 2 * 2 ) ^ 3 = 4 * 4 * 4 = 64
-- glen