同餘運算：數位時鐘

演算法背後的故事：循環的邏輯

想像妳有一個時鐘。如果現在是 10 點，妳等待了 4 個小時，現在是幾點？ 在普通數學中，$10 + 4 = 14$。但在時鐘上，它是 $2$ 點。

這就是 同餘運算 (Modular Arithmetic)，也被稱為「時鐘算術」。數字 12 就是這裡的 模 (Modulus)。每當妳達到 12，妳就會重置並重新開始。

這個系統的天才之處在於，它允許我們用有限的空間處理無限的序列。無論一個數字變得多大，如果妳對它取模 mod 100，它永遠會落在 0 到 99 之間。這就是「在邊界內行事」的藝術。

為什麼需要它？

• 哈希： 為了將巨大的用戶 ID 映射到小型陣列的索引中，我們使用 hash(ID) % array_size。
• 密碼學： 公鑰加密（如 RSA）完全建立在模冪運算之上。它就像一條單行道：計算「時鐘上的時間」很容易，但僅透過觀察指標來推算「過去了多少天」幾乎是不可能的。
• Diffie-Hellman 密鑰交換： 允許兩個人在公開渠道上透過在「模數時鐘」上「混合顏色」來達成秘密密鑰。
• 遊戲邏輯： 讓角色在螢幕邊緣循環出現：x = (x + speed) % screen_width。

演算法是如何「思考」的

同餘運算遵循她自己的平衡法則：

1. 加法： $(A + B) \pmod M = (A \pmod M + B \pmod M) \pmod M$
2. 乘法： $(A imes B) \pmod M = (A \pmod M imes B \pmod M) \pmod M$
3. 模逆元： 這是最難的部分。在模運算中，除以 $X$ 等同於乘以「$X$ 的逆元」。這是破解（或製造）密碼的核心。

工程決策：溢位保護

在程式設計中，我們經常需要計算巨大的和或積。

• 如果妳先計算 $(A imes B imes C)$ 再取模，中間結果可能會大到溢位 64 位元整數，導致得到垃圾數據。
• 專家提示： 在每一步都應用模運算。$(A imes B \pmod M) imes C \pmod M$。這能保持數值小巧且安全。

實作參考 (Python)

def modular_exponentiation(base, exp, mod):
    # 高效計算 (base^exp) % mod
    # 時間複雜度 O(log exp) —— 這是密碼學的核心
    res = 1
    base = base % mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

# 範例
# 計算 (5^117) % 19
# 普通計算器會因為數字太大而失效，但同餘運算能輕鬆處理
print(f"5^117 mod 19 的結果: {modular_exponentiation(5, 117, 19)}")
# Python 內建的 pow(base, exp, mod) 也經過了這種優化
print(f"原生 pow 結果: {pow(5, 117, 19)}")

小結

同餘運算教會我們：限制創造了結構。透過創造一個數字周而復始的循環世界，我們可以用有限管理無限。她提醒我們，在工程實踐中，有時候處理增長最強大的方法，就是明確在哪裡重置。