代数学と符号暗号理論 - Pythonによる実装 -

寺杣友秀法政大教授理博著

符号・暗号理論の基礎となる初等整数論から始め，Pythonによる演習を入れた。

ジャンル

発行年月日: 2025/10/31

判型: A5

ページ数: 202ページ

ISBN: 978-4-339-06135-2

在庫あり

2営業日以内に出荷致します。

定価

3,300円(本体3,000円+税)

カートに入れる

購入案内

内容紹介
まえがき
目次
著者紹介
広告掲載情報

【書籍の紹介】
代数学を学んだことがない読者の方々にも符号理論，暗号理論の根本原理を理解していただけるよう丁寧に，かつ議論が明解になるように心がけて執筆しました。また，変数の扱いが容易であり，扱える整数の大きさにほとんど制限がないPythonによる演習を入れることで，紹介した理論が応用に耐えうるものかどうかを実感していただけるようにしています。

1章「初等整数論」ではその後の2章「暗号理論」，3章「符号理論」で共通に使われる代数的な道具を準備します。環論においてはイデアルを用いた統一的扱いが標準的ですが，後で使う場面を考えて，ユークリッドアルゴリズムおよびそれを拡張した拡張ユークリッドアルゴリズムを議論の中心として説明しました。また符号理論においては素体上の多項式の扱い（例えば割り算アルゴリズムなど）が中心部分を占めているので，これについては詳しく説明しました。
2章で扱う「暗号理論」は伝えたい人にのみ理解でき、第三者にはわからないような形で情報を送るために考えられた理論です。古くは戦争において敵に知られないように作戦をつたえる目的で用いられました。現在ではクレジットカードの番号や、パスワードを送るときに使われています。暗号を解読する理論も研究され、さまざまな種類の暗号があります。
3章に出てくる「符号理論」はあまりおなじみではない方もいらっしゃるかもしれません。復元に使うための情報を送る情報に追加して、送信の途中で情報に傷がついても復元できるようにする理論です。身近な例としては、QRコードにつかわれています。実際にQRコードの一部に小さいロコなどを埋め込んで、その部分を見えなくしても正常に読み込めるものを見かけた人がいるかもしれません。
最後にPythonのプログラミングの基礎と本文中に書ききれなかった定理の証明などを追記しました。

【著者からのメッセージ】
本書は抽象的な定義から始まる代数学の教科書とは異なり、代数学を学んでいない理工学部学生にとってもなじみの深い具体的なものから始まります。よく使われているPythonでプログラミングをしながら読み進めれば理解が深まることと思います。

☆発行前情報のため，一部変更となる場合がございます

本書は筆者が法政大学理工学部で代数学を学んだことのない学生を対象とした講義録とゼミで用いた資料が基になっている。本書は代数に関する知識を仮定せず，一般教養の微積分と線型代数の初歩の基礎的知識は仮定するが，線型代数で用いられる言葉は復習の意味も込めて最初から説明した。しかし線型代数に関するいくつかの主要な定理には証明は付けずに説明したので，なぜそのような定理が成り立つかについては，適宜教科書を参照して復習をすることをおすすめする。執筆にあたっては，できるだけ丁寧に，かつ議論が明解になるように心がけた。場合によっては厳密な証明が理解の妨げになることも考慮し，厳密性を省いたところもある。

暗号理論，符号理論は現在も進化をとげており，実際に使用される場面では本書に書かれているものにさらに工夫を加えているものが多いが，根本原理は本書で理解できるものと思っている。

また，ある程度の大きな数を扱わないと，紹介した理論が応用に耐えうるものかどうかを実感しにくい場面も多々あるので，PC上で実際に動くPythonによる演習を入れることとした。Pythonを使う利点としては，変数の扱いが容易である（あいまいな記述も許す）こと，扱える整数の大きさにほとんど制限がないことが挙げられる。これらの点がプログラミング初心者にとってはとっつきやすいだろう。Pythonはいったん機械語に翻訳されてから実行されるので，実行速度は高速である。逆に実際に自分でプログラムを書く立場で考えると，思わぬミスを発見し，修正するのに苦心するところが同時に欠点でもある。またオブジェクト志向型プログラムの書き方をすることも可能であり，いくつかの理論を組み合わせて全体を構成する本書の進め方と合致している面も見逃せないところである。

本書について，実際に使用して使いにくい点，未熟な点などをご指摘下さった松本圭司氏には，この場をもって感謝の意を述べさせていただきたい。

本書は大きく分けて代数的な準備の部分の「1章初等整数論」とその後に続く「2章暗号理論」と「3章符号理論」である。「初等整数論」ではその後の「暗号理論」，「符号理論」で共通に使われる代数的な道具を準備する。環論においてはイデアルを用いた統一的扱いが標準的であるが，後で使う場面を考えて，ユークリッドアルゴリズムおよびそれを拡張した拡張ユークリッドアルゴリズムを議論の中心として説明した。また符号理論においては素体上の多項式の扱い（例えば割り算アルゴリズムなど）が中心部分を占めているので，これについては詳しく説明した。

2025年8月
寺杣友秀

☆発行前情報のため，一部変更となる場合がございます

1．初等整数論
1.1　約数，倍数とユークリッドアルゴリズム
　1.1.1　約数，倍数，素数
　1.1.2　最大公約数，最小公倍数，素因数分解
　1.1.3　整数とユークリッドアルゴリズム
　1.1.4　拡張ユークリッドアルゴリズム
　1.1.5　演習：拡張ユークリッドアルゴリズム
1.2　剰余系
　1.2.1　剰余類の定義
　1.2.2　剰余類の計算
　1.2.3　中国の補題
　1.2.4　105 減算
1.3　素体とフェルマーの定理
　1.3.1　素体における逆元の計算
　1.3.2　演習：素体における逆数
　1.3.3　素数に関するフェルマーの定理
　1.3.4　素数の積に関するフェルマーの定理
1.4　フェルマーの判定法と素数定理
　1.4.1　素数の密度
　1.4.2　Nまでの数で最初のk個の素数で割り切れない確率
　1.4.3　素数判定
　1.4.4　剰余類の高速べき計算
　1.4.5　演習：高速べき計算と素数判定
1.5　素体上の多項式
　1.5.1　体上の多項式
　1.5.2　体上の多項式の割り算アルゴリズム
　1.5.3　演習：素体上の多項式
　1.5.4　演習：多項式と代入
　1.5.5　体と多項式での約数，倍数
　1.5.6　多項式のユークリッドアルゴリズム
　1.5.7　演習：多項式のユークリッドアルゴリズム
　1.5.8　多項式における合同類別
1.6　既約多項式とガロア体
　1.6.1　既約多項式と素因子分解の存在
　1.6.2　ガロア体
　1.6.3　演習：ガロア体
　1.6.4　最小多項式
　1.6.5　原始根の存在定理
　1.6.6　ガロア体のフロベニウス写像
　1.6.7　演習：ガロア体を係数とする多項式

2．暗号理論
2.1　暗号理論の概要
　2.1.1　暗号化と復号
　2.1.2　公開鍵暗号
　2.1.3　鍵共有と鍵の配送問題
2.2　RSA暗号
　2.2.1　フェルマーの定理とRSA暗号
　2.2.2　現在のRSAの問題と世界記録
　2.2.3　演習：RSA暗号，鍵の生成と復号
2.3　ディフィー・ヘルマン鍵共有
　2.3.1　離散対数問題
　2.3.2　ディフィー・ヘルマン鍵共有のプロトコル
　2.3.3　エルガマル暗号
　2.3.4　演習：ディフィー・ヘルマン鍵共有とエルガマル暗号
2.4　楕円曲線
　2.4.1　楕円曲線の定義
　2.4.2　座標を使った楕円曲線の和の計算
　2.4.3　素体上の楕円曲線の和の例
　2.4.4　演習：有限体上の楕円曲線
　2.4.5　楕円曲線上の点の自然数倍の高速計算
　2.4.6　演習：楕円曲線の点の高速倍数計算
2.5　楕円曲線暗号
　2.5.1　楕円曲線ディフィー・ヘルマン鍵共有
　2.5.2　楕円曲線エルガマル暗号
　2.5.3　一般の整数から楕円曲線の点を作る
　2.5.4　演習：楕円曲線ディフィー・ヘルマン鍵共有
2.6　電子署名
　2.6.1　電子署名に必要な要件
　2.6.2　電子署名の概要
　2.6.3　電子署名の準備（ハッシュ）
　2.6.4　電子署名の実際
　2.6.5　RSA暗号による実装

3．符号理論
3.1　体とベクトル空間
　3.1.1　行列の計算
　3.1.2　抽象ベクトル空間
　3.1.3　部分ベクトル空間と次元
3.2　ベクトル空間と線型写像
　3.2.1　線型写像と行列
　3.2.2　同型と基底，像と核
　3.2.3　行列式
　3.2.4　行列式と逆行列，基底
3.3　誤り訂正符号
　3.3.1　ブロック符号
　3.3.2　ハミング距離
　3.3.3　誤り訂正の原理
　3.3.4　線型符号と最小ハミング長さ
　3.3.5　シングルトン限界
　3.3.6　生成行列と組織的符号化
　3.3.7　(7,4,3)ハミング符号と誤り訂正
　3.3.8　誤り検出とシンドローム行列
3.4　リード・ソロモン符号
　3.4.1　符号多項式とリード・ソロモン符号
　3.4.2　リード・ソロモン符号の例
　3.4.3　リード・ソロモン符号の最小ハミング長さ
　3.4.4　リード・ソロモン符号の組織的符号化
　3.4.5　演習：リード・ソロモン符号の組織的符号化
　3.4.6　（参考）点評価型のリード・ソロモン符号
3.5　リード・ソロモン符号の誤り訂正
　3.5.1　シンドローム多項式
　3.5.2　変形拡張ユークリッドアルゴリズムと誤り位置多項式
　3.5.3　誤り多項式の計算
　3.5.4　演習：リード・ソロモン符号の誤り訂正
3.6　巡回符号，BCH符号
　3.6.1　巡回符号
　3.6.2　BCH符号
3.7　BCH符号の誤り訂正アルゴリズム
　3.7.1　シンドローム多項式
　3.7.2　誤り位置多項式，誤り多項式の計算

付録A：Pythonによるプログラミング
A.1　Pythonの基本的な使い方
　A.1.1　プログラムを始める前の一般的な常識
　A.1.2　Spyderのインストール
　A.1.3　プログラム環境
　A.1.4　言語Pythonについての一般的注意
　A.1.5　デバッグについて
A.2　Pythonの文法の基本
　A.2.1　変数，リスト，条件分岐
　A.2.2　リストの使い方
　A.2.3　整数の割り算
　A.2.4　インデントと条件分岐if文，else文，elif文
　A.2.5　ループを制御するfor文，while文，break文
A.3　関数，クラス，インポート
　A.3.1　関数
　A.3.2　クラス
　A.3.3　演算子オーバロード
　A.3.4　データのファイルへの保存

付録B：群論と原始根
B.1　群と巡回群
　B.1.1　群の定義
　B.1.2　元の位数，同型と巡回群
　B.1.3　原始根の存在
B.2　原始根の存在定理

付録C：楕円曲線の和についての結合法則
C.1　射影幾何学と同次多項式のアファイン化
C.2　射影幾何における楕円曲線
C.3　射影幾何における楕円曲線の和
C.4　結合法則について

例題解答
索引

寺杣友秀（テラソマトモヒデ）

代数学の一分野である代数幾何の研究をしてきました。この６，７年前から理工学部学生に代数学の初歩とそれを応用した「暗号理論」「符号理論」を教えています。最近思っていることは、プログラミングをしながらでも数学的センスが磨かれるのではないかということです。まず、大きな枠組みを組み立てることが重要です。どのようにすすめれば目的を達成できるかを考えることです。また、ひとは間違いをする生き物です。計画を実行するときに、間違いを起こしにくい方法で、常に確認をしながら進める習慣が数学の問題を解くことと同様に大切です。
上のこととは全く関係ありませんが、最近（軽い）ジム通いを始めました。