具体数学 独立剩余 旁注
注:本节内容为"具体数学"(原书第二版) 第四章 数论 4.7 独立剩余 的旁注.
P106 独立剩余到底在做什么?
独立剩余可以将两个数对于一个大模数的 模数加法,模数减法,模数乘法,转换为这两个数对于若干个小模数的 模数加法,模数减法,模数乘法.
P106 独立剩余怎么做?
首先,我们定义 剩余系 (Residue Number System)
\operatorname{Res}(x) = (x \bmod m_1, \cdots ,x \bmod m_r), 1 \leq j < k \leq r \Rightarrow m_j \perp m_k
\prod _ k m_k = m