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:
# https://asecuritysite.com/encryption/modarith?Length=10 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)