大數的快速冪模 Python實現

• 2021 年 8 月 20 日
• 筆記
• 演算法

要求

實現模冪演算法，通過伺服器的檢驗。

訪問//2**.207.12.156:9012/step_04伺服器會給你10個問題，每個問題包含三個數(a,b,c)，請給出a^b%c的值。返回值寫入欄位ans，10個數字用逗號,隔開，提交到//2**.207.12.156:9012/step_04

提示：注意逗號必須是英文逗號。

{"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程式實現

import requests as re
import time
def fastModular(x): #快速冪的實現
	"""x[0] = base """
	"""x[1] = power"""
	"""x[2] = modulus"""
	result = 1
	while(x[1] > 0):
		if(x[1] & 1): # 位運算加快判斷奇偶
			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("//2**.207.12.156:9012/step_04/")

start = time.process_time()					# 運算時間戳
for i in eval(getHtml.json()['questions']): # 將帶有'[]'符號的字元串轉換成列表
	answer += str(fastModular(i)) + ','
end = time.process_time()					# 運算時間戳

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

>>>
runing time is 0.0 s
{"is_success": true, "message": "please visit //2**.207.12.156:9012/context/eb63fffd85c01a0a5d8f3cadea18cf56"}
>>>

直接運行即可獲得下一步鏈接答案!!

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

一種演算法是利用{(a % c) * (a % c) * (a % c) * (a % c) * (a % c)} % c，利用正常求冪次的方法，將變數進去迭代。result = result * a % c這樣會迭代5次，也就是冪次的運算時間複雜度。

註：迭代運算{（result % c） * （a % c）} % c == result * a % c

還有一種就是利用底數和冪次的關係，將冪次除以2，底數平方倍。這個數還是不變的。再加上利用引理就會方便很多。log(power)的時間複雜度。

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

上面這個需要平方3變9 再開2次方 9變3，得到結果。簡化後我們發現這種方法可以歸結為，當冪次變成奇數的時候，我們將奇數減一，除以二，底數平方，並乘以底數 進行計算。結果是一樣的。這樣想更簡單。也方便程式實現

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

奇數減一分成偶數次冪那部分最終都會到0次，結果為1。而分出去的一次冪就是決定結果的關鍵因素。