模运算

模运算

假设\ 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 协议》，转载必须注明作者和本文链接