密码学数论基础

本文最后更新于:2021年9月24日 晚上

密码学中需要知道的一些数论的知识大纲

密码学数论基础

整除性和带余除法

整除

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

整数

  • 带余除法(欧几里得除法a=qb+ra = qb +r
    • 进制表示

最大公因子

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

整数的唯一分解定理

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

素数

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

同余式

同余

  • nabab(modn)n\mid a-b \Leftrightarrow a \equiv b \pmod n

中国剩余定理

  • 求解同余方程组:中国剩余定理
    • 求解方程组:xbi(modm)ix\equiv b_i \pmod m_i
      • 计算:m=Πmi=miMim=\Pi m_i = m_iM_iMiMi1(modm)iM_i'M_i\equiv 1\pmod m_i
      • 则该方程有且仅有一个小于mm的解xMiMibi(modm)x\equiv \sum M_i'M_ib_i \pmod m

剩余类环

  • 剩余类:根据模 mm 的余数进行划分集合

    • 完全剩余系:对剩余类的每个集合选取一个代表元
  • Euler 函数:与 mm 互素的剩余类个数,记为 φ(m)\varphi(m)

    • Euler 定理:若 (k,m)=1(k,m) = 1,则 kφ(m)1(modm)k^{\varphi(m)} \equiv 1\pmod m
    • Fermat 小定理:若 pp 为素数,则对所有整数 aaapa(modp)a^p \equiv a \pmod p
    • 缩系:对剩余类的每个集合选取一个mm 互素的代表元
  • 快速模幂算法:“平方-乘”算法

同余方程

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

原根

  • 阶:满足 ad1(modm)a^d\equiv 1 \pmod m 的最小正整数 dd,记作 δm(a)\delta_m(a)
  • 原根:满足 δm(a)=φ(m)\delta_m(a) = \varphi(m)aa
    • 素数的原根总是存在,但是其他情况未必(原根存在定理)
    • 寻找原根:枚举原根并检验其正确性

二次剩余

Legendre 符号及 Euler 判别法

  • 二次剩余:(n,m)=1(n,m)=1,若 x2n(modm)x^2\equiv n \pmod m 有解,则 nn 称为模 mm 的二次剩余。否则称为二次非剩余
  • Legendre 符号及 Euler 判别法:设 pp 为奇素数,pnp \nmid n,则

    (ap)=±1ap12(modp)\left(\frac{a}{p}\right)=\pm 1 \equiv a^{\frac{p-1}{2}} \quad(\bmod p)

    pnp\mid n 时取得 0 )
  • 推论:
    • (1p)=(1)p12(\frac{-1}{p})=(-1)^{\frac{p-1}{2}}
    • (2p)=(1)18(p21)(\frac{2}{p})=(-1)^{\frac{1}{8}(p^2-1)}

二次互反律

  • p,qp,q 为奇素数,pqp\neq q,则

    (pq)(qp)=(1)p12q12(\frac{p}{q})(\frac{q}{p})=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}

Jacobi 符号和二次剩余问题

  • Jacobi 符号:对 Legendre 符号的扩充—— pp 不仅限于奇素数,p=Πpip=\Pi p_i

    (np)=Π(npi)(\frac{n}{p})=\Pi(\frac{n}{p_i})

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

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!