数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究信息安全中的欧拉定理是什么？
欧拉定理是费马小定理的一个推广，处理整数模正整数的幂。它在初等数论的应用中不断增加，例如 RSA 密码系统的理论支撑结构。
该定理指出，对于所有互质的 a 和 n −
$$\mathrm{a^{\phi \left ( n \right )}\, \equiv\, 1\left ( mod \, n \right ) }$$
其中 $\mathrm{\phi}$(n) 是欧拉函数，它计算小于 n 且与 n 互质的正整数的个数。
考虑这些整数的集合 −
R = {x1, x2, … x$\mathrm{\phi}$(n)}，即 R 的每个元素 xi 都是小于 n 的唯一正整数，且 gcd(xi, n) = 1。然后将每个元素乘以 a 并模 n −
S = {(ax1mod n), (ax2mod n), … (ax$\mathrm{\phi}$(n)mod n)}
因为 a 与 n 互质，并且 xi 与 n 互质，所以 axi 也必须与 n 互质。因此，S 的所有成员都是小于 n 且与 n 互质的整数。
S 中没有重复元素。
如果 axi mod n 和 n 等于 axj mod n，则 xi = xj
因此，
$$\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}$(Pe) = Pe − Pe−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 的因式分解的难度。
15K+ 浏览量
