RSA基础：欧拉素数定理 郝伟 2020/07/03
[TOC]
1. 0 前言
欧拉定理(Euler Theorem)，也称费马-欧拉定理或欧拉函数定理，这是一个关于正整数同余的公式，表示为：其中，$a$ 与 $n$ 均为正整数，且两者互质。具体这个公式到底有什么含义，在实际中如何使用，本文将进行详细解释。
2. 1 基本概念
首先，欧拉定理讨论的内容是整数的操作（记为：$\mathbb{N}$），尤其是正整数（$\mathbb{N^+}$）相关的，所以，为了理解欧拉定理，让我们先了解一些基本概念。
2.1. 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$.
2.2. 1.2 质数 (Prime)
给定自然数n大于1，若n只能够被1和其本身整除，则n是质数（也叫素数）。如 2，3，5，7，11，13 等都是质数。
2.3. 1.3 公约数
若正整数 $a,b$ 都可以被 $c$ 整除，则 $c$ 是 $a,b$ 的公约数，记作 $a,b|c$。如6是24和36的公约数。$a,b$的公约数可以有多个，其中最大公约数记作 $gcd(a,b)$ 或简化形式 $(a,b)$。
2.4. 1.4 互质 (relatively prime)
若 $a,b$ 均为正整数且两者的公约数只有1，则称两个数互质，记为：$(a,b)=1$。举例来说，(5,6)=1, (15, 13)=1。这里要特别注意，互质与这两个数是否为质数没有任何关系，比如 (3,5)=1 是两个质数，而(15,8)=1，则是两个合数。
2.5. 1.5 同余 (congruence modulo)
给定一个正整数 $m$，如果两个整数 $a$ 和 $b$ 满足 $a-b$ 能够被 $m$ 整除，即 $(a-b)/m$ 的结果为正整数，那么就称 $a$ 与 $b$ 对 模 $m$ 同余，或简称为对 $m$ 同余，记作 $a ≡ b \ (\textrm{mod} \ m)$，其中符号 $≡$ 表示同余，对模 $m$ 同余是整数的一个重要等价关系。根据这个定义，我们可以知道欧拉定理是一个关于同余的定理。
3. 2 欧拉函数 $φ(n)$
3.1. 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$。
3.2. 2.2 性质
欧拉函数的定义域与值域有一一对应关系，即已知 $m$ 可以求出唯一的 $\varphi(m)$，但是反过来不可能，如已知 $φ(m)=4$，除了8，结果还可以是其他值，如10（此时$A=[1,3,7,9]$）。所以欧拉函数的逆函数的解有多个值，尤其是当 $φ(m)$ 的值很大时，有更多的解。这个性质很重要，在密码学中有相关的应用。
3.3. 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)$ 证毕。
3.4. 2.4 计算扩展
我们对情况4进行扩展，可以得到更为一般的欧拉函数的计算方法：
已知 $n,p$ 均为正整数，若 则：也可以表示为：
举例说明，设 $n=72$，则$\varphi(n)=\varphi(72)=\varphi(89)=\varphi(2^33^2)$。此时，我们可以使用以上两个公式分别计算： 使用 $Eq.1$ 可得： 使用 $Eq.2$ 可得：
使用两种公式计算结果一致。 注1：$p|n$ 表示 $n$ 能被 $p$ 整除。 注2：$a_p$ 表示的是最大次方，如8可以写成 $2^3$，此时 $a_p$ 为 $3$，但是不可以写成 $2^2 * 2^1$。
4. 3 欧拉公式
4.1. 3.1 定义
对任意两个正整数 $a, n$，若两者素质，则：$a^{φ(n)} \equiv 1 (\mathrm{mod} \ n)$。 注：作为对比，费马小定理（$a^{p-1} \equiv 1 (\mathrm{mod} \ p)$，其中 $p$ 为质数），实际上就是欧拉公式的特殊情况。
4.2. 3.2 证明
设与 $n$ 互质的正整数集合 $Zn={x_1,x_2……x{φ(n)}}$，共$φ(n)$个元素。 再设集合 $S={m1, 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)}x1x_2...*x{\varphi{(n)}} ) \ \mathrm{mod} \ n$
$=(ax1ax_2...*ax{\varphi{(n)}}) \ \mathrm{mod} \ n$ # 将a的指数展开并分配至每个x
$=(ax1 \ \mathrm{mod} \ n)(ax_2 \ \mathrm{mod} \ n)...*(ax{\varphi{(n)}} \ \mathrm{mod} \ n) \ \mathrm{mod} \ n$
$=(m1 m_2...*m{\varphi{(n)}}) \ \mathrm{mod} \ n$
$=PS \ \mathrm{mod} \ n =P{Z_n} \ \mathrm{mod} \ n$
即 根据余数性质，两边可以同时消去$P_{Z_n}$，可得：最终可得：证毕。
5. 4 总结
本文首先介绍了欧拉函数的基础知识，然后介绍了欧拉函数，欧拉定理及其证明。欧拉定理是一个重要的定理，在很多领域都有应用，比如在信息安全领域，非对称公私钥加密算法RSA就是基于欧拉定理。