基礎から学ぶ整数論

【書籍の紹介】 本書では，RSA 暗号の原理の理解を目標とし，RSA 暗号を求めるのに必要となる，さまざまな基礎的な整数論の定理，演算手法を学びます。 1 章では，暗号の基礎知識とRSA 暗号の導入，数と式について学びます。読者の皆さんは，ここではRSA暗号の仕組みや特徴を学び，「なぜそのようなことが可能なのか」という疑問をもつことが大切で，理解できない部分があっても，まったく問題ありません。 2 章では，4 章の一次不定方程式，5 章の合同式を解くのに重要なキーワードとなる最小公倍数と最大公約数について学びます。 3 章では，最大公約数を効率的に求めることのできるユークリッドの互除法について学びます。このアルゴリズムは，4 章で学ぶ一次不定方程式の解法アルゴリズム4.1（拡張ユークリッドの互除法アルゴリズム）につながります。 4 章では，7 章のRSA 暗号を理解するのに必要となる一次不定方程式の解法を学びます。この方程式は，3 章3.3 節で学んだユークリッドの互除法アルゴリズムから導出される「拡張ユークリッドの互除法アルゴリズム」で求めることができます。 5 章では，合同の基本的な演算から合同式の解法について学びます。合同の考え方は，7 章のRSA 暗号において，暗号文を生成したり解読するのに必要となります。 6 章では，RSA 暗号を理解するうえで必要となる，素数にまつわるさまざまな定理や関数について学びます。 最後の7章では，6 章までに学んだ整数論の知識を基に，公開鍵暗号の一つのRSA暗号の原理を理解します。ユーザは，秘密鍵（secret key）SK から公開鍵（public key）PK を作成し，PK を自分の鍵として公開し，SK を自分だけが知っている値として秘密にしておきます。これらの鍵を求めるのに，巨大な素数や素因数分解などに関する知識が必要となりますが，6章までを習得していれば，1章では疑問だらけだったRSA暗号が，スラスラと計算でき原理も理解できるようになるはずです。 【読者へのメッセージ】 みなさんのなかに，今までに整数論を学ぼうとして挫折した人はいませんか？あまりにも難しい定理が急に出てきて「あぁ，もうだめだ・・・」などと感じたことがありませんか？筆者たちもその一人かもしれません。そんな筆者たちの経験をもとに，この内容から書いてあれば数学を専門としない読者にもわかるかもしれないと，構想(妄想か？) を立て書いたつもりです。本書の中には難しい証明もあるかもしれません。でも，そんなものは読み飛ばしても，全体の理解には問題はありませんので安心してください。この本を小説のように(?!) 読むことにより，「整数論って何だろう，RSA暗号ってどんな方式なんだろう」を理解できることを願っています。