多倍長整数演算

Arbitrary-Precision Integer Arithmetic

概要

多倍長整数の表現、基本演算、高速乗算・除算、モジュラー算術、GCD、素数判定、因数分解、数論関数まで。全13章で扱う。

レベル別

  • 入門（1章）

    多倍長整数入門

  • 基礎（2章）

    多倍長整数の表現 / 多倍長整数の基本演算

  • 中級（4章）

    高速乗算アルゴリズム / 高速除算アルゴリズム / モジュラー算術 / 整数 GCD アルゴリズム

  • 上級（6章）

    不均衡 Toom-Cook 乗算 / NTT 実装比較 / 素数判定 / 整数因数分解 / Block Lanczos / 数論関数

全章一覧

入門 (1 章)

  1. 第1章 多倍長整数入門

    64 bit の壁、多倍長整数が必要な場面、表現の選択肢、メモリ管理、主要ライブラリの概観

基礎 (2 章)

  1. 第2章 多倍長整数の表現

    リム配列、符号絶対値と 2 の補数、エンディアン、SBO、calx の設計選択

  2. 第3章 多倍長整数の基本演算

    加減乗除のスクールブック実装、キャリー伝播、比較、文字列変換

中級 (4 章)

  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、モジュラー逆元

上級 (6 章)

  1. 第8章 不均衡 Toom-Cook 乗算

    Toom-4,2 / Toom-8、pre-pad + addmul_1、unbalanced な invert_approx への応用

  2. 第9章 NTT 実装比較

    Prime NTT、Small Prime NTT、Goldilocks NTT、Double FFT、5-smooth NTT、AVX2 バタフライ

  3. 第10章 素数判定

    Miller-Rabin、Fermat、Baillie-PSW、APRCL、AKS、実用的な組み合わせ戦略

  4. 第11章 整数因数分解

    試し割り、Pollard rho/Brent、Pollard p-1、Fermat、ECM、SIQS、GNFS

  5. 第12章 Block Lanczos

    GF(2) 疎行列ソルバ、Coppersmith の Block 化、CSR 形式、GNFS の最終段階

  6. 第13章 数論関数

    Möbius μ、Euler totient φ、約数関数 σ_k、Jacobi 記号、Dirichlet 畳み込み、Möbius 反転

最終更新: 2026-04-20