模运算

模运算#

$假设 \ a, r,m\in Z（其中 Z 是所有整数的集合），\\ 并且 \ m > 0。如果 \ m\ 除 \ a - r, 可记作：\\ a = r\ mod\ m\\ 其中 \ m\ 称为模数，r\ 称为余数。$

余数的计算#

总可以找到一个$a\in z$，使得

$a = q・m + r, 其中 0\leq r < m$

由于$a - r = q・m (m 除 a-r)$, 上诉表达式可写作：$a\equiv r\ mod\ m\ (r\in {1,2,…,m-1)}$

例：假设$a = 42, m = 9$, 则$42 = 4·9 + 6$
因此$42\equiv6\ mod\ 9$

余数不唯一#

考虑一个奇怪的问题：对每个给定的模数$m$ 和整数$a$，可能同时存在无限多个有效的余数。下面来看另一个例子。
例：考虑$a = 12, m = 9$ 的情形。根据前面的定义，以下的结果都是正确的：

• 12 = 3 mod 9, 3 是一个有效的余数，因为 9｜（ 12 - 3 ）
• 12 = 21 mod 9, 21 是一个有效的余数，因为 9｜（ 21 - 3 ）
• 12 = -6 mod 9, -6 是一个有效的余数，因为 9｜（ -6 -3 ）
  这里的 x|y 代表 x 除以 y 。这个操作背后是一个系统。整数集

  $\left\{...,-24,-15,-6,3,12,21,30,...\right\}$

  构成了一个所谓的等价类，模数 9 还存在另外 8 个等价类：

  $\left\{...,-27,-18,-9,0,9,18,27,...\right\}\\ \left\{...,-26,-17,-8,1,10,19,28,...\right\}\\ ·\\ ·\\ ·\\ \left\{...,-19,-10,-1,8,17,26,35,...\right\}$

  等价类中所有成员的行为等价#

  对于一个给定模数 m, 选择等价类中任何一个元素用于计算的结果都是一样的。等价类的这个特性具有重大的实际意义。在固定模数的计算中 — 这也是密码学中最常见的情况 — 我们可以选择等价类中最易于计算的一个元素。
  当然，不管在等价类中怎么切换，任何模数计算的最终结果都是相同的。

  余数选择问题#

  一般选择满足以下条件的 r:

  $0\leq r\leq m-1$

  但从数学角度看，选择等价类中的任何一个元素对最后的结果都没有任何影响。

本作品采用《CC 协议》，转载必须注明作者和本文链接