模算术是整数的算术结构,其中数字在达到特定值时“环绕”。模块化算法使我们能够简单地创建组、环和域,它们是大多数现代公钥密码系统的基本构成部分。
例如,Diffie-Hellman 需要以素数 pp 为模的整数乘法组。有不同的组可以工作。模数或时钟算术是圆上的算术而不是数轴模数 N,它只能使用从 0 到 N-1 的十二个整数。
模数运算在几种基本运算的算法方法中得到了很好的理解。这就是它可以在对称密钥加密中使用有限域 (AES) 的原因之一。密码学需要复杂的问题。一些问题发展成模运算的难题。
例如,对数只是简单地计算所有整数,但当它可以引入模约简时,它可能变得难以计算。与发现根类似。Mod-arithmetic 是密码学中的核心数学术语。
许多现代数论和一些实际问题都与模运算有关。在算术模 N 中,它涉及整数的算术运算,它可以识别所有以 N 的强加倍数变化的数字。也就是说,
x=y mod N 如果 x = y +mN 对于某个整数 m。
这种识别将所有整数分成 N 个相同的类。它通常可以通过它们最简单的成员来表示这些,即数字 0、1、….N-1。
如果 a 是整数且 n 是正整数,则将 a mod n 表示为 a 除以 n 时的余数。然后 $\mathrm{a\, =\, \left \lfloor a/n\right \rfloor\, x\, n\, +\, \left ( a\, mod\, n \right );}$
示例 - 11 mod 7 = 4
Theorem - n 是整数的等价关系。等价类包括那些除以 n 时余数相等的整数。等价类也称为模n的同余类。与其说整数 a 和 b 是等价的,不如说它们是模 n 一致的。
与模n全等的所有整数的集合称为剩余类[a]。
模运算符具有以下属性 -
a ≡ b mod n 如果 n|(a − b)。
(a mod n) = (b mod n) 意味着 a ≡ b mod n。
a ≡ b mod n 意味着 b ≡ a mod n。
a ≡ b mod n 和 b ≡ c mod n 蕴含 a ≡ c mod n。
模算术运算的性质
[(a mod n) + (b mod n)] mod n = (a + b) mod n
[(a mod n) - (b mod n)] mod n = (a - b) mod n
[(a mod n) x (b mod n)] mod n = (axb) mod n
令 Zn = {0, 1, 2,… (n-1)},为残差模数 n 的集合。
财产 | 表达 |
---|---|
Commutative laws | (w + x) mod n = (x + w) mod n |
Associative laws | (wxx) mod n = (xxw) mod n |
[(w + x)+y] mod n = [w+(x+y)] mod n | |
Distributive laws | [(wxx) xy] mod n = [wx (xxy)] mod n |
Identities | [(wx (x + y)] mod n =[(wxx) + (wxy)] mod n |
(0 + w) mod n = w mod n | |
Additive inverse (-w) | (1 xw) mod n = w mod n |
对于每个 w ∈ Zn,存在 az 使得 w + z ≡ 0 mod n |