# Fast power modulus Python implementation of large numbers

2021-08-23 01:18:47 Dba_ sys

# requirement

Modular exponentiation algorithm , Through the verification of the server .

visit `http://2**.207.12.156:9012/step_04` The server will give you 10 A question , Each question contains three numbers (a,b,c), Please give me `a^b%c` Value . The return value is written to the field ans,10 Use a comma for each number , separate , Submitted to the `http://2**.207.12.156:9012/step_04`

Tips ： Note that commas must be English commas .

``````{"is_success": true, "questions": "[[1336, 9084, 350830992845], [450394869827, 717234262, 9791], [2136, 938408201856, 612752924963], [6026, 754904536976, 5916], [787296602, 305437915, 661501280], [864745305, 6963, 484799723855], [4165, 110707859589, 102613824], [398189032, 723455558974, 794842765789], [974657695, 138141973218, 760159826372], [9034, 7765, 437523243]]"}
``````

# Python Program realization

``````import requests as re
import time
def fastModular(x): # Fast power implementation
"""x[0] = base """
"""x[1] = power"""
"""x[2] = modulus"""
result = 1
while(x[1] > 0):
if(x[1] & 1): #  Bit operations speed up the judgment of parity
result = result * x[0] % x[2]
x[1] = int(x[1]/2)
x[0] = x[0] * x[0] % x[2]
return result

getHtml = re.get("http://2**.207.12.156:9012/step_04/")

start = time.process_time()					#  Operation timestamp
for i in eval(getHtml.json()['questions']): #  Will have '[]' The string of symbols is converted into a list
end = time.process_time()					#  Operation timestamp

print(f"Runing time is { end- start} sec")
getHtml = re.get("http://2**.207.12.156:9012/step_04/",params=param)
print(getHtml.text)

>>>
runing time is 0.0 s
>>>
``````

# How can we calculate A^B mod C quickly if B is a power of 2 ?

Using modular multiplication rules:

i.e. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C

`a^b % c = (a % c)^b % c`

`(a * b * c) % d = {(a % d) * (c % d) * (b % d)} % d`

`a^5 % c = (a % c)^5 % c = {(a % c) * (a % c) * (a % c) * (a % c) * (a % c)} % c`

One algorithm is to use `{(a % c) * (a % c) * (a % c) * (a % c) * (a % c)} % c`, Using the normal power method , Iterate variables in .`result = result * a % c` This will iterate 5 Time , That is to say Power operation time complexity .

notes ： Iterative operations `{（result % c） * （a % c）} % c == result * a % c`

Another is to use the relationship between base and power , Divide the power by 2, Square times the base . This number remains the same . Plus the use of lemma will be much more convenient .log(power) Time complexity of .

4^20 mod 11 = 1099511627776 % 11 =1

= 16^10 mod 11 = (16 mod 11)^10 = 5 ^ 10 mod 11

= 25 ^ 5 mod 11 = (25 mod 11)^5 = 3 ^ 5 mod 11

9 ^ 2.5 = 9 ^ 2 * 9^(1/2) = 9 ^ 2 * 3 mod 11

The above one needs square 3 change 9 Reopen 2 Power 9 change 3, Get the results . After simplification, we find that this method can be reduced to , When the power becomes odd , Let's subtract one from the odd number , Divide by two , Base squared , And multiply by the base Calculate . The result is the same . It's easier to think so . It is also convenient for program implementation

3 ^ 5 mod 11 = 9 ^ 2 * 3 mod 11 ( 5-1=4 ,4/2=2 )

= (9 mod 11)^2 mod 11 = 2 ^ 2 *3 mod 11

= 4 ^ 1 * 3 mod 11 = (4 mod 11)^1 * 3 mod 11 = 7^1 * 3 mod 11

= 49^0 *7 *3 mod 11 =21 % 11

=1

Odd minus one The part divided into even powers will eventually reach 0 Time , The result is 1. The power of the first power is the key factor to determine the result .