2.5 模运算
模运算
假设\ 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
但从数学角度看,选择等价类中的任何一个元素对最后的结果都没有任何影响。