暗号技術におけるモジュラー逆元の計算

整数論

暗号技術で用いられるモジュラー逆元の概念を理解し、拡張ユークリッドの互除法を用いて具体的なモジュラー逆元を計算する能力を養います。これにより、整数論が情報セキュリティの基盤であることを実践的に学びます。

暗号技術におけるモジュラー逆元の計算

情報セキュリティにおいて、公開鍵暗号システム（例：RSA）では、鍵の生成や暗号化・復号のプロセスでモジュラー逆元が重要な役割を果たします。整数 $a$ のモジュラス $m$ における逆元 $a^{-1}$ とは、$a \cdot a^{-1} \equiv 1 \pmod{m}$ を満たす整数 $a^{-1}$ のことです。ただし、$0 < a^{-1} < m$ であるとします。モジュラー逆元が存在するのは、$a$ と $m$ が互いに素である場合（すなわち、$\text{gcd}(a, m) = 1$ の場合）に限られます。

以下の問いに答えなさい。

$a=7$ のモジュラス $m=26$ における逆元 $a^{-1}$ を求めなさい。
$a=14$ のモジュラス $m=26$ における逆元は存在しますか？理由とともに答えなさい。

解答を見る

1. $a=7$ のモジュラス $m=26$ における逆元 $a^{-1}$ を求める

まず、$a=7$ と $m=26$ が互いに素であるかを確認します。ユークリッドの互除法を用いて最大公約数 ($\text{gcd}$) を計算します。

$26 = 3 \cdot 7 + 5$
$7 = 1 \cdot 5 + 2$
$5 = 2 \cdot 2 + 1$
$2 = 2 \cdot 1 + 0$

$\text{gcd}(7, 26) = 1$ であるため、$a=7$ のモジュラス $m=26$ における逆元は存在します。

次に、拡張ユークリッドの互除法を用いて、$7x + 26y = 1$ を満たす整数 $x, y$ を求めます。この $x$ が $7$ のモジュラス $26$ における逆元となります。

上記のユークリッドの互除法の計算を逆向きにたどります。 $1 = 5 - 2 \cdot 2$ （式3より） $1 = 5 - 2 \cdot (7 - 1 \cdot 5)$ （式2の $2$ を代入） $1 = 5 - 2 \cdot 7 + 2 \cdot 5$ $1 = 3 \cdot 5 - 2 \cdot 7$ $1 = 3 \cdot (26 - 3 \cdot 7) - 2 \cdot 7$ （式1の $5$ を代入） $1 = 3 \cdot 26 - 9 \cdot 7 - 2 \cdot 7$ $1 = 3 \cdot 26 - 11 \cdot 7$

この式から、$3 \cdot 26 - 11 \cdot 7 = 1$ が導かれます。これを合同式で考えると、$-11 \cdot 7 \equiv 1 \pmod{26}$ となります。 $x = -11$ は $7$ の逆元の一つですが、$0 < a^{-1} < m$ という条件を満たす必要があります。 $-11 \pmod{26}$ を計算すると、$(-11 + 26) \pmod{26} = 15 \pmod{26}$ となります。

したがって、$a=7$ のモジュラス $m=26$ における逆元 $a^{-1}$ は 15 です。

（検算: $7 \cdot 15 = 105$、$105 \div 26 = 4$ 余り $1$ なので、$7 \cdot 15 \equiv 1 \pmod{26}$ は正しい。）

2. $a=14$ のモジュラス $m=26$ における逆元が存在するかどうか

逆元が存在するためには、$a$ と $m$ が互いに素である必要があります。 $a=14$ と $m=26$ の最大公約数を計算します。

$26 = 1 \cdot 14 + 12$
$14 = 1 \cdot 12 + 2$
$12 = 6 \cdot 2 + 0$

$\text{gcd}(14, 26) = 2$ となります。 $2 \neq 1$ であるため、$14$ と $26$ は互いに素ではありません。

結論: $a=14$ のモジュラス $m=26$ における逆元は 存在しません。 理由: $a$ と $m$ の最大公約数が $1$ ではない（互いに素ではない）ためです。