Fast Powering Algorithm

Let’s assume we want to compute a large power of a number \(g\), i.e. we want to compute \(g^a\) for some big number \(a\). A naive approach would be to perform \(a-1\) multiplications. By this would be rather slow if \(a\) has hundreds or even thousands of of digits. A more efficient approach is the following, also known as the fast powering algorithm:

First, write \(a\) as the sum of powers of two:

\[a = a_0\cdot 2^0 + a_1\cdot 2^1 + a_2\cdot 2^2 + \dots + a_n\cdot 2^n\]

Now, \(g^a\) can be written as

\[\begin{align} g^a & = g^{a_0 + a_1\cdot 2^1 + a_2\cdot 2^2 + \dots + a_n\cdot 2^n} \\[2ex] & = g^{a_0} \cdot g^{a_1\cdot 2^1} \cdot g^{a_2\cdot 2^2 } \cdot \ \ldots \ \cdot g^{a_n\cdot 2^n} \\[2ex] & = g^{a_0} \cdot \left(g^{2^1}\right)^{a_1} \cdot \left(g^{2^2 }\right)^{a_2} \cdot \left(g^{2^3 }\right)^{a_3} \cdot \ \ldots \ \cdot \left(g^{2^n}\right)^{a_n} \end{align}\]

The powers within the parentheses can be easily computed:

\[\begin{align} g^2 &= g \cdot g \\[2ex] g^{2^2} &= g^{2\cdot 2} = \left(g^2\right)^2 \\[2ex] g^{2^3} &= g^{2^2\cdot 2} = \left(g^{2^2}\right)^2 \\[2ex] g^{2^4} &= g^{2^3\cdot 2} = \left(g^{2^3}\right)^2 \\[2ex] &\vdots \end{align}\]

From this we can see that we get the power \(g^{2^i}\) by raising \(g^{2^{i-1}}\) (which we get from the previous step) to the power of 2. As \(a\) requires \(n=O(\log_2 a)\) bits, the fast powering algorithm requires only \(O(\log_2 a)\) steps.