RSA基础：欧拉素数定理
郝伟 2020/07/03

• 0 前言
• 1 基本概念
  • 1.1 余数 (Reminder)
  • 1.2 质数 (Prime)
  • 1.3 公约数
  • 1.4 互质 (relatively prime)
  • 1.5 同余 (congruence modulo)
• 2 欧拉函数 $φ(n)$
  • 2.1 定义
  • 2.2 性质
  • 2.3 计算
  • 2.4 计算扩展
• 3 欧拉公式
  • 3.1 定义
  • 3.2 证明
• 4 总结
• 参考资料

0 前言

欧拉定理(Euler Theorem)，也称费马-欧拉定理或欧拉函数定理，这是一个关于正整数同余的公式，表示为：$$a^{φ(n)} \equiv1 (\mathrm{mod} \ n)$$其中，$a$ 与 $n$ 均为正整数，且两者互质。具体这个公式到底有什么含义，在实际中如何使用，本文将进行详细解释。

1 基本概念

首先，欧拉定理讨论的内容是整数的操作（记为：$\mathbb{N}$），尤其是正整数（$\mathbb{N^+}$）相关的，所以，为了理解欧拉定理，让我们先了解一些基本概念。

1.1 余数 (Reminder)

若整数 $m, n, k, r$ 满足 $m = k \times n + r$，且 $n \neq 0，0 \leq r < n$，则称 $r$ 是 $m$ 对 $n$ 的余数。举例来说，$13 = 2 * 5 + 3$，其中3就是13除以5的余数。我们也可以换一种方式来表达 $r=m-\lfloor {b \over a} \rfloor n$，即 $\lfloor {b \over a} \rfloor$ 表示取 a 除以 b 的整数部分。为了求余数，定义 mod 作为取余操作，如 $r = m$ mod $n$，当 $r = 0$ 时，称 $m$ 可以被 $n$ 整除，记作 $a|b$。

注：$\lfloor \rfloor$ 是对小数的取整数部分的操作，如 $\lfloor {5 \over 4} \rfloor=\lfloor 1.25 \rfloor =3$，$\lfloor 3.1415926 \rfloor =3$.

1.2 质数 (Prime)

给定自然数n大于1，若n只能够被1和其本身整除，则n是质数（也叫素数）。如 2，3，5，7，11，13 等都是质数。

1.3 公约数

若正整数 $a,b$ 都可以被 $c$ 整除，则 $c$ 是 $a,b$ 的公约数，记作 $a,b|c$。如6是24和36的公约数。$a,b$的公约数可以有多个，其中最大公约数记作 $gcd(a,b)$ 或简化形式 $(a,b)$。

1.4 互质 (relatively prime)

若 $a,b$ 均为正整数且两者的公约数只有1，则称两个数互质，记为：$(a,b)=1$。举例来说，(5,6)=1, (15, 13)=1。这里要特别注意，互质与这两个数是否为质数没有任何关系，比如 (3,5)=1 是两个质数，而(15,8)=1，则是两个合数。

1.5 同余 (congruence modulo)

给定一个正整数 $m$，如果两个整数 $a$ 和 $b$ 满足 $a-b$ 能够被 $m$ 整除，即 $(a-b)/m$ 的结果为正整数，那么就称 $a$ 与 $b$ 对 模 $m$ 同余，或简称为对 $m$ 同余，记作 $a ≡ b \ (\textrm{mod} \ m)$，其中符号 $≡$ 表示同余，对模 $m$ 同余是整数的一个重要等价关系。根据这个定义，我们可以知道欧拉定理是一个关于同余的定理。

2 欧拉函数 $φ(n)$

2.1 定义

设 $n \in \mathbb{N^+}$ ，则 $φ(n)=|A|，其中A=\{m | 1 \leq m < n$, $(m, n)=1\}$。

注：$| S |$ 表示集合S元素的个数。

解释：给定一个正整数 $n$，欧拉函数就是求在 $[1, n)$ 区间上，与 $n$ 互质的整数的个数。举例来说，设$m=8$，则与8互质的正整数集合$A={1, 3, 5, 7}$，此集合共有4个元素，所以 $φ(8)=4$。

2.2 性质

欧拉函数的定义域与值域有一一对应关系，即已知 $m$ 可以求出唯一的 $\varphi(m)$，但是反过来不可能，如已知 $φ(m)=4$，除了8，结果还可以是其他值，如10（此时$A=[1,3,7,9]$）。所以欧拉函数的逆函数的解有多个值，尤其是当 $φ(m)$ 的值很大时，有更多的解。这个性质很重要，在密码学中有相关的应用。

2.3 计算

有了这个函数以后怎么计算，我们分情况讨论：

• 情况1：$n = 1$，则 $\varphi(n) = 1$，因为1与自身互质；
• 情况2：$n$ 是质数，则 $\varphi(n) = n - 1$, 因为任何一个质数与比自身小的数都只有1这个公约数；
• 情况3：$n = p^k$，其中 $p>1, k \geq 1$ 且均为正整数，则 $\varphi(n) =\varphi(p^k)= (p-1)*p^{k-1}$；
• 情况4：$n=pq$，其中 $p,q$均为质数，则 $\varphi(n)=\varphi(pq)=\varphi(p)\varphi(q)$。

关于情况4，我们可以简单证明：
由于 $p, q$ 是质数，所以与 $pq$ 不互质的数只有两种情况：
1：$p$的整数倍： $p, 2p, 3p, ..., (q-1)p$，共 $q-1$ 个；
2：$q$的整数倍： $q, 2q, 3q, ..., (p-1)q$，共 $p-1$ 个；
所以在区间 $[1, pq)$ 上，与 $qp$ 互质的正整数个数$=$比 $pq$ 小的正整数个数 $- p$ 的倍数 $-q$ 的倍数
即，$\varphi(pq) =(pq-1) - (q-1)-(p-1)=pq - p - q + 1 = (p-1)(q-1)$
证毕。

2.4 计算扩展

我们对情况4进行扩展，可以得到更为一般的欧拉函数的计算方法：

已知 $n,p$ 均为正整数，若 $$n=\prod_{p|n,1\leq p < n} p ^{a_p - 1}$$则：$$\varphi(n) = \prod (p - 1 ) p^{a_p - 1} ……(Eq.1)$$也可以表示为：$$\varphi(n) =n\prod(p-{1 \over p})……(Eq.2)$$

举例说明，设 $n=72$，则$\varphi(n)=\varphi(72)=\varphi(8*9)=\varphi(2^3*3^2)$。此时，我们可以使用以上两个公式分别计算：
使用 $Eq.1$ 可得：$$\varphi(2^3*3^2)=(2-1) 2^{3-1} * (3-1)3^{2-1}=4*6=24$$
使用 $Eq.2$ 可得：$$\varphi(2^3*3^2)=72*(1- {1 \over 2}) (1 - {1 \over 3}) =72 * {1\over 2} * {2 \over 3} =24$$

使用两种公式计算结果一致。
注1：$p|n$ 表示 $n$ 能被 $p$ 整除。
注2：$a_p$ 表示的是最大次方，如8可以写成 $2^3$，此时 $a_p$ 为 $3$，但是不可以写成 $2^2 * 2^1$。

3 欧拉公式

3.1 定义

对任意两个正整数 $a, n$，若两者素质，则：$a^{φ(n)} \equiv 1 (\mathrm{mod} \ n)$。
注：作为对比，费马小定理（$a^{p-1} \equiv 1 (\mathrm{mod} \ p)$，其中 $p$ 为质数），实际上就是欧拉公式的特殊情况。

3.2 证明

设与 $n$ 互质的正整数集合 $Z_n=\{x_1,x_2……x_{φ(n)}\}$，共$φ(n)$个元素。
再设集合 $S=\{m_1, m_2,…,m_{φ(n)}\}$，其中 $m_i=a * x_1；(\mathrm{mod} \ n)$，即整数 $a$ 与每个质数的乘积后对 $n$ 求余；
则有：$Z_n= S$。

为什么 $Z_n=S$？
① 因为 $a$ 与 $n$ 互质，所以对任意 $m_i = a * x_i \ mod \ n$，都有 $m_i$ 与 $n$ 互质；
② 当 $i \neq j$ 时， $x_i \neq x_j$，所以 $x_i (\mathrm{mod} \ n) \neq x_j (\mathrm{mod} \ n)$，由 $a, n$ 互质可得 $a * x_i (\mathrm{mod} \ n) \neq a * x_j (\mathrm{mod} \ n)$。
由①和②联立可得，一个任意两元素均不相同且都与$n$互质的集合，因为这样的集合是唯一的，所以$Z_n$与$S$相同。

设 $P_{Z_n} = \prod_1^{\varphi(n)} x_i, P_S= \prod_1^{\varphi(n)} m_i$，因为 $Z_n= S$， 所以 $P_{Z_n} =P_S$。

$a^{\varphi(n)}*P_{Z_n} \ \mathrm{mod} \ n$
$=(a^{\varphi(n)}*x_1*x_2*...*x_{\varphi{(n)}} ) \ \mathrm{mod} \ n$
$=(ax_1*ax_2*...*ax_{\varphi{(n)}}) \ \mathrm{mod} \ n$ # 将a的指数展开并分配至每个x
$=(ax_1 \ \mathrm{mod} \ n)*(ax_2 \ \mathrm{mod} \ n)*...*(ax_{\varphi{(n)}} \ \mathrm{mod} \ n) \ \mathrm{mod} \ n$
$=(m_1 * m_2*...*m_{\varphi{(n)}}) \ \mathrm{mod} \ n$
$=P_S \ \mathrm{mod} \ n =P_{Z_n} \ \mathrm{mod} \ n$

即 $$a^{\varphi(n)}*P_{Z_n} \ \mathrm{mod} \ n=P_{Z_n} \ \mathrm{mod} \ n$$根据余数性质，两边可以同时消去$P_{Z_n}$，可得：$$a^{\varphi(n)} \ \mathrm{mod} \ n=1 \ \mathrm{mod} \ n$$最终可得：$$a^{\varphi(n)} \ \mathrm \equiv 1 \ (\mathrm{mod} \ n)$$证毕。

4 总结

本文首先介绍了欧拉函数的基础知识，然后介绍了欧拉函数，欧拉定理及其证明。欧拉定理是一个重要的定理，在很多领域都有应用，比如在信息安全领域，非对称公私钥加密算法RSA就是基于欧拉定理。

参考资料

[1] 余数定理，郝老师，2020/05/03.
[2] 欧拉定理，百度百科。