資料結構
網路
關係型資料庫管理系統
作業系統
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+ 瀏覽量
