数论初探--从同余到 RSA

数论初探—从同余到 RSA

secondary

致谢

• 感谢李老师指出本文关于欧拉函数积性的说明中 $\varphi(ab)=\varphi(a)\cdot\varphi(b)$ 缺少了该性质成立的前提条件 $\gcd(a,b)=1$．
• 感谢 yegetables 指出本文的一个 typo．

本文中，将混合出现「C 语言表达式」与数学公式，「C 语言表达式」将使用「特殊的格式」标注．
本文的内容以「乘法逆元」的计算与「RSA」算法的推导为核心．
部分符号说明：

• 整除 $\mid$
  $\forall a,b\in\mathbb{Z},b\ne0, \exists{c}\in \mathbb{Z},a=bc$ 或者说 a%b==0，则记作 $b\mid a$
• 最大公因数 $\gcd(a,b)$
  $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公因数

其余符号将在本文文中说明．

模意义下的运算

模余运算

$\forall a,b,n\in\mathbb{Z}$时，有 $a \bmod n=b \bmod n$ 或者说 a%n==b%n，则称「整数 $a$ 与整数 $b$ 对模 $n$ 同余」 ，记作 $a\equiv b\pmod{n}$

同余还可定义为：$\forall a,b,n\in\mathbb{Z}$ ，若 $n\mid a-b$，则「整数 $a$ 与整数 $b$ 对模 $n$ 同余」 ，记作 $a\equiv b\pmod{n}$

若 「整数 $a$ 与整数 $b$ 对模 $n$ 不同余」，记作 $a\not\equiv b\pmod{n}$

$e.g.$

$3\equiv (-9)\mod 12$

同余的性质

• $a\equiv a\pmod{n}$

• $b\equiv a\pmod{n}$

• 若 $a\equiv b\pmod{n}$ 且 $b\equiv c\pmod{n}$，则 $a\equiv c\pmod{n}$

• 若 $a\equiv b\pmod{n}$ 且 $c\equiv d\pmod{n}$，则 $a+c\equiv b+d\pmod{n}$

• 若 $a\equiv b\pmod{n}$ 且 $c\equiv d\pmod{n}$，则 $ac\equiv bd\pmod{n}$

• 若 $ac\equiv bc\pmod{n}$ 且 $c\neq0$，则 $a\equiv b\pmod{\frac{n}{\gcd(c,n)}}$

• 若 $a\equiv b\pmod{n}$ ，则 $a^m\equiv b^m\pmod{n}$

  模意义下的乘法逆元

  在有理数乘法中，乘一个数，继续乘这个数的倒数，那么最终的结果就是最初的数．
  $e.g.$

  $$3\times5=15\qquad15\times\frac{1}{5}=3$$

  可以直观的感受出乘 $5$ 和乘 $\frac{1}{5}$ 是相反的两种运算．
  而 $5\times \frac{1}{5}=1$ 也是理所当然的． $\frac{1}{5}$ 便可以理解为 $5$ 的在有理数乘法中的逆元；当然，$5$ 也是 $\frac{1}{5}$ 在有理数乘法中的逆元．
  这个例子并不严谨，但笔者相信，通过这个例子能很好的理解逆元的含义．

此时，考察模意义下的乘法逆元．
和上面一样，在模意义下乘一个数 $a$ 后，如果继续乘另一个 $x$，就能抵消乘 $a$ 所带来的影响，那么 $x$ 就是 $a$ 在模意义下的乘法逆元．
也就能得到 $ax\equiv 1\pmod{n}$ 时，$x$ 就是 $a$ 在模 $n$ 下的乘法逆元．

如何求解乘法逆元将在后文予以说明．

快速幂

为了快速求解 $a^b$ 的问题，降低其时间复杂度，可以通过快速幂的方式进行求解．
根据任何一个数都可用二进制的方式进行表示，那么

$$b = 2^0 \cdot b_0 + 2^1 \cdot b_1 + 2^2 \cdot b_2 + 2^3 \cdot b_3 + \dots + 2^n \cdot b_n \qquad \forall i\in\mathbb{N},i\in(0,n),b_i\in\{0,1\}$$

又 $\because$

$$a^{n+m}=a^n\cdot a^m$$

得

$$a^b = a^{2^0b_0} \cdot a^{2^1b_1} \cdot a^{2^2b_2} \cdot a^{2^3{b_3}}\cdots a^{2^nb_n}$$

tip
例如：

$$(13)_{10}=(1101)_2=2^0 \cdot 1 + 2^1 \cdot 0 + 2^2 \cdot 1 + 2^3 \cdot 1$$ $$a^{(13)_{10}}=a^{(1011)_2}=a^{2^0 \cdot 1 + 2^1 \cdot 0 + 2^2 \cdot 1 + 2^3 \cdot 1}=a^{2^0 \cdot 1} \cdot a^{2^1 \cdot 0} \cdot a^{2^2 \cdot 1} \cdot a^{2^3 \cdot 1}$$

据此，为了求解 $a^b$ 的值，（假设数据不会溢出）可写出如下的代码：

unsigned long long quickPower(unsigned long long a, unsigned long long b)
{
    unsigned long long result = 1;
    while (b > 0)
    {
        if (b & 1U)
            result *= a;
        a *= a;
        b >>= 1U;
    }
    return result;
}

使用快速幂的方式求 $a^b$ 的值，时间复杂度为 $\log_2b$．

快速幂并取余

有些情况下，题目中为了避免数据移除或处理高精度的大数，会只要求幂运算的结果以某个数为模的余数，此时求出最终的结果不是必要的．
在快速幂的运算中，可提前在每步运算中取余，根据同余的性质，易得：

$$(a*b)\bmod{n}=((a\bmod{n})*(b\bmod{n}))\bmod{n}$$

据此，为了求解 $a^b\bmod{n}$，可写下如下的代码：

unsigned long long quickPower(unsigned long long a, unsigned long long b, unsigned long long n)
{
    unsigned long long result = 1;
    while (b > 0)
    {
        if (b & 1U)
        {
            result *= a;
            result %= n;
        }
        a *= a;
        a %= n;
        b >>= 1U;
    }
    return result % n;
}

快速幂还可通过二分的思路使用递归实现，时间复杂度也为 $\log_2b$ ，但因同规模的数据量下递归实现相较循环实现在函数调用期间开销较大，运行速度较慢性能较差，故此本文不做介绍．

裴蜀定理

定理： $\forall a,b\in\mathbb{Z},ab\ne0$ ，则 $\exists x,y\in\mathbb{Z}$, 使得 $ax+by=\gcd(a,b)$．

线性同余方程

形如 $ax \equiv c \pmod b$ 的方程被称为 线性同余方程．

定理：方程 $ax+by=c$ 与方程 $ax \equiv c \pmod b$ 等价

因此，当求解 $ax \equiv c \pmod b$ 时，常常转化成 二元一次不定方程 $ax+by=c$ 进行求解．

定理：方程 $ax+by=c$ 与二元一次不定方程 $ax \equiv c \pmod b$ 是等价的，有整数解的充要条件为 $\gcd(a,b) \mid c$．

二元一次不定方程

info
$ax+by=c$ 有整数解的充要条件是 $\gcd(a,b)\mid c$．
证明：

• 充分性
  设 $\gcd(a,b)\mid c$ ，由 裴蜀定理 ，$ax+by=\gcd(a,b)$ 有整数解． $$\{ \begin{matrix} x=x_0 \\ y=y_0 \end{matrix}$$ 设 $c=k\cdot\gcd(a,b),k\in\mathbb{Z},k\neq0$ 则 $$ax+by=k\cdot\gcd(a,b)\\ \frac{ax}{k}+\frac{by}{k}=\gcd(a,b)$$ 则有 $$\{ \begin{matrix} x=\frac{x_0}{k} \\ y=\frac{y_0}{k} \end{matrix}$$
• 必要性 $$\because ax_0+by_0 \bmod\gcd(a,b)=0$$ $$\therefore c\bmod\gcd(a,b)=0$$

二元一次不定方程的通解

• 若 $ax+by=c$ 有解 $(x_0,y_0)$，则其通解为： $$\{ \begin{matrix} x=x_0-b_1t \\ y=y_0+a_1t \end{matrix}\\$$ 当 $t$ 为任意整数时，其为 $ax+by=c$ 整数通解．

其中

$$\{ \begin{matrix} a_1=\frac{a}{gcd(a,b)} \\ b_1=\frac{b}{gcd(a,b)} \end{matrix}$$

二元一次不定方程的特解

由 裴蜀定理 中知，下式有整数解．

$$ax_1+by_1=\gcd(a,b)$$

对比 $ax_1+by_1=\gcd(a,b)$ 与 $ax+by=c$，易知：

$$\{ \begin{matrix} x_0=kx_1 \\ y_0=ky_1 \end{matrix} \qquad(k=\frac{c}{\gcd(a,b)},k\in\mathbb{Z},k\neq0)$$

故此，只需出 $ax_1+by_1=\gcd(a,b)$ 的一个特解，即可得 $ax+by=c$ 的一个特解．

扩展欧几里德算法（exgcd）

根据欧几里德算法知：

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

即

$$ax_1+by_1=bx_2+(a\bmod b)y_2$$

又 $\because$

$$a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)$$

$\therefore$

$$ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2$$ $$ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$$

$\therefore$

$$\{ \begin{matrix} x_1=y_2 \\ y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2 \end{matrix}$$

这便是扩展欧几里德算法的核心．扩展欧几里德算法提供了计算 $ax_1+by_1=\gcd(a,b)$ 的一个特解的一种方式．

扩展欧几里德算法的一种 C 语言描述如下：

int exgcd(int a, int b, int *x, int *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    *y -= a / b * *x;
    return gcd;
}

至此，求解线性同余方程的方式描述完毕．

回顾一下，求解线性方程 $ax+by=c$ 的步骤：

1. 先利用扩展欧几里德算法求解 $ax_1+by_1=\gcd(a,b)$ 的一个特解．
2. 根据 $ax_1+by_1=\gcd(a,b)$ 与 $ax+by=c$ 的关系，求解 $ax+by=c$ 的一个特解．
3. 求解 $ax+by=c$ 的通解．

费马小定理

• 若 $p$ 为素数，$\gcd(a, p) = 1$，则 $a^{p - 1} \equiv 1 \pmod{p}$．

• $\forall a\in\mathbb{Z}$，有 $a^p \equiv a \pmod{p}$．

当 $p$ 为素数时，常用来求解乘法逆元．
经过十分简单的变换，便可发现：
$\gcd(a, p) = 1$，则 $a\cdot a^{p - 2}\equiv 1 \pmod{p}$．
所以 $a^{p - 2}$ 就是 $a$ 在模 $p$ 下的乘法逆元．
而 $a^{p - 2}$ 的求值，可通过快速幂算法完成．此处不必赘述．

欧拉函数

欧拉函数 $\varphi (n)$ 是小于或等于n的正整数中与n互质的数的数目．[4]

• 积性
  当 $\gcd(a,b)=1$ 时， $$\varphi(ab)=\varphi(a)\cdot\varphi(b)$$

欧拉定理

欧拉定理是费马小定理的推广．
若 $a,n\in\mathbb{Z^+},\gcd(a,n)$，则

$$a^{\varphi (n)}\equiv 1{\pmod {n}}$$

欧拉定理也可以用来求乘法逆元．
经过与 费马小定理 类似的变换，即可得到：
若 $a,n\in\mathbb{Z^+},\gcd(a,n)$，则

$$a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}$$

所以，$a^{\varphi (n)-1}$ 是 $a$ 在 模$n$ 下的乘法逆元．
如何求解 $\varphi (n)$ 本文不做介绍．

RSA 算法

在 RSA 中，密钥对的生成过程中完成了以下步骤：

• 生成随机数去其中的素数 $p$ 、$q$

• 记 $n=pq$ 计算 $\varphi(n)$

• 生成随机数 $e\in(0,\varphi(n))$

• 根据 $ed\equiv 1\pmod{\varphi(n)}$ 计算 $e$ 的乘法逆元 $d$．

$\varphi(n)$ 如何计算？回顾一下，$\varphi(n)$ 具有积性，也就是说当 $\gcd(a,b)=1$ 时，$\varphi(ab)=\varphi(a)\cdot\varphi(b)$．还有，若 $m$ 为素数，则有 $\varphi(m)=m-1$ ．

所以

$$\varphi(pq)=\varphi(p)\cdot\varphi(q)=(p-1)\cdot(q-1)$$

RSA 算法如何实现加密解密？

众所周知，任何信息或者说数据在计算机中都是以二进制数据的形式存储，当然这也包含欲传递的消息和将其加密后的密文．

$$C\equiv M^e\pmod{n}$$ $$M\equiv C^d\pmod{n}$$

根据欧拉定理，当 $n,a\in \mathbb{Z^+}$ 且 $\gcd(n,a)=1$ 时，

$$a^{\varphi(n)} \equiv 1 \pmod n$$

一般在简化幂的模运算的时候，当$a$和$n$互素时，可对$a$的指数取模$\varphi(n)$，当$x\equiv y \pmod {\varphi(n)}$

$$a^x \equiv a^y \pmod n$$

根据上式，有

$$e\equiv d^{-1}\pmod{\varphi(n)}$$

所以

$$M^e\equiv M^{d^{-1}}\pmod{n}$$

根据同余的传递性，可知

$$C\equiv M^{d^{-1}}\pmod{n}$$

又根据同余式幂运算的法则可知：

$$M\equiv C^d\pmod{n}$$

这便实现了消息的加密与解密．

参考资料

¹：NickelAngel’s nest. [数学]乘法逆元[G/OL].洛谷. https://www.luogu.com.cn/blog/1239004072Angel/post-shuo-xue-sheng-fa-ni-yuan.
²：维基百科编者. 费马小定理[G/OL]. 维基百科. https://zh.wikipedia.org/zh-cn/费马小定理.
³：维基百科编者. 欧拉定理 (数论)[G/OL]. 维基百科. https://zh.wikipedia.org/zh-cn/欧拉定理(数论).
⁴：维基百科编者. 欧拉函数[G/OL]. 维基百科. https://zh.wikipedia.org/zh-hans/%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0.
⁵：oi-wiki编者. 欧拉定理 & 费马小定理[G/OL]. oi-wiki. https://next.oi-wiki.org/math/fermat.
⁶：oi-wiki编者. 线性同余方程[G/OL]. oi-wiki.https://next.oi-wiki.org/math/linear-equation.
⁷：oi-wiki编者. 最大公约数[G/OL]. oi-wiki.https://next.oi-wiki.org/math/gcd.
⁸：oi-wiki编者. 欧拉函数[G/OL]. oi-wiki.https://next.oi-wiki.org/math/euler.
⁹：oi-wiki编者. 裴蜀定理[G/OL]. oi-wiki.https://next.oi-wiki.org/math/bezouts.