多倍長整数 中級

目次 (第4章〜第7章)

※ 第1章〜第3章は基礎編を参照。

  1. 第4章 高速乗算アルゴリズム

    Karatsuba、Toom-Cook 3/4/6/8、NTT、5-smooth NTT、squaring 最適化、閾値の設計

  2. 第5章 高速除算アルゴリズム

    Knuth Algorithm D、Burnikel-Ziegler、Newton 逆数反復、Exact Division、calx の実装

  3. 第6章 モジュラー算術

    Barrett 還元、Montgomery 乗算、CRT、高速冪剰余、定時間実装

  4. 第7章 整数 GCD アルゴリズム

    古典 Euclid、Binary GCD (Stein)、Lehmer、HGCD、Extended GCD、モジュラー逆元

最終更新: 2026-04-20