公钥密码学有关知识

作者：hxd

日期：2025年3月28日

欧拉函数的知识

欧拉函数（Euler’s Totient Function），记作$\phi(n)$，是数论中的一个重要函数，表示小于或等于正整数$n$且与$n$互质的正整数的个数。这里“互质”指的是最大公约数为1。

欧拉函数的定义

对于正整数$n$，欧拉函数$\phi(n)$定义为：

$\phi(n) = \text{小于或等于 } n \text{ 且与 } n \text{ 互质的正整数的个数}$

欧拉函数的性质

  1. 对于素数$p$：

    因为素数与所有小于它的正整数都互质。

  2. 对于素数的幂$p^k$：

这是因为在$1$到$p^k$之间，只有$p$的倍数（共有$p^{k-1}$个）不与$p^k$互质。

  1. 积性函数：
    如果两个正整数$a$和$b$互质（即$\gcd(a, b) = 1$），则：

  2. 一般公式：
    如果$n$的质因数分解为：

则欧拉函数可以通过以下公式计算：

计算示例

  1. 计算$\phi(12)$：
    • 质因数分解：$12 = 2^2 \times 3$
    • 应用公式：
    • 验证：小于12且与12互质的数为1, 5, 7, 11，共4个。
  2. 计算$\phi(7)$：
    • 7是素数，所以：
    • 验证：小于7且与7互质的数为1, 2, 3, 4, 5, 6，共6个。

$\phi(12) = 12 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$

$\phi(7) = 7 - 1 = 6$

欧拉定理

欧拉函数在欧拉定理中扮演重要角色。欧拉定理指出，如果两个正整数$a$和$n$互质，则：

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

这是费马小定理的推广（当$n$为素数时，$\phi(n) = n - 1$，即费马小定理）。

为什么在$1$到$p^k$之间，只有$p$的倍数不与$p^k$互质？

要理解这一点，我们需要明确以下几个概念：

  1. 互质的定义：两个数$a$和$b$互质，当且仅当$\gcd(a, b) = 1$。
  2. $p^k$的性质：$p$是素数，$p^k$的唯一质因数是$p$。因此，任何与$p^k$不互质的数必须包含$p$作为其质因数（即能被$p$整除）。

关键观察：

  • 在$1$到$p^k$之间，不与$p^k$互质的数必须满足$\gcd(m, p^k) \neq 1$。由于$p^k$的唯一质因数是$p$，这意味着：
  • 即$m$是$p$的倍数。
  • 因此，不与$p^k$互质的数就是$p$的倍数。

$\gcd(m, p^k) \neq 1 \iff p \mid m$

$p$的倍数的个数：

在$1$到$p^k$之间，$p$的倍数为：

$p, 2p, 3p, \ldots, p^{k-1} \cdot p = p^k$

这些数的形式为$m = p \cdot t$，其中$t = 1, 2, \ldots, p^{k-1}$。因此，$p$的倍数的总数为$p^{k-1}$。

举例验证：

以$p=2$和$k=3$（即$p^k = 8$）为例：

  • $1$到$8$之间的数：1, 2, 3, 4, 5, 6, 7, 8。
  • 其中$2$的倍数为：2, 4, 6, 8，共$4 = 2^{3-1} = 2^2$个。
  • 与$8$不互质的数就是这些$2$的倍数（因为$\gcd(2,8)=2$,$\gcd(4,8)=4$, …,$\gcd(8,8)=8$）。

欧拉函数

欧拉函数$\phi(n)$定义为小于或等于$n$且与$n$互质的正整数的个数。对于任意正整数$n$，如果其质因数分解为：

$n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m},$

其中$p_1, p_2, \ldots, p_m$是不同的质数，$k_1, k_2, \ldots, k_m$是它们的幂次，那么欧拉函数可以通过以下公式计算：

$\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right).$

为什么这个公式成立？

这个公式的推导基于容斥原理（Inclusion-Exclusion Principle），即通过逐步排除不满足条件的数来计算满足条件的数的个数。

具体推导过程

  1. 初始情况：
    在$1$到$n$之间，总共有$n$个数。我们需要计算其中与$n$互质的数的个数，即这些数不被$n$的任何质因数$p_1, p_2, \ldots, p_m$整除。
  2. 排除被$p_i$整除的数：
    • 对于每个质因数$p_i$，$1$到$n$之间能被$p_i$整除的数的个数为$\frac{n}{p_i}$（因为每隔$p_i$个数就有一个$p_i$的倍数）。
    • 因此，我们需要从总数$n$中减去这些数的个数：
    • 但这样会多减了那些同时被多个$p_i$整除的数（比如同时被$p_1$和$p_2$整除的数）。
  3. 加回被$p_i p_j$整除的数（容斥原理）：
    • 对于每对不同的质因数$p_i$和$p_j$，$1$到$n$之间能被$p_i p_j$整除的数的个数为$\frac{n}{p_i p_j}$。
    • 我们需要加回这些数，因为它们被减去了两次（一次在$p_i$，一次在$p_j$）：
    • 但这样又会多加那些同时被三个质因数整除的数。
  4. 继续容斥：
    • 对于三个质因数的组合$p_i p_j p_k$，我们需要再减去$\frac{n}{p_i p_j p_k}$，以此类推。
    • 最终，根据容斥原理，$\phi(n)$可以表示为：
  5. 因式分解：
    观察上式，可以发现它实际上是以下乘积的展开形式：
    • 展开这个乘积时，会得到：
    • 这与容斥原理的表达式一致。

$n - \sum_{i=1}^m \frac{n}{p_i}.$

$n - \sum{i=1}^m \frac{n}{p_i} + \sum{1 \leq i < j \leq m} \frac{n}{p_i p_j}.$

$\phi(n) = n - \sum{i=1}^m \frac{n}{p_i} + \sum{1 \leq i < j \leq m} \frac{n}{pi p_j} - \sum{1 \leq i < j < k \leq m} \frac{n}{p_i p_j p_k} + \cdots + (-1)^m \frac{n}{p_1 p_2 \cdots p_m}.$

$\phi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right).$

$n \left(1 - \sum{i=1}^m \frac{1}{p_i} + \sum{1 \leq i < j \leq m} \frac{1}{p_i p_j} - \cdots + (-1)^m \frac{1}{p_1 p_2 \cdots p_m}\right),$

直观理解

  • 公式$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$可以理解为：
    从$1$到$n$的所有数中，排除掉所有能被$n$的质因数整除的数，剩下的就是与$n$互质的数。
  • 每个$\left(1 - \frac{1}{p_i}\right)$表示“保留不被$p_i$整除的数的比例”。

例子验证

以$n = 12$为例：

  • 质因数分解：$12 = 2^2 \times 3$。
  • 应用公式：
  • 验证：小于等于 12 且与 12 互质的数为 1, 5, 7, 11，共 4 个。

$\phi(12) = 12 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4.$

有限域

有限域（Finite Field），也称为伽罗瓦域（Galois Field），是一个包含有限个元素的域。域是一种代数结构，支持加、减、乘、除（除零以外）等运算，并且满足特定的性质（如结合律、交换律、分配律等）。

当提到GF(q)时，它表示一个包含$q$个元素的有限域。如果$q$是一个素数，那么GF(q)是一个由模$q$的整数构成的域。

GF(q) 的定义

  1. $q$是素数：
    • 当$q$是一个素数时，GF(q)可以简单地表示为模$q$的整数集合：
    • 加法和乘法运算都是模$q$的运算。
  2. 域的性质：
    • 加法：$a + b \mod q$
    • 乘法：$a \cdot b \mod q$
    • 加法逆元：对于任意$a$，存在$-a$使得$a + (-a) \equiv 0 \mod q$。
    • 乘法逆元：对于任意非零元素$a$，存在$a^{-1}$使得$a \cdot a^{-1} \equiv 1 \mod q$。
  3. 例子：
    • 如果$q = 5$，则$GF(5) = {0, 1, 2, 3, 4}$。
    • 加法示例：$3 + 4 = 7 \equiv 2 \mod 5$。
    • 乘法示例：$3 \cdot 4 = 12 \equiv 2 \mod 5$。
    • 乘法逆元示例：$3^{-1} = 2$，因为$3 \cdot 2 = 6 \equiv 1 \mod 5$。

$GF(q) = {0, 1, 2, \dots, q-1}$

为什么$q$必须是素数？

  1. 保证乘法逆元的存在：
    • 如果$q$是素数，那么对于任意非零元素$a \in GF(q)$，都存在一个乘法逆元$a^{-1}$，使得$a \cdot a^{-1} \equiv 1 \mod q$。
    • 如果$q$不是素数，某些元素可能没有乘法逆元，从而不满足域的定义。
  2. 例子：
    • 如果$q = 4$（不是素数），则$GF(4) = {0, 1, 2, 3}$。
    • 元素$2$没有乘法逆元，因为$2 \cdot 1 = 2 \not\equiv 1 \mod 4$，且$2 \cdot 3 = 6 \equiv 2 \mod 4$。

GF(q) 的扩展：$q$是素数的幂

当$q$是素数的幂（即$q = p^n$，其中$p$是素数，$n$是正整数）时，GF(q)仍然是一个有限域，但它的构造更加复杂。这种情况下，GF(q)的元素不再是简单的整数，而是多项式或其他代数结构的表示。

  1. 例子：

    • $GF(2^3) = GF(8)$是一个包含 8 个元素的有限域。
    • 它的元素可以表示为多项式，例如$0, 1, x, x+1, x^2, x^2+1, x^2+x, x^2+x+1$。

  2. 运算规则：

    • 加法和乘法基于多项式运算，并使用一个不可约多项式进行模运算。

GF(q)/{0}的概念

GF(q)/{0}表示在有限域GF(q)中移除零元素后的集合。换句话说，它是GF(q)中所有非零元素组成的集合。详细解释如下：

  1. GF(q)：
    • GF(q)是一个包含$q$个元素的有限域，其中$q$是一个素数或素数的幂。
    • 如果$q$是素数，GF(q)可以表示为：
    • 如果$q$是素数的幂（如$q = p^n$），GF(q)的元素通常是多项式或其他代数结构的表示。
  2. GF(q)/{0}：
    • GF(q)/{0}表示从GF(q)中移除零元素后的集合。
    • 即：
    • 这个集合中的元素都是非零的。

$GF(q) = {0, 1, 2, \dots, q-1}$

$GF(q)/{0} = {1, 2, \dots, q-1}$

GF(q)/{0} 的性质

  1. 乘法群：
    • GF(q)/{0}构成一个乘法群（称为乘法循环群）。
    • 在这个群中，每个非零元素都有一个乘法逆元，且乘法运算满足封闭性、结合律和交换律。
  2. 生成元：
    • 有限域的乘法群是一个循环群，GF(q)/{0}是一个循环群，因此存在一个生成元（原根）$g$，使得：
    • 生成元的幂可以生成整个GF(q)/{0}。
  3. 阶数：
    • GF(q)/{0}的阶数（元素个数）是$q-1$。

$GF(q)/{0} = {g^0, g^1, g^2, \dots, g^{q-2}}$

例子

  1. GF(5)：
    • $GF(5) = {0, 1, 2, 3, 4}$。
    • $GF(5)/{0} = {1, 2, 3, 4}$。
    • 这是一个乘法群，生成元可以是$2$或$3$。
      • 以$2$为生成元：
      • 因此，$GF(5)/{0} = {2^0, 2^1, 2^2, 2^3} = {1, 2, 4, 3}$。
  2. GF(4)：
    • $GF(4)$的元素可以表示为多项式：
    • $GF(4)/{0} = {1, x, x+1}$。
    • 这是一个乘法群，生成元可以是$x$或$x+1$。

$2^1 = 2, \quad 2^2 = 4, \quad 2^3 = 3, \quad 2^4 = 1$

$GF(4) = {0, 1, x, x+1}$