模运算的概念和性质

aggresss

12080人浏览 · 2021-10-09 14:49:20

aggresss · 2021-10-09 14:49:20 发布

0x00 模运算的概念

整数除法运算中，被除数 A，除数 B，运算结果商为 Q，余数为 R，表示如下：
$\frac{A}{B} = Q\text{ remainder }R$

其中：

A is the dividend
B is the divisor
Q is the quotient
R is the remainder

利用上面的算式我们将模运算表示为：
$\text{ mod } B = R$

数论中的模运算 (Modulo Operation) 与解析几何中的模 (Norm) 没有任何关联。

0x01 模运算和余运算的区别

模运算（Modulo Operation）和余运算（Remainder Operation）两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。模运算主要用于计算机术语中，余运算则更多是数学概念。

对于整数 a, b 来说，模运算或者余运算的方法都是：

求整数商： $\lbrack a / b \rbrack$
计算模或者余数： $\cdot b$

求模运算和求余运算在第一步不同:

模运算在计算 c 的值时使用 floor() 函数；
余运算在取 c 的值时使用 fix() 函数；

四种取整运算

floor() // 向 $-\infty$ 方向取整
ceil() // 向 $+\infty$ 方向取整
fix() // 向 0 方向取整
round() // 四舍五入到最近的整数

例如:

$\text{ mod } 4 = -7 - (-2) \cdot 4 = 1$
$\text{ rem } 4 = -7 - (-1) \cdot 4 = -3$

在不同的计算机语言中 % 运算符的含义不同，例如 C/C++/Go/Java/JavaScript 为余运算，而 Python 为模运算；
专业的数学软件语言中会将模运算和余运算区分开，例如 MATLAB 中的 mod 和 rem 。

0x02 模运算的性质

模运算与基本四则运算有些相似，除法例外。其规则如下：

$b)\text{ \% } p = (a \text{ \% } p + b \text{ \% } p)\text{ \% } p \tag{1}$
$\text{ - } b)\text{ \% } p = (a \text{ \% } p \text{ - } b \text{ \% } p)\text{ \% } p \tag{2}$
$\cdot b) \text{ \% } p = (a \text{ \% } p \cdot b \text{ \% } p) \text{ \% } p \tag{3}$
$\text{ \textasciicircum\ } b) \text{ \% } p = ((a \text{ \% } p) \text{ \textasciicircum\ } b) \text{ \% } p \tag{4}$

结合律：
$\text{ \% } p + c) \text{ \% } p = (a + (b+c) \text{ \% } p) \text{ \% } p \tag{5}$
$\cdot b) \text{ \% } p \cdot c) \text{ \% } p = (a \cdot (b \cdot c) \text{ \% } p) \text{ \% } p \tag{6}$

交换律：
$\text{ \% } p = (b+a) \text{ \% } p \tag{7}$
$\cdot b) \text{ \% } p = (b \cdot a) \text{ \% } p \tag{8}$

分配律：
$\text{ \% } p \cdot c) \text{ \% } p = ((a \cdot c) \text{ \% } p + (b \cdot c) \text{ \% } p) \text{ \% } p \tag{9}$

证明: $\text{ \% } p = ((a \text{ \% } p) ^ b) \text{ \% } p$

假设 $\% p = R$ ，可以得到 $a = pQ + R$ ；
将 a 代入 $(a^b) \text{ \% } p$ ，得到 $R)^b) \text{ \% } p$ ；
由二项式定理： $R)^b = \sum_{r=0}^{b}C_{b}^{r}(pQ)^{b-r}(R)^{r}$ ，当 $\neq 0$ 时，存在 $p$ 的算子中都可以被 $p$ 整除，所以： $R)^b) \text{ \% } p = C_{b}^{b}(pQ)^{0}(R)^{b} =(R)^{b} \text{ \% } p = (a \text{ \% } p)^b \text{ \% } p$