📂整数論

合同方程式の根

アルゴリズム ¹

自然数$b,k,m$が$\gcd (b , m) = \gcd ( k , \phi (m) ) = 1$を満たす場合、合同方程式$x^{k} \equiv b \pmod{ m }$の解$x$は以下のようにして計算できる。

---

ステップ 1.

$\phi (m)$を計算する。

---

ステップ 2.

$ku - \phi (m) v =1$を満たす$u, v$を見つけ、両辺を$u$乗して$x^{ku} \equiv b^{u} \pmod{m}$を得る。

---

ステップ 3.

$b^{u} \pmod{ m }$を繰り返し二乗法で計算する。

説明

$\phi$はオイラーのφ関数で、乗法的性質を持っているから$m$の素因数分解が鍵となる。

知られているように、素因数分解には王道がなく、非常に難しい。巨大な素数$p,q$が存在して、$m=pq$とすると、まず$x := \phi (m)$を求めることから難しい。一見これは欠点に見えるかもしれないが、逆に$x$を暗号のように使うことができる。$k$と$m$が公開されていても、$m$の素因数分解を知らなければ$x$の計算は非常に難しい。したがって$m$の素因数分解を知っている人だけが$x$を知る資格があれば、素晴らしい暗号システムとなる。このような暗号システムをRSA暗号という。

このアルゴリズムは、非常に大きな素数を見つけることが実用的な価値を持つことを示している。

証明

$ku - \phi (m) v =1$を満たす整数解$u,v$の存在は保証されており、$ku = \phi (m) v + 1$であるため、 $$ x^{ku} \equiv x^{ \phi (m) v + 1 } \pmod{m} $$

オイラーのφ関数定理: $\gcd(x,m) = 1 \implies x^{ \phi (m) } \equiv 1 \pmod{m}$

$x^{ \phi (m) v + 1 } \equiv x^{ 1 } = b^{u} \pmod{m}$であるから、$b^{u}$だけを計算すればよい。$\gcd (x, m) = 1$を満たしていないが、このようにして得られた$x$は、与えられた合同方程式の解として全く問題がない。

$$ x^{k} = \left( b^{u} \right)^{k} = b^{uk} = b^{ 1+ \phi (m ) v} = b \cdot b^{ \phi (m ) v} $$ $\gcd (b , m) = 1$を仮定したので、次が成り立つ。 $$ x^{k} \equiv b \pmod{ m } $$

■