第 2 章 基礎數論演算法#

數論曾經被視為「最純粹、最無用」的數學，但自從 1977 年 RSA 公鑰密碼系統問世後，它成了網路安全的基石。本章介紹三組最基礎也最常用的數論演算法：質數的測試與篩選、最大公因數與擴展歐幾里得演算法、以及模冪運算與費馬小定理。

2.1 節教你如何有效率地找出所有質數——從逐個試除到埃拉托斯特尼篩法，再到只篩到 √n 的最佳化版本。2.2 節介紹有兩千多年歷史的歐幾里得輾轉相除法，以及它的強化版「擴展歐幾里得」：後者不只算出 gcd，還能找出 ax + by = gcd 的整數解，是解線性同餘方程與求模反元素的鑰匙。2.3 節講模冪運算（平方-乘法）與費馬小定理，這兩者合起來構成了密碼學中「快速計算 a^b mod m」與「概率性質數測試」的基礎。

本章的演算法有一個共同的甜美之處：程式碼都極短，卻蘊含深刻的數學。你會看到十行以內的函式，足以支撐起 RSA 加解密的核心。同時這些演算法的效率分析也特別乾淨——歐幾里得法只需 O(log min(a,b)) 次迭代，篩法是 O(n log log n)，模冪是 O(log b) 次乘法。學完本章，你就具備了閱讀第 3 章進階數論（中國剩餘定理、離散對數、質因數分解）的全部工具。