資訊安全中的模算術是什麼？

模算術是整數算術的一種結構，其中數字達到特定值後會“迴圈”。模算術使我們能夠輕鬆地構建群、環和域，這些是大多數現代公鑰密碼系統最基本的構建塊。

例如，Diffie-Hellman 需要模素數 p 的整數乘法群。可以使用不同的群。模算術或時鐘算術是在圓圈而不是模 N 數軸上的算術，它只使用從 0 到 N-1 的十二個整數。

模算術在多種基本運算的演算法方法中得到了很好的理解。這就是它可以在對稱金鑰加密中使用有限域 (AES) 的原因之一。密碼學需要複雜的問題。有些問題在模算術中變得很難解決。

例如，對所有整數計算對數很簡單，但在引入模約簡時，計算對數可能變得困難。發現根也是如此。模算術是密碼學中的核心數學概念。

現代數論的許多內容和一些實際問題都與模算術有關。在模 N 算術中，它關注整數上的算術，其中識別所有相差 N 的倍數的數字。

也就是說，

如果對於某個整數 m，x = y + mN，則 x ≡ y (mod N)。

這種識別將所有整數劃分為 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

**定理** - n 是整數上的等價關係。一個等價類包括那些除以 n 後餘數相同的整數。等價類也稱為模 n 同餘類。與其說整數 a 和 b 等價，不如說它們模 n 同餘。

模 n 同餘於 a 的所有整數的集合稱為剩餘類 [a]。

模運算子具有以下性質：

• 如果 n | (a - b)，則 a ≡ b (mod n)。

• (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 = (a x b) mod n

令 Zn = {0, 1, 2,… (n-1)} 為模 n 的剩餘集。

Ginni

更新於：2022年3月15日

8K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

開始學習