## [Python,Algorithms] Fast Modular exponentiation script

If we want to know the last ten digits of number an – we have to evaluate expression an mod 1010. Using brute force approach, we have to do O(n) ( If you don’t understand big „O” notation, visit: Big O notation – it’s VERY important) multiplications and modulo divisions. When n is greater than 109, it will take a lot of time. Fortunately, we can use more „mathematical” approach, which has O(log n) complexity.
Firstly, we have to notice, that:
(1) a2c mod r = (ac)2 mod r
(2) a2c+1 mod r = a*(ac)2 mod r

```#! /usr/bin/env python # Author: Wojtek Jamrozy (www.wojtekrj.net)   def modexp(a, n, m): bits = [] while n: bits.append(n%2) n /= 2 solution = 1 bits.reverse() for x in bits: solution = (solution*solution)%m if x: solution = (solution*a)%m return solution   print modexp(2,34, pow(10,10)) print modexp(2,pow(10,20), pow(10,10))```

output:

```7179869184 1787109376```

Function pow(a,b) is Python’s function, which computes ab
Function modexp(a, n, m) computes an mod m. Here is example, which shows running of the function a=2, n=34, m=1010
Firstly, we want to have bits of binary notation of n in list bits.
Before reversion, bits have following content: [0, 1, 0, 0, 0, 1] (21 + 25 = 33)
After reversion of list: bits= [1, 0, 0, 0, 1, 0]
Bits of binary notation of n are in order from “bigger” powers to “lower” ones.
I will use (b) for binary notation of number: 33 = 100001(b)
At the beggining, solution = 20 mod 1010 = 1. Then, during execution of for loop, solution has following values: 21(b) mod 1010, 210(b) mod 1010, 2100(b) mod 1010, 21000(b) mod 1010, 210001(b) mod 1010 and finally 2100010(b) mod 1010.
Using (1) and (2) we can calcualte every solution’s value if we know previous one.
Loop for is executed for each element of bits. Bits size is log2n, so the complexity of whole alghorithm is O(log n)

expon.py (369 bytes, 927 hits)

This entry was posted in Algorithms, Python and tagged , , , . Bookmark the permalink.

### 3 Responses to [Python,Algorithms] Fast Modular exponentiation script

1. Eremeeff says:

Hi there,
Not enought information

Thank you
Eremeeff

2. AnnaHopn says:

Greatings,
Super post, Need to mark it on Digg

Thank you
AnnaHopn

3. Elcoj says:

Hello,
Super post, Need to mark it on Digg

Thank you
Elcoj