訳者まえがき
序文
目次
アルゴリズム一覧
図表の一覧
はじめに
１　シクロヘキサン，暗号，コード，計算機代数
　１.１　シクロヘキサンの立体配座
　１.２　RSA暗号系
　１.３　分散データ構造
　１.４　計算機代数システム
第 Ⅰ 部　Euclid
２　基本的なアルゴリズム
　２.１　整数の表現と足し算
　２.２　多項式の表現と足し算
　２.３　掛け算
　２.４　余りを伴う割り算
　注解
　練習問題
３　Euclidのアルゴリズム
　３.１　Euclid整域
　３.２　拡張Euclidアルゴリズム
　３.３　ℤとF[x]に対する計算量の解析
　３.４　gcdの（非）一意性
　注解
　練習問題
４　Euclidのアルゴリズムの応用
　４.１　モジュラ算
　４.２　Euclidアルゴリズムによるモジュラ逆元
　４.３　繰り返し平方
　４.４　Fermatの小定理によるモジュラ逆元
　４.５　線形Diophantine方程式
　４.６　連分数とDiophantine近似
　４.７　暦
　４.８　音階
　注解
　練習問題
５　モジュラアルゴリズムと補間
　５.１　表現の変換
　５.２　値を計算することと補間
　５.３　応用：秘密の共有
　５.４　中国剰余アルゴリズム
　５.５　行列式のモジュラ計算
　５.６　Hermite補間
　５.７　有理関数の復元
　５.８　Cauchy補間
　５.９　Padé近似
　５.１０　有理数の復元
　５.１１　部分分数分解
　注解
　練習問題
６　終結式と最大公約数の計算
　６.１　Euclidのアルゴリズムの係数の増大化
　６.２　Gaußの補題
　６.３　終結式
　６.４　モジュラgcdアルゴリズム
　６.５　F[x，y]におけるモジュラgcdアルゴリズム
　６.６　ℤ[x]におけるMignotteの因子の上界とモジュラgcdアルゴリズム
　６.７　小さい素数 のモジュラgcdアルゴリズム
　６.８　応用：平面曲線の交わり
　６.９　0でないことの保存といくつかの多項式のgcd
　６.１０　部分終結式
　６.１１　モジュラ拡張Euclidアルゴリズム
　６.１２　擬除算と原始的Euclidアルゴリズム
　６.１３　実装
　注解
　練習問題
７　応用：BCH符号での符号化
　注解
　練習問題
第II部　Newton
８　高速乗算
　８.１　Karatsubaの乗算アルゴリズム
　８.２　離散Fourier変換と高速Fourier変換
　８.３　SchönhageとStrassenの乗算アルゴリズム
　８.４　ℤ[x]およびR[x，y]における乗算
　注解
　練習問題
９　Newton反復法
　９.１　Newton反復法による余りを伴う除算
　９.２　一般Taylor展開と基数の転換
　９.３　形式的微分とTaylor展開
　９.４　Newton反復法による代数方程式の解法
　９.５　整数べき根の計算
　９.６　Newton反復法，Julia集合およびフラクタル
　９.７　高速算術の実装
　注解
　練習問題
１０　高速多項式評価と補間法
　１０.１　高速多数点評価
　１０.２　高速補間法
　１０.３　高速中国剰余
　注解
　練習問題
１１　高速Euclidアルゴリズム
　１１.１　多項式についての高速Euclidアルゴリズム
　１１.２　Euclidアルゴリズムによる部分終結式
　注解
　練習問題
１２　高速線形代数
　１２.１　Strassenの行列乗算
　１２.２　応用：多項式の高速モジュラ合成
　１２.３　線形再帰点列
　１２.４　Wiedemannのアルゴリズムとブラックボックス線形代数
　注解
　練習問題
１３　Fourier変換と画像圧縮
　１３.１　連続的および離散的Fourier変換
　１３.２　音声と画像の圧縮
　注解
　練習問題
第III部　Gauß
１４　有限体上の多項式の因数分解
　１４.１　多項式の因数分解
　１４.２　異なる次数の因数分解
　１４.３　等しい次数の因数分解：CantorとZassenhausのアルゴリズム
　１４.４　完全な因数分解のアルゴリズム
　１４.５　応用：根の探索
　１４.６　平方自由因数分解
　１４.７　反復Frobeniusアルゴリズム
　１４.８　線形代数をもとにしたアルゴリズム
　１４.９　既約性判定と既約多項式の構成
　１４.１０　円分多項式とBCH符号の構成
　注解
　練習問題
１５　Hensel持ち上げと多項式の因数分解
　１５.１　ℤ[x]上とℚ[x]上の因数分解：基本的アイデア
　１５.２　ある因数分解アルゴリズム
　１５.３　FrobeniusとChebotarevの密度定理
　１５.４　Hensel持ち上げ
　１５.５　多因子のHensel持ち上げ
　１５.６　Hensel持ち上げを用いた因数分解：Zassenhausのアルゴリズム
　１５.７　実装
　注解
　練習問題
１６　格子上の短いベクトル
　１６.１　格子
　１６.２ Lenstra，Lenstra ＆ Lovászの基底簡約アルゴリズム
　１６.３　基底の簡約のコストの評価
　１６.４　短いベクトルから因数分解へ
　１６.５　ℤ[x]上の多項式時間因数分解アルゴリズム
　１６.６　多変数多項式の因数分解
　注解
　練習問題
１７　基底の簡約の応用
　１７.１　ナップザック型暗号系の破れ
　１７.２　擬似乱数
　１７.３　連立Diophantine近似
　１７.４　Mertensの反証
　注解
　練習問題
第Ⅳ部　Fermat
１８　素数判定
　１８.１　整数の乗法位数
　１８.２　Fermatテスト
　１８.３　強擬素数性判定テスト
　１８.４　素数発見
　１８.５　SolovayとStrassenのテスト
　１８.６　素数判定の計算量
　注解
　練習問題
１９　整数の因数分解
　１９.１　因数分解の挑戦
　１９.２　素朴な方法
　１９.３　PollardとStrassenの方法
　１９.５　Dixonのランダム平方法
　１９.６　Pollardのp—1法
　１９.７　Lenstraの楕円曲線法
　注解
　練習問題
２０　応用：公開鍵暗号系
　２０.１　暗号系
　２０.２　RSA暗号
　２０.３　Diffle—Hellmanの鍵交換プロトコル
　２０.４　ElGamal暗号系
　２０.５　Rabinの暗号系
　２０.６　楕円曲線暗号
　注解
　練習問題
第Ⅴ部　Hilbert
２１.　Gröbner基底
　２１.１多項式イデアル
　２１.２　単項式順序と多変数多項式の余りを伴う割り算
　２１.３　単項式イデアルとHilbertの基底定理
　２１.４　Gröbner基底とS多項式
　２１.５　Buchbergerのアルゴリズム
　２１.６　幾何への応用
　２１.７　Gröbner基底の計算量
　注解
　練習問題
２２　記号的積分
　２２.１　微分代数
　２２.２　Hermiteの方法
　２２.３　Lazard，Rioboo，Rothstein，Tragerの方法
　２２.４　超指数積分：AlmkvistとZeilbergerのアルゴリズム
　注解
　練習問題
２３　記号的和
　２３.１　多項式の和
　２３.２　調和数
　２３.３　最大階乗分解
　２３.４　超幾何和：Gosperのアルゴリズム
　注解
　練習問題
２４　応用
　２４.１　Gröbner証明システム
　２４.２　Petri　網
　２４.３　等式証明とアルゴリズムの分析
　２４.４　シクロヘキサン再考
　注解
　練習問題
付録
２５　基本的事項
　２５.１　群
　２５.２　環
　２５.３　多項式と体
　２５.４　有限体
　２５.５　線形代数
　２５.６　有限確率空間
　２５.７　「大きいO」記号
　２５.８　計算量理論
　注解
図版の出典
引用句の出典
参考文献
索引