オイラーのトーシェント関数電卓

オイラーのトーシェント関数電卓へようこそ。これは、ステップバイステップの素因数分解、インタラクティブな互いに素な数のグリッド可視化、および詳細な分析を使用して φ(n)（オイラーのファイ関数）を計算する包括的な数論ツールです。抽象代数を学んでいる学生、数学オリンピックの準備をしている方、RSA暗号に取り組んでいるエンジニア、あるいは剰余演算を探索している方など、あらゆるニーズに応える教育コンテンツが充実したプロフェッショナルな計算ツールです。

オイラーのトーシェント関数とは？

オイラーのトーシェント関数 φ(n)（オイラーのファイ関数としても知られる）は、1からnまでの正の整数のうち、nと互いに素（既約）であるものの個数をカウントします。2つの数は、それらの最大公約数（GCD）が1に等しいとき、互いに素であると言います。

例えば、φ(12) = 4 です。なぜなら、1から12までの整数のうち、12と互いに素なのは 1、5、7、11 のちょうど4つの数だからです。

積の公式

φ(n)を計算する最も効率的な方法は、nの素因数分解を利用することです。もし \(n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}\) ならば：

これは、nに各異なる素因数pについて \((1 - 1/p)\) を掛けることを意味します。指数（a）は関係なく、異なる素数の種類のみが重要です。

主な性質

オイラーの定理

オイラーの定理は、トーシェント関数を暗号学において極めて重要なものにしている主要な結果です：

これはフェルマーの小定理（nが素数の場合の特殊ケース）を一般化したものです。RSA暗号の数学的基礎となっています。

この電卓の使い方

1. 正の整数を入力： 入力フィールドに1から1,000,000までの数値を入力します。
2. クイック例を使用： 例ボタンをクリックして、素数、合成数、RSAスタイルの半素数などの典型的な値を試せます。
3. 結果を表示： 電卓が φ(n)、素因数分解、互いに素な比率、および検出された性質を表示します。
4. 互いに素なグリッドを探索： n ≤ 400 の場合、アニメーション表示されるグリッドでどの数がnと互いに素か確認できます。
5. トレンドチャートを確認： k = 1 から min(n, 100) までの φ(k) の変化を確認できます。

RSA暗号との関連

RSA暗号において、オイラーのトーシェント関数は中心的な役割を果たします：

1. 2つの大きな素数 p と q を選びます。n = p × q を計算します。
2. φ(n) = (p−1)(q−1) を計算します。
3. gcd(e, φ(n)) = 1 となる公開指数 e を選びます。
4. e × d ≡ 1 (mod φ(n)) となる秘密指数 d を計算します。

RSAの安全性は、nの因数分解を知らずに φ(n) を計算することの困難さに依存しています。もし攻撃者が効率的に φ(n) を計算できれば、RSAは破られてしまいます。

φ(n) の一般的な値

よくある質問

オイラーのトーシェント関数とは何ですか？

オイラーのトーシェント関数 φ(n)（オイラーのファイ関数とも呼ばれる）は、1からnまでの正の整数のうち、nと互いに素（既約）であるものの個数をカウントする関数です。2つの数は、最大公約数（GCD）が1であるときに互いに素であると言います。例えば、φ(12) = 4 です。これは、1、5、7、11の4つだけが12と互いに素だからです。

オイラーのトーシェント関数はどのように計算しますか？

φ(n)を計算するには： (1) nを素因数分解します。 (2) 積の公式を適用します：nの各異なる素因数pに対して φ(n) = n × ∏(1 − 1/p) となります。例えば、φ(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 は2つの大きな素数の積です。トーシェント φ(n) = (p−1)(q−1) は秘密鍵の計算に使用されます。復号指数dは e × d ≡ 1 (mod φ(n)) を満たす必要があります。nを因数分解してpとqを特定できなければ φ(n) を知ることはできず、dを計算することは事実上不可能です。

オイラーの定理とは何ですか？トーシェント関数とどう関係していますか？

オイラーの定理は、aとnが互いに素であれば、a^φ(n) ≡ 1 (mod 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) は常に偶数です。

2つの数が「互いに素」であるとはどういう意味ですか？

2つの整数aとbが互いに素（既約）であるとは、それらの最大公約数が1であることを意味し、共通の素因数を持たないことを指します。例えば、8と15は、どちらも素数ではありませんが、最大公約数が1なので互いに素です。トーシェント関数 φ(n) は、まさに何個の整数がnと互いに素であるかを数えます。

参考リソース

• オイラーのφ関数 - Wikipedia
• RSA暗号 - Wikipedia
• オイラーの定理 - Wikipedia