一、實驗要求與目的

學習快速模冪運算、擴展歐幾里得、中國剩余定理的算法思想以及代碼實現。

二、實驗內容與步驟記錄（只記錄關鍵步驟與結果，可截圖，但注意排版與圖片大小）

1.快速模冪運算的設計思路

快速模冪運算的核心思想是利用二進制表示和平方乘法來減少乘法運算的次數。具體步驟如下：將指數 b 表示為二進制形式。例如，b=13 的二進制表示為 1101。

?

通過這種表示，可以將冪運算分解為若干次平方和乘法。

從最低位開始逐位處理指數的二進制表示：如果當前位是 1，將當前的 a 乘到結果中。不管當前位是 0 還是 1，都將 a 平方（即 a=a^2modm），并右移一位（相當于除以 2）。在每一步中，都對結果和中間值取模 m，以避免數值過大導致溢出。使用一個循環來處理指數的每一位。循環條件是 b>0，每次循環都將 b 右移一位，直到 b 為 0。

2.擴展歐幾里得算法的設計思路：

擴展歐幾里得算法是基于經典的歐幾里得算法（輾轉相除法）進行擴展的。歐幾里得算法用于計算兩個整數 a 和 b 的最大公約數（gcd(a,b)），其核心思想是利用遞歸關系： gcd(a,b)=gcd(b,a mod b) 直到 a mod b=0，此時 b 即為最大公約數。目標是找到整數 x 和 y，使得： ax+by=gcd(a,b) 這實際上是將最大公約數表示為 a 和 b 的線性組合。算法通過遞歸的方式逐步求解 x 和 y。

假設已知： gcd(b,a mod b)=b?x1?+(a modb)?y1?。根據歐幾里得算法的遞歸關系，可以推導出：gcd(a,b)=gcd(b,a mod b)。因此： ax+by=b?x1?+(a mod b)?y1?。進一步展開 a mod b=a?b??b/a??，可以得到： ax+by=b?x1?+(a?b??b/a??)?y1?，整理后得到： x=y1? y=x1???b/a???y1。當 a=0 時，遞歸終止，此時： gcd(0,b)=b 對應的線性組合為： 0?x+b?y=b 因此，x=0，y=1。

通過遞歸調用擴展歐幾里得算法，逐步求解 x 和 y，直到找到滿足 ax+by=gcd(a,b) 的整數解。如果 gcd(a,b)=1，則找到了滿足 ax+by=1 的解。結果如下圖：

3.中國剩余定理設計思路：

首先計算所有模數（除數）的乘積 M，即 M=∏i?divisor[i]。這是中國剩余定理的關鍵基礎，因為最終的解將在這個范圍內。

對于每個同余方程 x≡remainder[i]?(mod?divisor[i])，計算 Mi?=M/divisor[i]，即 M 除以當前模數的商。然后使用 gmpy2.invert 求 Mi? 在模 divisor[i] 下的逆元 k。根據中國剩余定理的構造方法，將每個同余方程的解表示為 remainder[i]×k×Mi?，并將所有這些項相加，得到一個可能的解 n。

最終的解 n 可能大于 M，因此通過 nmodM 取最小非負解 nmin?。返回 nmin?，即滿足所有同余方程的最小非負整數解。

三、源代碼記錄

快速模冪運算

def fast_modular_exponentiation(a, b, m):result = 1 base = a % m  while b > 0:if b % 2 == 1:  result = (result * base) % mbase = (base * base) % m  # 將 base 平方并模 mb //= 2  # 將指數 b 右移一位（相當于除以 2）return resulta = 3
b = 13
m = 17
result = fast_modular_exponentiation(a, b, m)
print(f"{a}^{b} mod {m} = {result}")

擴展歐幾里得算法

def extended_gcd(a, b):if a == 0:return (0, 1, b)else:x1, y1, gcd = extended_gcd(b % a, a)x = y1 - (b // a) * x1y = x1return (x, y, gcd)# 用戶手動輸入 a 和 b
a = int(input("請輸入整數a: "))
b = int(input("請輸入整數b: "))# 使用函數求解 ax + by = gcd(a, b)
x, y, gcd = extended_gcd(a, b)if gcd == 1:print(f"找到 x = {x}, y = {y} 使得 {a}x + {b}y = 1")
else:print(f"沒有整數解，因為 gcd({a}, {b}) = {gcd} 不等于 1")

中國剩余定理

import gmpy2
divisor=[3,5,7]
remainder=[2,3,2]def CRT(divisor, remainder):mul = 1for d in divisor:mul *= d  # 計算除數列中所有元素的乘積n = 0for i in range(len(divisor)):k = gmpy2.invert(mul // divisor[i], divisor[i])n += remainder[i] * k * (mul // divisor[i])n_min = n % mulreturn n_min# 調用函數并打印結果
result = CRT(divisor, remainder)
print("The smallest solution is:", result)

四、實驗思考

求兩個數的最大公因數是否還有其他算法？

答：更相減損術是一種古老的求最大公因數的方法，其核心思想是通過反復相減來逐步減小兩個數的大小，直到它們相等，此時的值即為最大公因數。具體操作是：每次用較大的數減去較小的數，然后用得到的差替換原來的較大數，繼續進行相減操作，直到兩個數相等為止。這種方法簡單直觀，無需復雜的數學運算，僅通過減法即可實現，特別適合于手工計算或在不支持除法運算的環境中使用。

二進制GCD算法，也稱為Stein算法，是一種高效計算最大公因數的方法，它通過位運算和減法操作來逐步簡化問題。算法的核心思想是利用二進制的特性，首先判斷兩個數是否都是偶數，如果是，則同時除以2并記錄下除的次數；接著通過減法和位移操作逐步減小兩個數的差距，直到它們相等，此時的值乘以之前記錄的除2的次數即為最大公因數。這種方法避免了復雜的除法運算，僅使用位移和減法，特別適合在計算機中實現，因為它充分利用了計算機對二進制運算的高效處理能力。

此外還有一些其他的方法，如利用Fibonacci數列的性質、利用同余關系等，但這些方法通常只在特定情況下使用，或者作為理論研究的工具。