FilesExpand file tree

 Write-for-current-Python

/

binary_exp_mod.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

28 lines (23 loc) · 661 Bytes

 Write-for-current-Python

/

binary_exp_mod.py

Copy path

Top

File metadata and controls

• Code
• Blame

28 lines (23 loc) · 661 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

def bin_exp_mod(a, n, b):

"""

>>> bin_exp_mod(3, 4, 5)

1

>>> bin_exp_mod(7, 13, 10)

7

"""

# mod b

assert not (b == 0), "This cannot accept modulo that is == 0"

if n == 0:

return 1

if n % 2 == 1:

return (bin_exp_mod(a, n - 1, b) * a) % b

r = bin_exp_mod(a, n / 2, b)

return (r * r) % b

if __name__ == "__main__":

try:

BASE = int(input("Enter Base : ").strip())

POWER = int(input("Enter Power : ").strip())

MODULO = int(input("Enter Modulo : ").strip())

except ValueError:

print("Invalid literal for integer")

print(bin_exp_mod(BASE, POWER, MODULO))