歐拉函數計算機

歡迎使用 歐拉函數計算機，這是一個全面的數論工具，可計算 φ(n)（歐拉函數），並提供逐步質因數分解、互動式互質數字網格可視化和深入分析。無論您是在學習抽象代數、準備數學競賽、研究 RSA 加密還是探索模運算，本計算機都能提供專業級的計算與豐富的教育內容。

什麼是歐拉函數？

歐拉函數 φ(n)，也稱為 歐拉總計函數，計算從 1 到 n 的正整數中與 n 互質（相對質數）的數字個數。當兩個數的最大公約數 (GCD) 等於 1 時，這兩個數就是互質的。

例如，φ(12) = 4，因為在 1 到 12 的整數中，恰好有四個數字（1, 5, 7 和 11）與 12 互質。

乘積公式

計算 φ(n) 最有效的方法是使用 n 的 質因數分解。如果 \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\)，則：

這意味著我們將 n 乘以每個 不同 質因數 p 的 \((1 - 1/p)\)。指數的大小並不重要，只有不同的質因數會影響結果。

關鍵性質

歐拉定理

歐拉定理 是使歐拉函數在密碼學中變得至關重要的核心結果：

這是 費馬小定理（n 為質數時的特殊情況）的推廣。它構成了 RSA 加密的數學基礎。

如何使用此計算機

1. 輸入正整數： 在輸入欄位中輸入 1 到 1,000,000 之間的任何數值。
2. 使用快速範例： 點擊範例按鈕嘗試經典數值，如質數、合數或 RSA 風格的半質數。
3. 查看結果： 計算機會顯示 φ(n)、質因數分解、互質比例和檢測到的性質。
4. 探索互質網格： 對於 n ≤ 400 的情況，可以在動畫可視化網格中查看哪些數字與 n 互質。
5. 研究趨勢圖： 查看 φ(k) 在 k = 1 到 min(n, 100) 範圍內的變化。

RSA 加密關聯

在 RSA 加密法 中，歐拉函數扮演著核心角色：

1. 選擇兩個大質數 p 和 q。計算 n = p × q。
2. 計算 φ(n) = (p−1)(q−1)。
3. 選擇與 φ(n) 互質的公鑰指數 e，即 gcd(e, φ(n)) = 1。
4. 計算私鑰指數 d，使得 e × d ≡ 1 (mod φ(n))。

RSA 的安全性取決於在不知道 n 的因數分解的情況下計算 φ(n) 的難度。如果攻擊者能高效地計算 φ(n)，他們就能破解 RSA。

φ(n) 的常見數值

常見問題

什麼是歐拉函數？

歐拉函數 φ(n)，也稱為歐拉總計函數，計算從 1 到 n 的正整數中與 n 互質（相對質數）的數字個數。當兩個數的最大公約數 (GCD) 為 1 時，它們就是互質的。例如，φ(12) = 4，因為只有 1, 5, 7 和 11 與 12 互質。

如何計算歐拉函數？

計算 φ(n) 的步驟：(1) 找出 n 的質因數分解。(2) 應用乘積公式：φ(n) = n × ∏(1 − 1/p)，其中 p 為 n 的每個不同質因數。例如，φ(12) = 12 × (1−1/2) × (1−1/3) = 12 × 1/2 × 2/3 = 4。對於質數 p，φ(p) = p−1。對於質數冪 p^k，φ(p^k) = p^k − p^(k−1)。

為什麼歐拉函數在 RSA 加密中很重要？

在 RSA 加密中，模數 n = p × q 是兩個大質數的乘積。歐拉函數 φ(n) = (p−1)(q−1) 用於計算私鑰：解密指數 d 必須滿足 e × d ≡ 1 (mod φ(n))，其中 e 是公鑰加密指數。在不知道 φ(n)（這需要分解 n）的情況下，計算 d 在計算上是不可行的。

什麼是歐拉定理？它與歐拉函數有什麼關係？

歐拉定理指出，如果 a 和 n 互質，則 a^φ(n) ≡ 1 (mod n)。這是費馬小定理（適用於 n 為質數時）的推廣。它是模運算和密碼學的基礎，為 RSA 加密和高效的模冪運算提供了數學基礎。

歐拉函數有哪些關鍵性質？

關鍵性質包括：(1) φ(1) = 1。(2) 對於質數 p：φ(p) = p−1。(3) 對於質數冪 p^k：φ(p^k) = p^(k−1)(p−1)。(4) 積性性質：如果 gcd(m,n) = 1，則 φ(m×n) = φ(m)×φ(n)。(5) 因數求和：對於 n 的所有因數 d，Σ φ(d) = n。(6) 當 n > 2 時，φ(n) 始終為偶數。

兩個數互質是什麼意思？

如果兩個整數 a 和 b 的最大公約數為 1，則稱它們互質（也稱為相對質數），這意味著它們沒有共同的質因數。例如，8 和 15 互質，因為 gcd(8,15) = 1，儘管兩者都不是質數。歐拉函數 φ(n) 正是計算從 1 到 n 中有多少個整數與 n 互質。

其他資源

• 歐拉函數 - 維基百科
• RSA 加密演算法 - 維基百科
• 歐拉定理 - 維基百科