9.9 乗法に関する逆元と打ち消し
\(x\) の乗法に関する逆元 (multiplicative inverse) とは、次の関係を満たす \(x^{-1}\) を言う:
これから「逆元」は (関係に関する逆元ではなく) 乗法に関する逆元を意味すると定める。
例えば有理数を考えるとき、\(1/3\) は当然 \(3\) の逆元である。これは次の関係から分かる:
唯一の例外 \(0\) を除けば、任意の有理数 \(n/m\) には逆元 \(m/n\) が存在する。一方で、整数を考えるなら逆元を持つのは \(1\) と \(-1\) だけである。\(\mathbb{Z}_{n}\) を考えるとき、事態はさらに複雑になる。例えば、次の関係から \(\mathbb{Z}_{15}\) において \(2\) が \(8\) の逆元だと分かる:
しかし、\(\mathbb{Z}_{15}\) で \(3\) は逆元を持たない。この事実は背理法で証明できる: \(3\) に逆元 \(j\) が存在するなら、次の関係が成り立つ:
両辺に \(5\) を乗じると \(5 = 0\) という矛盾が得られる:
よって \(3\) の逆元 \(j\) は存在しない。
つまり \(15\) を法とする剰余算術では逆元を持つ整数もあれば持たない整数もある。奇妙な性質だと思うかもしれないが、この理由は簡単に説明できる。
9.9.1 互いに素
共通の素因数を持たない二つの整数を互いに素 (relatively prime, coprime) と言う。この条件は「\(1\) より大きい公約数を持たない」や「最大公約数が \(1\)」と等しい。
例えば \(\operatorname{gcd}(8, 15) = 1\) なので \(8\) と \(15\) は互いに素である。また、\(\operatorname{gcd}(3, 15) = 3 \neq 1\) なので \(3\) と \(15\) は互いに素でない。この事実は \(\mathbb{Z}_{15}\) で \(8\) が逆元を持ち \(3\) が逆元を持たない理由を説明する:
\(k \in [0..n)\) が \(n\) と互いに素なら、\(\mathbb{Z}_{n}\) で \(k\) は逆元を持つ1。
証明 \(k\) と \(n\) が互いに素なら、最大公約数の定義より \(\operatorname{gcd}(n, k) = 1\) が成り立つ。よって第 9.2.2 項で見た粉砕法を使えば、\(1\) を \(n\) と \(k\) の線形結合で表せる:
よって剰余算術の一般原理 (補題 9.7.1) から次を得る:
\(\operatorname{rem}(n, n) = 0\) と \(\operatorname{rem}(k, n) = k\) より次が分かる:
つまり \(\operatorname{rem}(t, n)\) は \(k\) の逆元である。 ■
補題 9.9.1 の証明からは、\(n\) と互いに素な任意の整数 \(k\) の \(\mathbb{Z}_{n}\) における逆元は粉砕法で見つかる係数を \(n\) で割った剰余に等しいと分かる。
もし逆元が存在するなら一意であるという事実も有用なので示しておく:
\(i\), \(j\) が \(\mathbb{Z}_{n}\) における \(k\) の逆元なら、\(i = j\) である。
証明
■
素数 \(p\) を法とする剰余算術は魅力的な特徴を持つ: 有理数全体の集合や実数全体の集合と同様に、\(\mathbb{Z}_{p}\) では \(0\) でない任意の整数が逆元を持つ。ただ、合成数を法とする剰余算術の厄介さが非常に大きいわけでもない ── 看護師が巨大な針を腕に刺す前に言う「ちょっとチクッとしますよ」と同じように聞こえてしまうかもしれないが。
9.9.2 打ち消し
実数が持つもう一つの素晴らしい特徴として、共通因数の打ち消し (cancel) が可能なことがある。具体的に言えば、実数 \(r\), \(s\), \(t\) が \(tr = ts\) を満たすとき、\(t \neq 0\) なら両辺から \(t\) を打ち消して \(r = s\) を得られる。一般に、\(\mathbb{Z}_{n}\) で打ち消しは可能でない。例えば、次の関係が成り立つ:
しかし、\(3\) を打ち消すと \(10\) と \(5\) が \(\mathbb{Z}_{n}\) で等しいという正しくない結論が得られてしまう。
項の打ち消しが不可能な場合がある事実は、\(\mathbb{Z}_{n}\) の算術と通常の算術の最も大きな相違点である。
\(\mathbb{Z}_{n}\) で整数 \(k\) が打ち消し可能 (cancellable) とは、全ての \(a, b \in [0..n)\) で次の関係が成り立つことを言う:
先ほどの例で共通する項が \(15\) と互いに素な整数なら、その項は逆元を乗じることで打ち消せる。つまり逆元を持つなら打ち消し可能である:
\(k\) が \(\mathbb{Z}_{n}\) で逆元を持つなら、\(k\) は打ち消し可能である。
一方で、\(3\) は \(15\) と互いに素ではない事実からは、\(3\) が \(\mathbb{Z}_{15}\) で打ち消し可能でないと分かる。等式 \(\text{(9.14)}\) を使った例と同じ議論を使うと、\(n\) と互いに素でない任意の \(k\) は \(\mathbb{Z}_{n}\) で打ち消し可能でないと示せる。
まとめると、次の事実が分かる:
任意の正整数 \(n\) と \(k \in [0..n)\) に対して、次の条件は同値である2:
- \(\operatorname{gcd}(k, n) = 1\)
- \(\mathbb{Z}_{n} \text{ で } k \text{ が逆元を持つ}\)
- \(\mathbb{Z}_{n} \text{ で } k \text{ が打ち消し可能である}\)
9.9.3 復号 (バージョン 2.0)
乗法に関する逆元は Turing の暗号の復号における鍵となる。具体的には、暗号化されたメッセージ \(\widehat{\vphantom{\scriptsize l} m}\) に秘密鍵 \(k\) の \(\mathbb{Z}_{n}\) における逆元 \(j\) を乗じると元のメッセージ \(m\) が得られる:
このとき秘密鍵 \(k\) の逆元が復号に必要なるものの、その値は粉砕法 (第 9.2.2 項) で簡単に計算できる ── \(k\) が逆元を持ちさえすれば。\(k\) は正かつ法 \(n\) 未満なので、\(k\) を法 \(n\) と互いに素とするには、素数の \(n\) を選択するのが簡単な方法である。
9.9.4 Turing の暗号 (バージョン 2.0) の解読
第二次大戦中のドイツも、気象報告をエニグマで強固に暗号化することはなかった。アイスランドの南岸で雨が降ったことを連合国が知ったところで何になるのか？ しかし驚くべきことに、この習慣は 1941 年に大西洋で起こった海戦においてイギリスに決定的な情報をもたらした。
問題だったのは、一部の気象報告が元々は大西洋に展開した U ボートからエニグマを使って送信されたものを転送していた事実である。このため、イギリスは暗号化されていない気象報告と、同じ気象報告をエニグマで暗号化したメッセージを入手できた。両者を比較することで、イギリスはその日にエニグマで使われている鍵を特定し、その日にエニグマで暗号化される通信を全て解読できた。現在、こういった手法は既知平文攻撃 (known-plaintext attack) と呼ばれる。
Turing の暗号 (バージョン 2.0) において既知平文攻撃がどのように動作するか見てみよう。ナチスがメッセージ \(m\) と、\(m\) を暗号化したメッセージ
を入手したとする。\(m\) は正で素数 \(n\) 未満だから、粉砕法を使って \(\mathbb{Z}_{n}\) における \(m\) の逆元 \(j\) を計算できる。すると
が成り立つので、ナチスは \(j \cdot \widehat{\vphantom{\scriptsize l} m} = k \quad (\mathbb{Z}_{n})\) を計算すれば秘密鍵を入手でき、全てのメッセージを解読可能になってしまう！
これは重大な脆弱性なので、仮想的な Turing の暗号 (バージョン 2.0) には実用上の価値はない。幸い、この暗号を考案した後も Turing は暗号学の研究を進めた。後に彼が達成したエニグマの解読は、(イギリス全体とは言わないにしても) 数千人のイギリス人の命を救ったことは間違いない。
9.9.5 Turing のその後
第二次世界大戦が終結してから数年後、Turing の家に強盗が入った。警察による捜査は、Turing の同性の元恋人が強盗犯と共謀したと結論付けた。そこで警察は彼を ── つまり Alan Turing を ── 逮捕した。当時のイギリスで同性愛は最大二年の懲役で罰せられる犯罪だったからである。Turing は同性愛をホルモン「治療」で治すことを宣告された: 彼は何度もエストロゲン注射を受け、胸が大きくなっていったという。
三年後、情報科学の創始者である Alan Turing は死亡した。彼の母親は、息子の伝記で彼の死を説明している。母親から何度も止めるように言われたにもかかわらず、Turing は自宅で化学治療を完了した。その後、彼女の最大の危惧は現実となった: リンゴを食べながらシアン化カリウムを扱っていたとき、誤ってシアン化カリウムを摂取して命を落とした。
しかし、Turing はその最期さえ謎に包まれている。彼の母親は自殺を罪と考える敬虔な女性だった。そして、他の伝記作家が指摘するように、Turing は毒を塗ったリンゴを食べることによる自殺をほのめかしていた。こういった点から考えると、Alan Turing は、情報科学という分野を開拓しイギリスを救った科学者は、母親に事故だと思わせる形で自らの命を奪ったようである。
Turing が 1939 年に公の場から姿を消す前に取り組んでいた最後のプロジェクトは、Riemann 予想 (Riemann conjecture) という数学の予想が成り立つかどうかを判定する精巧な数学的機械の構築だった。これは 1859 年に Bernhard Riemann が短い論文で初めて示した予想であり、現在の数学における最も有名な未解決問題の一つである。
無限幾何級数の和は次の公式で計算できる:
\(x = 1/2^{s}\), \(x = 1/3^{s}\), \(x = 1/5^{s}\), \(\ldots\) と素数 \(p\) に対する \(x = 1/p^{s}\) で置き換えると、次の等式が得られる:
左辺および右辺ごとに全て乗じると、次の等式が成り立つと示せる:
左辺の和は無限級数を全て乗じて算術の基本定理を利用すると得られる。例えば、項 \(1/300^{s}\) は最初の式から \(1/2^{2s}\) を取り、二つ目の式から \(1/3^{s}\) を、三つ目の式から \(1/5^{2s}\) を取ると得られる。Riemann は右辺に全ての素数が現れることに注目し、単純な左辺に注目すれば素数の性質を何か発見できるだろうと考えた。特に、彼は \(s\) を複素数としたときの左辺をゼータ関数 \(\zeta(s)\) と定義した。Riemann は \(\zeta(s) = 0\) となる \(s\) が素数の分布に関係していることに気が付き、次の有名な予想を提起した:
ゼータ関数 \(\zeta(s)\) の非自明な零点は全て複素数平面における直線 \(s = 1/2 + ci\) 上にある。
リーマン予想が証明されると、強い形の素数定理などの様々な命題が直ちに導かれる。
研究者たちは一世紀以上にわたって Riemann 予想を解決するべく精力的な研究を続けている。Riemann 予想はミレニアム問題の一つでもあり、解決者には Clay 研究所から百万ドルが授与される。