[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)

You can download code here:

  expon.py (369 bytes, 879 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

Leave a Reply

Your email address will not be published. Required fields are marked *