第3章 進階數論#

第2章的工具讓我們能測質數、求 gcd、做模冪；本章把這些積木組裝成更強大的機器。3.1 節的中國剩餘定理教我們如何把「一個大數的餘數問題」拆成幾個互質模數下的小問題再合併——它誕生於一千八百年前的《孫子算經》，如今是 RSA-CRT 加速與多餘數算術的核心。3.2 節討論離散對數：模冪運算容易、反過來求指數卻極難，這種不對稱性正是 Diffie–Hellman 與 ElGamal 的安全基礎，我們也將實作 baby-step giant-step 演算法。3.3 節探索大數質因數分解：從試除與 Pollard 的 ρ 演算法一路談到現代密碼學賴以為生的「分解困難」假設，看懂 RSA 為什麼安全、又面臨哪些威脅。