Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
45 lines (36 sloc) 1.78 KB
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 15 10:22:47 2015
@author: Alejandro Alcalde (elbauldelprogramador.com)
"""
from timeit import time
def main():
a = 73208616291729490009973433121286344567434489939282793597607519000966996155360750368319793684412925463106458801305905417659505277658173580019690672647131149181691673085352991108383422899064111557676239886382393720679790707000007022943670027071869801952045077456667008417783362547455032994902700653449707460650861865827079710793628382710628215723590417499922623227328512330542136090646598393820931691345712444045913948265747291110928879288688808327471851465040466869820789521303662074003273766746823743
k = 643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390152
n = 643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153
#a, k, n = 50, 2361479148548741, 36780481
print str(a) + " times " + str(k) + " mod " + str(n) + " is " + str(powerModInt(a,k,n))
start_time = time.time()
print powerModInt(a,k,n)
elapsed_time = time.time() - start_time
print("%0.10f" % elapsed_time)
def powerModInt(a,k,n):
"""
@input a in Z_n and integers 0 <= k <= n
@outup a times k mod n
"""
b = 1
if k == 0:
return b
A = a
if 1 & k: # If the least significant bit is 1, a^1 = a
b = a
k = k >> 1
while k:
A = (A**2) % n
if 1 & k:
b = (b * A) % n
k = k >> 1
return b
if __name__ == '__main__':
main()