Ask Your Question

Revision history [back]

I dont know how the "power" algorithm is implemented in sage. But you can use the binary method for power (or repeated squaring method). It goes like this:

To compute a^n, write down binary representation of n say

n = \sum_{i=1}^d a_i 2^i.

Then if a_i = 1, then square, else (i.e. a_i=0) do nothing.

Here is the algorithm:

If a_0 = 0
    set c = 1
    set c = a
set b_0 = a
For each i in 1..d (Note: d = no of digits in bin. rep. of n)
    b_i = b_{i-1}^2
    If a_i == 1
        c = c \cdot b_i
        c = c

This algorithm comes very handy when you want to compute a^n(mod m). I hope this will help you to get rid of these limitation on index.

-- VInay