0Pricing
Cryptology Academy · レッスン

GCD、Eulerのトーシェント関数と数論入門

実際の暗号の問題にGCDとEulerのトーシェント関数を適用します。

「GCD、Eulerのトーシェント関数と数論入門」はCoddyKit上の無料Cryptology Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCryptology Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Cryptology Academyコースには全4レッスンが含まれています。

ようこそ

GCDとオイラーのトーシェント関数は、RSAやその他多くの公開鍵システムに欠かせない道具です。例を使って習得しましょう。

最大公約数（GCD）

GCD(a, b)は、aとbの両方を余りなく割り切る最大の整数です。GCD(12, 8) = 4です。GCD(a, m) = 1なら、aとmは互いに素、または相対的に素であるといいます。

ユークリッドの互除法

GCD(a, b) = GCD(b, a mod b)、基底ケースはGCD(a, 0) = aです。 GCD(48, 18): = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6 Python: import math; math.gcd(48, 18) → 6

拡張ユークリッドの互除法

拡張版では、ax + by = GCD(a,b)を満たす整数x、yを求めます。GCD(a,m)=1のとき、xはaのmod mにおけるモジュラー逆元です。RSAでは、この方法で秘密鍵を計算します。

オイラーのトーシェント関数 φ(n)

φ(n)は、1からnまでの整数のうち、nと互いに素なものの個数です。φ(10) = 4です。{1, 3, 7, 9}が10と互いに素だからです。任意の素数pについて、φ(p) = p-1です。

積のトーシェント関数

RSAでは、n = p×q（p、qは素数）です。φ(n) = φ(p)×φ(q) = (p-1)(q-1)となります。 例：p=5、q=11の場合、φ(55) = 4×10 = 40です。 このため、nを素因数分解するとφ(n)が分かり、RSAが破られます。

オイラーの定理

GCD(a,n)=1なら、a^φ(n) ≡ 1 (mod n)です。これはRSAの復号の数学的基盤です。e×d ≡ 1 (mod φ(n))なので、M = C^d mod nとなります。

RSAでのdの計算

e = 65537（RSAで一般的な公開指数）を選びます。拡張ユークリッドの互除法を使って、d = e^(-1) mod φ(n)を計算します。e×d mod φ(n) == 1であることを確認します。

Pythonでのトーシェント関数

def totient(n): from math import gcd return sum(1 for i in range(1, n+1) if gcd(i, n) == 1) # Fast for n=p*q: def rsa_totient(p, q): return (p-1)*(q-1)

Carmichaelのラムダ関数

現代のRSAでは、φ(n)の代わりにCarmichaelのラムダ関数λ(n) = lcm(p-1, q-1)を使います。これは、より小さい同値な法を与えます。PKCS#1 v2とNISTはλ(n)を推奨しています。

実用上のまとめ

GCD：eとφ(n)が互いに素であることを確認します。拡張ユークリッドの互除法：秘密鍵dを計算します。トーシェント関数：モジュラーべき乗で使う指数の群を決定します。この3つすべてが、RSAの鍵生成で使われます。

確認問題

p=7、q=11のRSAでは、φ(n)はいくつですか？

まとめ

すばらしい成果です！GCD、ユークリッドの互除法、オイラーのトーシェント関数が、あなたの道具箱に加わりました。次は、共通鍵暗号の構成要素であるXORとビット演算を学びます。

よくある質問

「GCD、Eulerのトーシェント関数と数論入門」レッスンは無料ですか？

はい。「GCD、Eulerのトーシェント関数と数論入門」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Cryptology Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Cryptology Academyコースには全4レッスンが含まれています。

「GCD、Eulerのトーシェント関数と数論入門」で何を学びますか？

実際の暗号の問題にGCDとEulerのトーシェント関数を適用します。 ブラウザで直接実行するハンズオンコードでCryptology Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Cryptology Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCryptology Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「GCD、Eulerのトーシェント関数と数論入門」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCryptology Academyレッスンでコードを書いて実行できますか？

はい。すべてのCryptology Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 2進数と16進数の基礎
  2. 剰余算の基礎
  3. 素数と素因数分解
  4. GCD、Eulerのトーシェント関数と数論入門
← Cryptology Academyに戻る