Lecture 3：数论基础¶

学习目标¶

完成本讲后，应当能够：

若存在整数 $m$ 使得 $a=mb$，则称 $b$ 整除 $a$，记作 $b\mid a$。若 $n\mid(a-b)$，则 $a$ 与 $b$ 模 $n$ 同余，记作：

\[ a\equiv b\pmod n \]

对正整数 $n$，整数 $a$ 除以 $n$ 可写为 $a=qn+r$，其中 $0\le r<n$；$r$ 是余数，也就是 $a\bmod n$。例如 $-12\bmod 7=2$，因为 $-12=(-2)\cdot7+2$。

加、减、乘都可以在计算过程中随时取模：

\[ (a+b)\bmod n=((a\bmod n)+(b\bmod n))\bmod n \]

乘法同理。提前约化数值可以显著降低后续计算量。

素数只有 $\pm1$ 和自身作为因数。每个大于 1 的整数都能唯一分解为素数幂的乘积。密码学会利用大整数分解困难这一特点，但求最大公因数不需要先分解因数。

$a$ 与 $b$ 的最大公因数记为 $\gcd(a,b)$。若 $\gcd(a,b)=1$，则二者互素（relatively prime）。欧几里得算法反复使用：

\[ \gcd(a,b)=\gcd(b,a\bmod b) \]

直到余数为 0，最后一个非零余数就是最大公因数。例：

\[ 999=1\cdot911+88,\quad 911=10\cdot88+31,\quad 88=2\cdot31+26, $$ $$ 31=1\cdot26+5,\quad 26=5\cdot5+1,\quad 5=5\cdot1+0 \]

因此 $\gcd(911,999)=1$。该算法避免了对大整数做质因数分解。

若存在整数 $x$ 使得 $ax\equiv1\pmod n$，则 $x$ 是 $a$ 模 $n$ 的乘法逆元（modular inverse），记作 $a^{-1}\bmod n$。模逆存在当且仅当 $\gcd(a,n)=1$。

扩展欧几里得算法求出整数 $x,y$，满足贝祖等式：

\[ ax+ny=\gcd(a,n) \]

当最大公因数为 1 时，对等式两边模 $n$ 化简可得 $ax\equiv1\pmod n$，所以 $x$ 即为模逆。例：扩展欧几里得算法给出

\[ 1=-193\cdot911+176\cdot999 \]

故 $911^{-1}\equiv-193\equiv806\pmod{999}$。验证时计算 $911\cdot806\bmod999=1$。

欧拉函数（Euler's totient function）$\varphi(n)$ 统计 $1$ 到 $n$ 中与 $n$ 互素的整数个数。若 $p$ 为素数，则：

\[ \varphi(p^e)=p^{e-1}(p-1) \]

若 $m,n$ 互素，则 $\varphi(mn)=\varphi(m)\varphi(n)$。因此若 $n=\prod_i p_i^{e_i}$，则：

\[ \varphi(n)=\prod_i p_i^{e_i-1}(p_i-1) \]

费马小定理（Fermat's little theorem）：若 $p$ 为素数且 $p\nmid a$，则 $a^{p-1}\equiv1\pmod p$。其推广欧拉定理（Euler's theorem）为：若 $\gcd(a,n)=1$，则：

\[ a^{\varphi(n)}\equiv1\pmod n \]

这些定理用于化简幂指数，也是 RSA 正确性推导的基础之一。

直接计算 $a^e$ 需要约 $e$ 次乘法，指数很大时不可行。平方-乘算法（square-and-multiply）将指数写成二进制或 2 的幂之和，逐次平方并只乘入指数二进制位为 1 的项，时间复杂度为 $O(\log e)$。

例：计算 $11^{15}\bmod13$。因为 $15=8+4+2+1$，且

\[ 11^2\equiv4,\quad11^4\equiv3,\quad11^8\equiv9\pmod{13}, \]

所以 $11^{15}\equiv9\cdot3\cdot4\cdot11\equiv5\pmod{13}$。每一步都先约化模数，避免生成巨大整数。

数学问题的困难性并不能自动保证软件实现安全。运行平台可能通过执行时间、功耗、电磁辐射或声音泄露有关密钥的信息，这类泄露称为侧信道（side channel）。平方-乘算法若依据指数位决定是否执行额外乘法，运行时间也可能泄露指数信息；实际实现需考虑恒定时间等防护。