数论与密码学基础

数论研究整数及其结构。它也是许多密码系统的数学基础，尤其是模运算、素数和最大公因数。

整除性与模运算

若存在整数 $k$ 使得 $b=ak$，就写作 $a\mid b$。整数除法可以表示为

$$a=qm+r, \qquad 0\le r<m,$$

其中 $r$ 是余数。模同余满足

$$a\equiv b\pmod m \quad\Longleftrightarrow\quad m\mid(a-b)$$

算法与定理

欧几里得算法可以高效求最大公因数。扩展欧几里得算法还给出 Bézout 恒等式，因此能帮助求模逆和解线性同余方程。

中国剩余定理处理模数两两互质的同余方程组。费马小定理则说明，当 $p$ 为素数且 $p\nmid a$ 时，

$$a^{p-1}\equiv1\pmod p$$

快速模幂算法通过平方与取模，把指数运算的复杂度从线性规模降到对数规模。它是 RSA 等密码算法中的重要工具。

英文正文包含算法伪代码和同余方程练习，后续会把算法块改成博客的 pseudocode 格式，并检查每个复杂度结论。