01_数学基础：数论与模运算

1. 整除 Divisibility

整除是模运算的基础概念。

定义：设\(a\)、\(b\)均为整数，且\(a \neq 0\)，若存在整数\(k\)使得\(b=a*k\)，则称\(a\)整除\(b\)，记作\(a|b\)。
整除相关的3个命题：
- ① 对于任意整数\(a\)，都有\(1|a\)；若\(a \neq 0\)，则有\(a|0\)且\(a|a\)。
- ② 若\(a|b\)且\(b|c\)，则\(a|c\)。
- ③ 若\(a|b\)且\(a|c\)，则\(a|(s*b+t*c)\)，其中\(s\)、\(t\)为任意整数。

2. 素数与互素 Primes and Coprimes

素数的定义：若整数\(p\)只有因子\(\pm 1\)及\(\pm p\)，则称\(p\)为素数。
互素 (relatively prime) 的定义：对于整数\(a\)、\(b\)，若最大公约数\(\gcd(a,b)=1\)，则称\(a\)、\(b\)互素。
算术基本定理（质因数分解）：任一整数\(a(a>0)\)都能唯一分解成以下形式：\(a=p_1*p_2*...*p_t\)，其中\(p_1, p_2, ..., p_t\)是素数。

3. 最大公约数与裴蜀定理 Greatest Common Divisor & Bézout's Identity

裴蜀定理在数论中至关重要，特别是用于求解模逆元。

定理定义：设\(a\)、\(b\)为整数，且\(a\)、\(b\)中至少有一个不等于0，令\(d=\gcd(a,b)\)，则一定存在整数\(x\)、\(y\)使得下式成立：\(a*x+b*y=d\)。
互素时的特例：特别地，当\(a\)、\(b\)互素时（即\(\gcd(a,b)=1\)），则一定存在整数\(x\)、\(y\)使得\(a*x+b*y=1\)成立。这可以通过扩展欧几里得算法（Extended Euclidean Algorithm）来求解。

扩展欧几里得算法

算法背景与核心目的

假设 \(A\) 与 \(N\) 互素，即 \(\gcd(A, N) = 1\)，此时若要求解 \(A\) 在模 \(N\) 下的乘法逆元 \(A^{-1} \pmod N\)，就需要使用扩展欧几里得算法。

扩展欧几里得算法是对传统欧几里得算法（辗转相除法）的拓展。在求解 \(\gcd(A, N)\) 的每一次循环中，该算法不仅会更新被除数和除数，还会同步更新用于展开 \(n\) 和 \(a\) 的系数变量 \(x_1\)、\(y_1\)、\(x_2\)、\(y_2\) 。

数学原理解析与公式推导

算法的核心在于维护两个等式，使其在每一次“辗转相除”的循环中都保持成立。

初始状态下，令 \(n=N\)、\(a=A\)、\(x_1=1\)、\(y_1=0\)、\(x_2=0\)、\(y_2=1\) 。此时，当前的被除数 \(n\) 和除数 \(a\) 可以展开为以下线性组合：

\[ n = x_1 \cdot N + y_1 \cdot A \]

\[ a = x_2 \cdot N + y_2 \cdot A \]

在每一次循环中，计算商 \(q = n / a\) 。根据辗转相除法的规则，下一次循环的被除数 \(n'\) 和除数 \(a'\) 为：

下一次的被除数 \(n'\) 就是当前的除数 \(a\) ：

\[ n' = a = x_2 \cdot N + y_2 \cdot A \]
下一次的除数 \(a'\) 则是当前 \(n\) 除以 \(a\) 的余数，即 \(n \pmod a\) ：

\[ a' = n \pmod a \]

利用除法关系 \(n = q \cdot a + r \implies r = n - q \cdot a\)，可以将其展开为：

\[ a' = (x_1 - q \cdot x_2) \cdot N + (y_1 - q \cdot y_2) \cdot A \]

通过对比系数，可以得出在每次循环中更新 \(x\) 和 \(y\) 的核心递推公式：

新的 \(x_1 \leftarrow x_2\)
新的 \(x_2 \leftarrow x_1 - q \cdot x_2\)
新的 \(y_1 \leftarrow y_2\)
新的 \(y_2 \leftarrow y_1 - q \cdot y_2\)

结果判定

当循环结束（即除数 \(a = 0\) 时），此时的被除数 \(n\) 即为 \(A\) 和 \(N\) 的最大公约数 \(\gcd(A, N)\) 。若 \(n = 1\)（即 \(A\) 与 \(N\) 互素），根据最后保留下来的展开式 \(1 = x_1 \cdot N + y_1 \cdot A \implies 1 \equiv y_1 \cdot A \pmod N\)，此时的 \(y_1\) 便是 \(A \pmod N\) 的乘法逆元。

为防止最终计算出的 \(y_1\) 为负数，通常需要将其转换为正数范围内的加法逆元：\(y_1 = (y_1 + N) \pmod N\) 。

代码实现

#include <stdio.h>

/**
 * 函数: xgcd
 * 功能: 使用扩展欧几里得算法求 gcd(A, N)，并计算 A 模 N 的乘法逆元。
 * 返回值: 返回 a 和 n 的最大公约数 gcd(a, n)。
 * 参数:
 * a: 要求逆元的数 (相当于推导中的 A)
 * n: 模数 (相当于推导中的 N)
 * pinverse: 用于输出乘法逆元的指针。例如 xgcd(3, 20, &inv) 返回 1，inv 被赋值为 7。
 */
int xgcd(int a, int n, int *pinverse)
{
    // 初始化系数
    int x1 = 1, y1 = 0;
    int x2 = 0, y2 = 1;
    int q, r, t;
    int N = n; // 保存初始模数，用于最后处理负数逆元

    // 循环直到余数(或新的除数)为 0
    while(a != 0)
    {
        /**
         * 当前状态:
         * 被除数 n = x1*N + y1*A
         * 除数 a = x2*N + y2*A
         */

        q = n / a;  // 计算商
        r = n % a;  // 计算余数

        // 1. 更新 x 系列系数
        t = x1;
        x1 = x2;
        x2 = t - q * x2;

        // 2. 更新 y 系列系数 (y 系数最终决定逆元)
        t = y1;
        y1 = y2;
        y2 = t - q * y2;

        // 3. 更新被除数和除数，进入下一轮迭代
        n = a;  // 老的除数成为新的被除数
        a = r;  // 老的余数成为新的除数
    }

    /**
     * 循环结束时，a = 0，此时 n 就是 gcd(A, N)。
     * 如果 n = 1，则说明 A 和 N 互素，此时 y1 即为 A (mod N) 的乘法逆元。
     */

    // 如果原先的 y1 是负数，将其转化为正数范围内的等价逆元
    y1 = (y1 + N) % N;

    // 通过指针返回逆元结果
    *pinverse = y1;

    // 返回最大公约数
    return n;
}

4. 模运算和同余 Modular Arithmetic and Congruence

模运算是一种整数算术系统，当数值达到某个称为“模”的\(n\)值时，数值会“绕回”。

同余的定义：设 \(a\)、\(b\)、\(n\) 均为整数，且 \(n \neq 0\)，当 \(a-b\) 是 \(n\) 的倍数时（即\(n|(a-b)\)），我们称 \(a\)、\(b\) 对于模 \(n\) 同余，记作：\(a \equiv b \pmod n\)。

同余的5个基本命题：

零同余：当且仅当\(n|a\)时，有\(a \equiv 0 \pmod n\)。
自反性：\(a \equiv a \pmod n\)。
对称性：当且仅当\(b \equiv a \pmod n\)时，有\(a \equiv b \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-c \equiv b-d \pmod n\)。
- 乘法：\(a*c \equiv b*d \pmod n\)。

5. 逆元 Inverse

在标准算术中，非零数都有倒数；在模运算中，逆元在特定条件下存在，并在解密过程中发挥关键作用。

5.1 加法模逆元 (Additive Inverse)

定义：若\(a+b \equiv 0 \pmod n\)，则称\(a\)是\(b\)的加法模\(n\)逆元（反之亦然）。
应用实例（恺撒加密）：
- 字母表被映射为\(0\)到\(25\)。
- 加密过程：\(y=(x+3)\%26\)（向前移位3）。
- 解密过程：\(x=(y+23)\%26\)（向后移位相当于加上加法逆元）。

5.2 乘法模逆元 Multiplicative Inverse

定义：若\(a*b \equiv 1 \pmod n\)，则称\(b\)是\(a\)的乘法模\(n\)逆元，记作\(a^{-1}\)。
存在条件：上述等式成立的充要条件是\(a\)与\(n\)互素，即\(\gcd(a,n)=1\)。
- 证明思路：由裴蜀定理，存在\(x\)、\(y\)使\(ax+ny=1\)。两边取模\(n\)得\(ax \equiv 1 \pmod n\)（因为\(ny \equiv 0 \pmod n\)），故\(x\)即为逆元。
求解示例：求13模35的乘法逆元
- 设逆元为\(x\)，则\(13*x \equiv 1 \pmod{35}\)。
- 因\(\gcd(13,35)=1\)，必定存在\(x\)、\(y\)使得\(13*x+35*y=1\)。
- 利用扩展欧几里得法 (Extended Euclidean algorithm) 求解：
  1. \(35 = 2*13 + 9\)
  2. \(13 = 1*9 + 4\)
  3. \(9 = 2*4 + 1\)
- 反向代入：
  
  \[ 1 = 9 - 2*4 = 35 - 2*13 - (13 - 1*9)*2 \]
  
  \[ = 35 - 2*13 - (13 - (35 - 2*13))*2 \]
  
  \[ = (35 - 2*13)*3 - 13*2 \]
  
  \[ = 35*3 - 8*13 \]
- 解得：\(x = -8, y = 3\)。
- 由于\(-8 \equiv (-35+27) \equiv 27 \pmod{35}\)，所以13模35的乘法逆元为27。
- 验证：\(13*27 = 351 \equiv 1 \pmod{35}\)。
乘法密码的加解密示例：
- 已知：模数\(n=5\)，加密密钥\(a=2\)。
- 求逆元：找\(b\)使\(2 \cdot b \equiv 1 \pmod 5\)，由于\(2 \cdot 3 = 6 \equiv 1 \pmod 5\)，故逆元\(b=3\)。
- 加密：明文\(s=4\)，密文\(t \equiv 4 \cdot 2 \pmod 5 \equiv 8 \pmod 5 \equiv 3\)。
- 解密：用密文\(t\)乘以逆元\(b\)，即\(s \equiv 3 \cdot 3 \pmod 5 \equiv 9 \pmod 5 \equiv 4\)。

6. 仿射密码 The Affine Cipher

仿射密码将加法和乘法元素结合成一个单一的线性函数。它需要两个密钥：\(k_1\)（乘数）和\(k_2\)（偏移量）。

加密：\(y \equiv (x \cdot k_1 + k_2) \pmod n\)。（为保证可逆，必须满足\(\gcd(k_1, n) = 1\)）。
解密：先减去偏移量\(k_2\)，再乘以\(k_1\)的模逆元：\(x \equiv (y - k_2) \cdot k_1^{-1} \pmod n\)。