-
Notifications
You must be signed in to change notification settings - Fork 497
/
modular_exponential.py
37 lines (29 loc) · 863 Bytes
/
modular_exponential.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
"""
Modular Exponential
"""
def mod_exponent(base, power, mod):
"""
Modular exponential of a number
:param base : number which is going to be raised
:param power : power to which the number is raised
:param mod : number by modulo has to be performed
:return : number raised to power and modulo by mod [(base ^ power) % mod]
"""
res = 1 # Initialize result
base = base % mod # Update base if it is more than or equal mod_
while power > 0:
if power & 1: # if pow_ is odd multiply it with result
res = (res * base) % mod
power = power >> 1 # _pow must be even now
base = (base * base) % mod
return res
def main():
"""
Driver function
"""
base = 42
power = 58
mod = 69
print(mod_exponent(base, power, mod))
if __name__ == '__main__':
main()