密码学中需要知道的一些数论的知识备忘

密码学数论基础

整除性和带余除法

整除

• 整除 $\mid$、因子、真因子
• 传递性、同乘、线性组合

整数

• 带余除法（欧几里得除法 $a = qb +r$）
  • 进制表示

最大公因子

• $(a,0) = 0$
• $(a,b)=xa+yb$
• 求法：辗转相除法（Euclid算法）
  • 计算量 $O(lg^3a)$
  • 多个数的最大公因子求法：从原数组选取两个数，得到其最大公因子后加入到原数组中。重复操作直至数组中仅一个元素。

整数的唯一分解定理

• 素数、合数、互素
• 唯一分解定理：整数可唯一表示为若干素数的乘积
• 最小公倍数
  • 求法：$[a,b]=\frac{ab}{(a,b)}$

素数

• 素数有无穷多个
  • $\lim\limits_{x\rightarrow +\infty}\frac{\pi(x)}{x}=0$
• 特殊的素数
  • Mersenne 素数：形如 $2^p - 1$ 的素数
  • Fermat 素数：形如 $2^{2^n} - 1$ 的素数
    • $F_5$ 就不是素数
• 寻找素数：
  • Eratosthenes 筛法
  • 素性测试

同余式

同余

• $n\mid a-b \Leftrightarrow a \equiv b \pmod n$

中国剩余定理

• 求解同余方程组：中国剩余定理
  • 求解方程组：$x\equiv b_i \pmod m_i$
    • 计算：$m=\Pi m_i = m_iM_i$，$M_i'M_i\equiv 1\pmod m_i$
    • 则该方程有且仅有一个小于 $m$ 的解 $x\equiv \sum M_i'M_ib_i \pmod m$

剩余类环

• 剩余类：根据模 $m$ 的余数进行划分集合

  • 完全剩余系：对剩余类的每个集合选取一个代表元

• Euler 函数：与 $m$ 互素的剩余类个数，记为 $\varphi(m)$

  • Euler 定理：若 $(k,m) = 1$，则 $k^{\varphi(m)} \equiv 1\pmod m$
  • Fermat 小定理：若 $p$ 为素数，则对所有整数 $a$ 有 $a^p \equiv a \pmod p$
  • 缩系：对剩余类的每个集合选取一个与 $m$ 互素的代表元

• 快速模幂算法：“平方-乘”算法

同余方程

• 一次方程：$ax +b \equiv 0 \pmod m$ 有解 $\Leftrightarrow (a,b)\mid m$
• 高次方程：不规则，但是若模数 $m$ 可以素数分解为同余方程组
  • Wilson 定理：若 $p$ 为素数，则 $(p-1)!\equiv -1 \pmod p$

原根

• 阶：满足 $a^d\equiv 1 \pmod m$ 的最小正整数 $d$，记作 $\delta_m(a)$
• 原根：满足 $\delta_m(a) = \varphi(m)$ 的 $a$
  • 素数的原根总是存在，但是其他情况未必（原根存在定理）
  • 寻找原根：枚举原根并检验其正确性

二次剩余

Legendre 符号及 Euler 判别法

• 二次剩余：$(n,m)=1$，若 $x^2\equiv n \pmod m$ 有解，则 $n$ 称为模 $m$ 的二次剩余。否则称为二次非剩余
• Legendre 符号及 Euler 判别法：设 $p$ 为奇素数，$p \nmid n$，则

  $\left(\frac{a}{p}\right)=\pm 1 \equiv a^{\frac{p-1}{2}} \quad(\bmod p)$

  （$p\mid n$ 时取得 0 ）
• 推论：
  • $(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}$
  • $(\frac{2}{p})=(-1)^{\frac{1}{8}(p^2-1)}$

二次互反律

• 设 $p,q$ 为奇素数，$p\neq q$，则

  $(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

Jacobi 符号和二次剩余问题

• Jacobi 符号：对 Legendre 符号的扩充—— $p$ 不仅限于奇素数，$p=\Pi p_i$

  $(\frac{n}{p})=\Pi(\frac{n}{p_i})$

  • 对 $n=-1,2$ 的求法与 Legendre 符号相同，二次互反律同样适用
  • 二次剩余假设：若不知道 $n=pq$ 的因子分解，判断 $a\in Z^1_n$ 是否为模 $n$ 的二次剩余是一个困难问题
    • 因为上述假设具有陷门（当 $n$ 的因子分解为已知是，存在多项式时间复杂度为 $O(lg^3(n))$ 的算法判断是否为二次剩余）。所以可以根据此构造一个公钥密码