An Introduction to Number Theory with Cryptography（暗号で学ぶ整数論入門）

引用

Kraft, J. S., & Washington, L. C. (2018). An Introduction to Number Theory with Cryptography (2nd ed.). Chapman & Hall/CRC.

章の要約

本書は21の章と2つの付録からなる。各章は章のまとめ（Chapter Highlights）と問題の節で終わり、問題の節は演習、プロジェクト、コンピュータによる探究、「Check Your Understanding」（理解度チェック）の解答に分かれているが、すべての章に4つの部分がそろっているわけではない。出版社は、第2版ではRSAより前の基本的な暗号を前の章に移し、合同式の直後に暗号を教えられるようにしたと説明している。

第1章：序論

本書の4つの主題、すなわちディオファントス方程式、モジュラー算術、素数とその分布、暗号の予告編である。

第2章：整除性

整除性、素数が無限に存在するというユークリッドの定理とユークリッド本来の証明から始め、エラトステネスの篩と除法の原理（暗号への応用つき）を扱う。続いて最大公約数、ユークリッドの互除法とその拡張版、ほかの基数による表記、フェルマー数とメルセンヌ数に進む。

第3–4章：1次ディオファントス方程式、一意分解

第3章は ax + by = c を解き、切手問題を扱う。第4章は因数分解の出発点から始めて算術の基本定理を証明し、ユークリッドがそれをどう扱ったかを論じる。

第5章：一意分解の応用

一意分解を使って一連の結果を導く。無理数性の証明（2の平方根が無理数であることの4つの別証明を含む）、有理根定理、ピタゴラス数、平方の差、階乗の素因数分解、リーマンのゼータ関数（素数の逆数の和 1/p が発散することを含む）である。

第6章：合同式

定義と例、べき乗の剰余計算、整除判定法、1次合同式、中国剰余定理、法 m での分数、チェス盤上にクイーンを置く問題。

第7章：古典暗号

最初の暗号の章である。シフト暗号とアフィン暗号、ヴィジュネル暗号、転置式暗号、ストリーム暗号（ワンタイムパッドと線形フィードバックシフトレジスタ）、ブロック暗号、秘密分散、乱数の生成を扱う。

第8章：フェルマー、オイラー、ウィルソン

3つの古典的な定理を、それぞれ1つの節で扱う。RSAや原始根が拠って立つ古典的な結果である。

第9章：RSA

RSA暗号とデジタル署名。

第10章：多項式合同式

素数を法とする多項式、素数べきを法とする解、合成数を法とする場合。

第11章：位数と原始根

元の位数（フェルマー数とメルセンヌ数を含む）、原始根、小数展開（ミディーの定理を含む）、カードシャッフル、離散対数問題（ベビーステップ・ジャイアントステップ法と指数計算法）、そして原始根の存在証明。

第12章：暗号のさらなる応用

ディフィー–ヘルマン鍵交換、電話によるコイン投げ、メンタルポーカー、エルガマル公開鍵暗号。

第13章：平方剰余の相互法則

素数を法とする平方数と平方根、p を法とする平方根の計算、2次方程式、ヤコビ記号、平方剰余の相互法則の証明。

第14章：素数判定と因数分解

試し割りとフェルマー法による因数分解に始まり、素数判定（擬素数、ポクリントン–レーマー判定、AKS判定、フェルマー数とメルセンヌ数の判定）と因数分解（x² ≡ y²、RSAの指数を用いた因数分解、ポラードの p − 1 法、2次の篩）を扱い、電話によるコイン投げに戻る。

第15–17章：数の幾何、数論的関数、連分数

第15章はミンコフスキーの定理、2つおよび4つの平方数の和、ペル方程式をバースカラのチャクラヴァーラ法とともに扱う。第16章は完全数と乗法的関数を論じる。第17章は有理数による近似から、周期的な展開、整数の平方根、いくつかの無理数まで、連分数を展開する。

第18–19章：ガウス整数、代数的整数

第18章は複素数の算術、ガウスの既約元、除法、一意分解を築き、2つの平方数の和、ピタゴラス数、y² = x³ − 1 への応用を示す。第19章は2次体と代数的整数、単数、環 Z[√−2] と Z[√3]（リュカ–レーマー判定を含む）、一意分解でない場合に進む。

第20–21章：素数の分布、エピローグ：フェルマーの最終定理

第20章はベルトランの仮説とチェビシェフの近似的な素数定理を扱う。第21章はフェルマーの最終定理についてのエピローグで、楕円曲線とモジュラー性を紹介する。

付録

付録Aの「補足的な話題」は、証明とは何か（背理法を含む）、等比級数、数学的帰納法、パスカルの三角形と二項定理、フィボナッチ数、行列を扱う。付録Bは奇数番号の演習の解答とヒントである。

主要概念

第1–6章：基礎

• ユークリッドの互除法：最大公約数の計算法で、拡張版はディオファントス方程式や法に関する逆元に必要な係数を与える。
• 一意分解：すべての整数は本質的に1通りの仕方で素数の積になるという性質で、第5章の応用の土台となる。
• 合同式と中国剰余定理：m を法とする算術と、法の異なる合同式の組み合わせ。

第7–9章、第12章：暗号

• 古典暗号：シフト、アフィン、ヴィジュネル、転置、ストリーム、ブロックの各暗号と、秘密分散、乱数の生成。
• RSA：オイラーの定理に基づく公開鍵暗号とデジタル署名。
• ディフィー–ヘルマンとエルガマル：離散対数問題に基づく鍵交換と公開鍵暗号。

第10–14章：根、相互法則、素数判定

• 原始根と離散対数問題：そのべき乗が素数 p を法とするすべての単数をわたる元と、指数を求める問題。
• 平方剰余の相互法則とヤコビ記号：数が素数や合成数を法として平方数かどうかを判定する。
• 擬素数とAKS判定：フェルマー型の判定を通過する合成数と、多項式時間の素数判定法。

第15–21章：さらなる話題

• ミンコフスキーの定理：平方和についての結果を証明するための幾何学的な道具。
• 連分数とペル方程式：有理数による近似と、古典的なディオファントス方程式。
• ガウス整数と代数的整数：複素数や代数的数からなる環で、因数分解が一意でない場合も含めて研究される。

批判的分析

長所

• 暗号は付け足しではなく統合されている。 暗号は第1、7、9、12、14章に現れ、それが使う理論と織り合わされている。古典暗号は合同式の後、RSAはオイラーの定理の後、離散対数は原始根の後、因数分解法は素数判定の章に置かれる。出版社は、この版で暗号の扱いが増えたことを強調している。
• 豊富な練習材料。 出版社は、演習、プロジェクト、コンピュータによる探究を合わせて800問を超えるとし、すぐにフィードバックが得られる「Check Your Understanding」の問いと、奇数番号の問題の解答とヒントがあると述べている。各章の問題は演習、プロジェクト、コンピュータによる探究に分かれている。
• 初学者への配慮。 証明とは何か、帰納法、等比級数、二項定理、行列についての付録が、必要な予備知識を1か所にまとめている。出版社は、本書が優秀な高校生にも読みやすく独習にも適していると述べており、S. V. Nagaraj による初版の書評（2014年、IACRが公開）は、よく書かれて非常に読みやすく、補足資料が独習に役立つとしている。
• 標準的な授業を超える余地。 数の幾何、ガウス整数と代数的整数、素数の分布、フェルマーの最終定理についてのエピローグは、中核を終えたあとの選択肢を教員に与える。出版社も、従来のカリキュラムを超えて探究したい学生のために、やや高度な話題がいくつか含まれていると述べている。

短所

• 1学期では収まらない。 約600ページ（出版社の数字）、21章という分量は1つの学期では扱い切れないので、教員も独習者も取捨選択が必要になる。
• 暗号の範囲は限定的。 本書の暗号は数論的なもの、すなわち暗号方式、RSA、離散対数に基づく方式、鍵交換、コイン投げ、メンタルポーカーである。楕円曲線はフェルマーの最終定理のエピローグにしか現れないので、楕円曲線暗号やプロトコルの安全性を学びたい読者には別の本が必要になる。
• エピローグは概観。 第21章は3つの節（導入、楕円曲線、モジュラー性）からなり、フェルマーの最終定理の証明を取り巻く考え方を説明するが、それらを証明するわけではない。
• 解答は奇数番号の演習のみ。 残りの演習の解答は本には載っておらず、独習では不便である。
• 終盤でレベルが上がる。 ガウス整数と代数的整数の第18–19章は、単数や一意分解でないことといった環論的な考え方を導入するので、抽象代数に触れたことのない学生には一段上がったと感じられるかもしれない。

コースにおける位置づけ

このサイトの整数論の本のなかで、Kraft と Washington は古典的な整数論と現代の暗号を一緒に扱う1冊である。Burton の Elementary Number Theory は最も近い古典的な代替で、平方剰余の相互法則まで似た道筋をたどり、関わった数学者についての歴史的な節を備える。どちらを選ぶかは、おおむね、その歴史的な縦糸を好むか、暗号と計算の応用を好むかにかかっている。証明に慣れていない読者には、Silverman の A Friendly Introduction to Number Theory が実験と予想に基づくより穏やかな入口になり、Robin Wilson の Number Theory: A Very Short Introduction は公開鍵暗号にも触れるコンパクトな概観である。

さらに先へ進むには、Hardy と Wright の An Introduction to the Theory of Numbers が初等的・解析的整数論の古典的な概説書であり、Ireland と Rosen の A Classical Introduction to Modern Number Theory は抽象代数を前提とする大学院向けの教科書である。Kraft と Washington の最後の章（ガウス整数、代数的整数、素数の分布）は、その両方への橋渡しになる。

本書の使い方

出版社は、本書を学部の2年生から4年生向けに設計し、優秀な高校生にも読みやすく独習にも適していると述べている。当サイトは前提条件として、証明の経験と基礎的な代数を挙げている。付録Aは、証明とは何か、帰納法、二項定理を復習したい読者のためにある。

実用的な計画は次のとおりである。

• 整数論の中核： 第2–6章（整除性、1次ディオファントス方程式、一意分解、合同式）、続いて第8、11、13章（フェルマー、オイラー、ウィルソン、原始根、平方剰余の相互法則）。
• 暗号のコース： 第6章の直後に第7章、第8章の後にRSAの第9章、そして第12章と第14章は、それが依拠する原始根と相互法則の内容のあとに。
• 任意： 多項式合同式の第10章、数の幾何、数論的関数、連分数の第15–17章、代数的・解析的な拡張の第18–21章。
• 演習： 読みながら「Check Your Understanding」の問いを使い、巻末の解答を頼りに奇数番号の演習を解き、因数分解や素数判定のためのコンピュータによる探究には数式処理システムを使う。