整除与最大公约数

若整数 $a=bq$ 则称 $b$ 整除 $a$，记 $b\mid a$。两数公共的最大因子是最大公约数 $\gcd(a,b)$；$\gcd=1$ 时称二者互素。整除与互素是全部数论的起点。

同余

若 $n\mid(a-b)$，记
$a\equiv b\pmod{n}$
读作「$a$ 与 $b$ 模 $n$ 同余」。同余对加减乘封闭（可逐步取模），把大整数运算压缩到 ${0,1,\dots,n-1}$ 内——这正是密码学反复用到的「钟表算术」。

快速模幂

加密常需算 $a^k\bmod n$（$k$ 极大）。用平方–乘：把 $k$ 写成二进制，边平方边按位乘，复杂度仅 $O(\log k)$：
$a^{13}=a^{8}\cdot a^{4}\cdot a^{1}\quad(13=1101_2)$

例题

例 1　$7^{100}\bmod 13$：由 $7^{12}\equiv1$（费马小定理）得 $7^{100}=7^{96}\cdot7^4\equiv7^4=2401\equiv9\pmod{13}$。

例 2　判断 $\gcd(24,36)=12$，故 $24,36$ 不互素。

应用

模运算是 RSA、Diffie–Hellman、椭圆曲线密码的运算舞台；身份证、ISBN、银行卡号的校验码也用模运算检错。一切公钥密码的「易算难逆」都建立在模幂之上。