# 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
answer = ''

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

answer += str(fastModular(i)) + ','

end = time.process_time() # Operation timestamp
param = {'ans':answer[:-1]}

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

{"is_success": true, "message": "please visit http://2**.207.12.156:9012/context/eb63fffd85c01a0a5d8f3cadea18cf56"}

>>>

### Run directly to get the next link answer !!

# 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 .

## Fast power modules of large numbers Python More articles on Implementation

- codeforces magic five －－ Fast power module
Topic link :http://codeforces.com/contest/327/problem/C First, calculate the value in a period , Save in ans Inside , Is the usual fast power module m practice ． Then you have to calculate a formula , Such as the k ...

- Fast power module n operation
Exponentiation in modular operation , such as 5^596 mod 1234, Of course , Direct use of the cycle of violence is also possible , See a fast modular exponentiation algorithm in the book The general idea is ,a^b mod n , First the b Convert to binary , Then start at the top ( Highest one ...

- URAL 1141. RSA Attack（ Euler theorem + Extended Euclid + Fast power module ）
Topic link The question : Here you are. n,e,c, And know me ≡ c (mod n), and n = p*q,pq All are prime numbers . Ideas : This question really matches the title , It's a RSA Algorithm , At present, the most important encryption algorithm on earth .RSA count ...

- hdu 2462( Euler theorem + High precision and fast power module )
The Luckiest number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe ...

- 2014 The first of many schools I topic || HDU 4869 Turn the pokers（ Fermat's small Theorem + Fast power module ）
Topic link The question : m card , It can be translated n Time , Every time I turn xi card , Ask how many forms you can get in the end . Ideas :0 Defined as the opposite ,1 Defined as positive ,( At first it was anti ), For each flop , We define two boundaries lb,rb, Represents each time 1 least ...

- hdu 1852( Fast power module + The formula for taking modulus when there is division )
Beijing 2008 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)Tota ...

- 2019 Nanchang invitational tournament C. Angry FFF Party Fast exponentiation of large number matrices + Classification of discussion
Topic link https://nanti.jisuanke.com/t/38222 The question : Defined function : $$F(n)=\left\{\begin{aligned}1, \quad n=1,2 \\F(n- ...

- [ primary ]sdut2605 A^X mod P Shandong Province, the fourth ACM Provincial competition （ The meter , Fast power module idea , Hash ）
This article from the :http://blog.csdn.net/svitter The question : f(x) = K, x = 1 f(x) = (a*f(x-1) + b)%m , x > 1 Find out ( A^(f(1) ...

- Fast power module m Algorithm
Here are three numbers ,a,b,m seek a^b%m Value . If b Too big , Using the ordinary fast power will timeout . So will b=2^0*b0+2^1*b+b1...... then , You know how to do it by using the knowledge of junior middle school . continue , Code up . #inc ...

- hdu 4602 Fast power module of recursive relation matrix
Partition Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total S ...

## Random recommendation

- Study with me python, Basic concepts （life is short ,we need python）
author :tobecrazy Source :http://www.cnblogs.com/tobecrazy Welcome to reprint , Reprint please indicate the source .thank you! Basic concepts : Constant : Constant names are all uppercase , Such as PI Variable : ...

- Network | UDP checksum
1. The checksum ICMP,IP,UDP,TCP It's all in the header checksum( Inspection and ) Field .IP The check sum in the header checks only the header :ICMP.IGMP.TCP and UDP Checksums in headers check headers and data . UDP and TCP ...

- 【Selenium】1. Introduce Selenium
This article is for study and communication , No commercial use , No profit . It's all my own translation to urge me to study . Poor translation , Forgive me . originate :http://www.guru99.com/introduction-to-selenium ...

- android Life cycle of
1. Running state : When an activity is at the top of the stack , At this time, the activity is active , The system is unwilling to recycle active , Will affect the user experience . 2. Pause state : When an activity is no longer at the top of the stack , But still visible , This is the pause state . On hold ...

- 【 Basics 】Asp.Net operation Cookie summary
One . What is? Cookie? Cookie Is a small amount of data stored in the text file of the client file system or in the memory of the client browser dialog . It's mainly used to track data settings , for example : When we want to visit a website page , When a user requests a web page , Applications may ...

- [ Reprint ] Dubbo Architecture design details
Reprinted from http://shiyanjun.cn/archives/325.html Dubbo yes Alibaba Open source distributed service framework , Its biggest characteristic is to construct in a hierarchical way , In this way, the layers can be decoupled ...

- node.js Advanced topics
< h3>notes_ control flow //forloopi.js var fs = require('fs'); var files = ['a.txt', 'b.txt', 'c.txt']; ...

- php in heredoc And nowdoc How to use
One .heredoc Structure and usage Heredoc Structure is like a double quote string without double quotes , That is to say in heredoc A single quotation mark in a structure does not need to be escaped . The variables in its structure will be replaced , But in heredoc The structure contains complex ...

- MySQL series --1. Install, uninstall and user rights management
MySQL install 1.Ubuntu18 Lower installation MySQL sudo apt-get install mysql-server MySQL The version is 5.7.25 2. Sign in MySQL use mysql-serve ...

- Linux-- Master slave copy
One . mysql+centos7 mariadb mariadb It's actually with mysql It's the same , It's just that centos7 It's called mariadb, Mainly because mysql After being acquired by Oracle , There may be a risk of closing the source ...