内容

目次

まえがき 第1章 安全で信頼できる情報 1.1 はじめに／1.2 最小非負剰余と時計算／1.3 暗号／1.4 誤りの検出と訂正／演習問題 第2章 モジュラ計算 2.1 mを法とする算術／2.2 モジュラ計算と暗号／2.3 mを法とする合同／2.4 文字から数へ／演習問題 第3章 mを法とする1次方程式 3.1 最大公約数／3.2 最大公約数を求める／3.3 ベズーの等式／3.4 べズーの等式の求解／3.5 ユークリッドの補題／3.6 1次ディオファントス方程式の解／3.7 1次合同式の操作と解法／演習問題 第4章 Zにおける素因数分解の一意性 4.1 素因数分解の一意性／4.2 帰納法／4.3 算術の基本定理／4.4 除法の原理／4.5 整列原理／演習問題 第5章 環と体 5.1 群，可換環，体，単元／5.2 群と環の基本的な性質／5.3 単元と体／5.4 イデアル／5.5 コセットとmを法とする整数／5.6 Z_mは可換環／5.7 Z/mZの完全代表系／5.8 Z/mZが体となる場合／演習問題 第6章 多項式 6.1 基本概念／6.2 除法の原理／6.3 ダランベールの定理／演習問題 第7章 行列とハミング符号 7.1 行列とベクトル／7.2 誤り訂正・検出符号／7.3 (7,4)-ハミング符号：単一誤り訂正符号／7.4 (8,4)-ハミング符号／7.5 これらの符号はなぜ機能するのか？／演習問題 第8章 位数とオイラーの定理 8.1 元の位数／8.2 フェルマーの小定理／8.3 オイラーの定理／8.4 二項定理とフェルマーの小定理／8.5 法mでの高次の冪の求め方／演習問題 第9章 RSA暗号と素数 9.1 RSA暗号／9.2 RSAはなぜ有効なのか？／9.3 署名／9.4 対称鍵暗号と非対称鍵暗号／9.5 大きな素数の存在／9.6 大きな素数の見つけ方／9.7 a-擬素数テスト／9.8 強a-擬素数テスト／演習問題 第10章 群，コセット，ラグランジュの定理 10.1 群／10.2 部分群／10.3 有限な巡回部分群の部分群／10.4 コセット／10.5 ラグランジュの定理／10.6 非可換群／演習問題 第11章 連立合同式の解法 11.1 「線形結合」による2本の連立合同式の解法／11.2 3本以上の連立合同式の解法／11.3 RSA暗号への応用／11.4 一般の連立合同式の解法／11.5 2本の合同式の解法／11.6 3本以上の合同式／11.7 モニックではない連立1次合同式／演習問題 第12章 準同型写像とオイラーのφ関数 12.1 オイラーのφ関数の公式／12.2 写像について／12.3 環準同型写像／12.4 準同型の基本定理／12.5 群準同型写像／12.6 環の直積と中国式剰余定理／12.7 単元とオイラーの公式／演習問題 第13章 巡回群と暗号 13.1 巡回群／13.2 離散対数／13.3 Diffie–Hellman鍵交換／13.4 エルガマル暗号／13.5 実用上のDiffie–Hellman／13.6 アーベル群の指数／13.7 原始根定理／13.8 U_mの指数／13.9 Pohlig–Hellmanアルゴリズム／13.10 シャンクスのBaby Step-Giant Stepアルゴリズム／演習問題 第14章 コセットの応用 14.1 群準同型写像，コセット，非同次連立方程式／14.2 ハミング符号／14.3 オイラーの定理／14.4 確率的合成数判定／14.5 強カーマイケル数は存在しない／14.6 ボネの定理／演習問題 第15章 リード–ソロモン符号入門 15.1 設定／15.2 リード–ソロモン符号の符号化／15.3 復号／15.4 例／演習問題 第16章 Blum–Goldwasser暗号 16.1 バーナム暗号／16.2 Blum–Blum–Shub疑似乱数生成器／16.3 Blum–Goldwasser暗号／16.4 BBS数列の周期／16.5 最終項からのBBS数列の復元／16.6 Blum–Goldwasser暗号の安全性／16.7 Blum–Goldwasser暗号の実装／演習問題 第17章 二次篩法による素因数分解 17.1 試し割り法／17.2 二次篩法の基本的な考え方／17.3 フェルマーの素因数分解法／17.4 二次篩法／17.5 離散対数の指数計算法／演習問題／付録：フェルマー法と試し割り法の比較 第18章 多項式と有限体 18.1 最大公約多項式／18.2 既約多項式への因数分解／18.3 F[x]のイデアル／18.4 コセットと商環／18.5 拡大体の構成／演習問題 第19章 リード–ソロモン符号II 19.1 1の冪根と離散フーリエ変換／19.2 8元体／19.3 F_8上のリード–ソロモン符号／19.4 F_13上の例／演習問題 参考文献 訳者あとがき 索引