多倍長整数 中級

目次 (第5章〜第8章)

※ 第1章〜第4章は初級編を参照。

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

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

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

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

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

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

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

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

最終更新: 2026-05-17

読み物 読み物

章立てとは別に、物語や直観で気軽に読める記事です。

  1. 読み物 最大公約数を最速で求める ― ユークリッドの2300年前の知恵

    素因数分解しなくても、割って余りに乗り換えるだけで最大公約数は求まる。世界最古のアルゴリズムが、いまも速くて現役な理由

  2. 読み物 分割して速く掛ける ― カラツバ法の発見

    数を半分に割って組み立て直すと、掛け算の回数を 4 回から 3 回に減らせる。23 歳のカラツバが「掛け算は二乗より速い」という常識を覆した話

  3. 読み物 時計の算数を一般化する ― 合同算術の威力

    時計は 12 で一周して 0 に戻る。この「あまりだけを見る」算数を一般の数に広げると、巨大な数をあふれさせずに計算する道が開ける

  4. 読み物 ばらして解いて組み立てる ― 中国剰余定理

    一つの巨大な数を小さな法の余りの組に置き換える。バラバラの余りからもとの数がただ一つ復元できる、千七百年前の数え方が生んだ定理

  5. 読み物 巨大なべき乗を一瞬で ― 繰り返し二乗法

    3 を 1000 回掛けるのに、本当に 1000 回も掛け算がいるのか。二乗を重ねて指数を半分ずつ畳めば、千回の掛け算が十数回で済む