Garner 法

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /garner-algorithm#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /garner-algorithm#noredirect を利用してください。
name
Garner 法
short description
Garner 法とは、中国剰余定理で存在が示されるところの $\forall i. x \equiv a_i \pmod{m_i}$ を満たす整数 $x$ について、それを別の $M$ で割った余り $x \bmod M$ を求めるアルゴリズムである。計算の過程で現われる整数の大きさが $m_i$ や $M$ の $2$ 乗程度で抑えられることを特徴とする。
input
整数と正整数の対の長さ $k$ の列 $((a_0, m_0), (a_1, m_1), \dots, (a _ {k-1}, m _ {k-1}))$ および正整数 $M$
output
$\forall i. x \equiv a_i \pmod{m_i}$ を満たす $x$ を $M$ で割った余り $x \bmod M$
time complexity
$\bmod m_i$ および $\bmod M$ での演算を $O(1)$ と仮定して $O(k^2)$