[Back] In cryptography, such as in the RSA, Diffie Hellman and Discrete Logarithm methods, we often use the operation of \(a^p \pmod N\). Unfortunately \(a^p\) can be extremely large and difficult to compute. So in this example we use a faster algorithm where we significantly reduce the number and complexity of the operations:

## Fast Powering Algorithm |

## Method

In this method we simplify \(a^p \pmod N\). First we take our \(p\) value, and define it in powers of 2. For example with a decimal value of 218 (binary: 11011010)we get:

\(218 = 2^{1} + 2^{3} + 2^{4}+ 2^{6}+2^{7} \)

Thus:

\(a^{218} = a^{2^{1} + 2^{3} + 2^{4}+ 2^{6}+2^{7}} \pmod N \)

and, because of the rules of logarithms, this is eqivalent to:

\(a^{218} = a^{2^{1}} a^{2^{3}} a^{2^{4}} a^{2^{6}} a^{2^{7}} \pmod N \)

In this way we can double our power value each time and simplify by taking the mod operation each time.

For \(3^{218} \pmod{1000}\) we get:

\(3^{218} \pmod{1000} = 9 \times 561 \times 721 \times 281 \times 961 \pmod{1000}\)

and which is equal to \(489 \pmod{1000}\).

Here is the sample code:

a = 3 power = 218 N=1000 binary = [int(x) for x in list('{0:0b}'.format(power))] binary.reverse() print "a:\t",a print "p:\t",power print "N:\t",N print "Binary (in reverse) of power:",binary aval=a running=1 print "\nMultipliers:", for val in binary: if (val==1): val=(aval) % N print val, running = (running * val) % N aval=(aval ** 2) print print "Result:\t",running print "\nLong handed calculation to check" result = pow(a,power,N) print "Result:\t",result