信息安全中的欧拉定理是什么？

---

欧拉定理是费马小定理的一个推广，处理整数模正整数的幂。它在初等数论的应用中不断增加，例如 RSA 密码系统的理论支撑结构。

该定理指出，对于所有互质的 a 和 n −

$$\mathrm{a^{\phi \left ( n \right )}\, \equiv\, 1\left ( mod \, n \right ) }$$

其中 $\mathrm{\phi}$(n) 是欧拉函数，它计算小于 n 且与 n 互质的正整数的个数。

考虑这些整数的集合 −

R = {x₁, x₂, … x_{$\mathrm{\phi}$(n)}}，即 R 的每个元素 xi 都是小于 n 的唯一正整数，且 gcd(x_i, n) = 1。然后将每个元素乘以 a 并模 n −

S = {(ax₁mod n), (ax₂mod n), … (ax_{$\mathrm{\phi}$(n)}mod n)}

因为 a 与 n 互质，并且 x_i 与 n 互质，所以 ax_i 也必须与 n 互质。因此，S 的所有成员都是小于 n 且与 n 互质的整数。

S 中没有重复元素。

如果 ax_i mod n 和 n 等于 ax_j mod n，则 x_i = x_j

因此，

$$\mathrm{\Pi _{i=1}^{\phi \left ( n \right )}\left ( ax_{i}\, mod\, n \right )=\Pi _{i=1}^{\phi \left ( n \right )}\, x_{i}}$$

$$\mathrm{\Pi _{i=1}^{\phi \left ( n \right )}\, ax_{i}\equiv \Pi _{i=1}^{\phi \left ( n \right )}\, x_{i}\left ( mod\, n \right )}$$

$$\mathrm{a^{\phi \left ( n \right )}\, x\left [ \Pi _{i=1}^{\phi \left ( n \right )}\, x_{i} \right ]=\Pi _{i=1}^{\phi \left ( n \right )}\, x_{i}\left ( mod\, n \right )}$$

$$\mathrm{a^{\phi \left ( n \right )}\equiv 1\left ( mod\, n \right )}$$

欧拉函数

欧拉函数是一个数学乘法函数，它计算正整数（通常称为“n”）范围内与“n”互质的正整数的个数，并且该函数可以用来理解直到给定整数“n”为止的素数的个数。

欧拉函数也称为欧拉 phi 函数。它在密码学中起着至关重要的作用。它可以找出小于 n 且与 n 互质的整数的个数。这些由 $\mathrm{Z_{n}^{*}}$ 定义的数字集合（小于 n 且与 n 互质的数字）。

欧拉函数在很多方面都是有益的。它可以用于 RSA 加密系统，该系统可用于安全目的。该函数处理素数理论，并且在计算大型计算方面也很有益。该函数可用于代数计算和简单数字。

用于表示该函数的符号是 ϕ，也称为 phi 函数。该函数包含更多理论用途而不是实际用途。该函数的实际需求是有限的。

通过几个实际示例而不是仅仅理论解释可以更好地理解该函数。计算欧拉函数有几个规则，对于不同的数字，需要使用不同的规则。

欧拉函数 $\mathrm{\phi}$(n) 使用以下规则计算 $\mathrm{Z_{n}^{*}}$ 中元素的数量 −

• $\mathrm{\phi}$(1) = 0。

• $\mathrm{\phi}$(P) = P − 1 如果 P 是素数。

• $\mathrm{\phi}$(m x n) = $\mathrm{\phi}$(m) x $\mathrm{\phi}$(n) 如果 m 和 n 互质。

• $\mathrm{\phi}$(P^e) = P^e − P^e−1（如果 P 是素数。）

以下四个规则可以组合起来获得 $\mathrm{\phi}$(n) 的值，将 n 因式分解为

$$\mathrm{n=P_{1}^{e1}\, x\,P_{2}^{e2}x\cdot \cdot \cdot P_{k}^{ek}}$$

$$\mathrm{\phi \left ( n \right )=\left ( P_{1}^{e1}-P_{1}^{e1-1} \right )\left ( P_{2}^{e2}-P_{2}^{e2-1} \right )x\cdot \cdot \cdot x\left (P_{k}^{ek}-P_{k}^{ek-1} \right )}$$

查找 $\mathrm{\phi}$(n) 的难度取决于查找 n 的因式分解的难度。