Skip to content

Instantly share code, notes, and snippets.

@komasaru
Created January 8, 2018 06:06
Show Gist options
  • Save komasaru/590612f2a7a7060a0d5501b343051d9f to your computer and use it in GitHub Desktop.
Save komasaru/590612f2a7a7060a0d5501b343051d9f to your computer and use it in GitHub Desktop.
Python script to compute modular-exponentiation recursively.
#! /usr/local/bin/python3.6
"""
Modular Exponentiation (recursive)
"""
import sys
import traceback
class ModularExponentiation:
def comp_mod_exp(self, b, e, m):
""" Computation of modular exponentiation
:param int b: base
:param int e: exponent
:param int m: modulus
:return int me: modular expornentiation
"""
try:
if e == 0:
return 1
ans = self.comp_mod_exp(b, e // 2, m)
ans = (ans * ans) % m
if e % 2 == 1:
ans = (ans * b) % m
return ans
except Exception as e:
raise
if __name__ == '__main__':
# me = b^e mod m
b, e, m = 12345, 6789, 4567
try:
obj = ModularExponentiation()
me = obj.comp_mod_exp(b, e, m)
print("{}^{} mod {} = {}".format(b, e, m, me))
except Exception as e:
traceback.print_exc()
sys.exit(1)
@amansk2050
Copy link

what if b is negative ??

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment