模运算的概念和性质

2024-07-03 18:21| 来源: 网络整理| 查看: 265

0x00 模运算的概念

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

其中：

A is the dividendB is the divisorQ is the quotientR is the remainder

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

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

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

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

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

求整数商： c = [ a / b ] c = \lbrack a / b \rbrack c=[a/b]计算模或者余数： r = a − c ⋅ b r = a - c \cdot b r=a−c⋅b

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

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

四种取整运算

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

例如:

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

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

0x02 模运算的性质

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

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

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

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

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

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

假设 a / p = Q , a % p = R a / p = Q, a \% p = R a/p=Q,a%p=R，可以得到 a = p Q + R a = pQ + R a=pQ+R；将 a 代入 ( a b ) % p (a^b) \text{ \% } p (ab) % p，得到 ( ( p Q + R ) b ) % p ((pQ + R)^b) \text{ \% } p ((pQ+R)b) % p；由二项式定理： ( p Q + R ) b = ∑ r = 0 b C b r ( p Q ) b − r ( R ) r (pQ + R)^b = \sum_{r=0}^{b}C_{b}^{r}(pQ)^{b-r}(R)^{r} (pQ+R)b=∑r=0bCbr(pQ)b−r(R)r ，当 b − r ≠ 0 b-r \neq 0 b−r=0 时，存在 p p p 的算子中都可以被 p p p 整除，所以： ( ( p Q + R ) b ) % p = C b b ( p Q ) 0 ( R ) b = ( R ) b % p = ( a % p ) b % p ((pQ + R)^b) \text{ \% } p = C_{b}^{b}(pQ)^{0}(R)^{b} =(R)^{b} \text{ \% } p = (a \text{ \% } p)^b \text{ \% } p ((pQ+R)b) % p=Cbb(pQ)0(R)b=(R)b % p=(a % p)b % p 参考文档 https://en.wikipedia.org/wiki/Modulo_operationhttps://baike.baidu.com/item/%E5%8F%96%E6%A8%A1%E8%BF%90%E7%AE%97https://crypto.stanford.edu/pbc/notes/numbertheory/https://www.khanacademy.org/computing/computer-science/cryptography#modarithmetic

【本文地址】

公司简介

联系我们