# 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
else
set c = a
set b_0 = a
For each i in 1..d (Note: d = no of digits in bin. rep. of n)
do
b_i = b_{i-1}^2
If a_i == 1
c = c \cdot b_i
else
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