Encryption
仿射密碼：為什麼要求 GCD(a, m) 等於 1
在仿射密碼中，密鑰 $ k = (a, b) $ 應具有以下性質，即GCD 的 $ a $ 並且模數應該是 1：
$ \gcd (a, m) = 1 $ ， 在哪裡 $ m $ 是可能模數的集合
我的問題是，為什麼需要 $ a $ 應該有上面的屬性嗎？這有什麼意義？為什麼是 $ b $ 排除在這個條件之外？
好的，為了理解這個問題，讓我們首先回顧一下仿射密碼是如何定義的：
$$ c=a\cdot x+b\bmod m $$ 請注意，以下內容成立： $ a\cdot x+b=c\iff a\cdot x=c-b $ , 你會在哪裡計算 $ -b $ 作為 $ m-b $ 這是 $ >0 $ 因為 $ m>b $ 因為否則你可以減少 $ b\bmod m $ 更遠。
好的，所以在我們解密的路上，我們現在只需要得到 $ x $ 在……之外 $ a\cdot x=c’\bmod m $ （和 $ c’=c-b\bmod m $ ).
現在如果 $ d=\gcd(a,m)>1 $ 那麼這個方程有 $ 0 $ 或者 $ d $ 解決方案，也不是您想要的解密功能（沒有明文恢復或不確定的明文恢復）。
所以這就是我們做出限制的原因 $ \gcd(a,m)=1 $ ，這將確保只有一個整數解 $ a\cdot x=c’\bmod m $ 和 $ 0\leq x<m $ .
如果您想說明缺少解決方案，請查看範例 15 的模乘法表。例如，您會注意到沒有 $ x $ 這樣 $ 6\cdot x=5\bmod 15 $ 但是，有三個 $ x $ 這樣 $ 6\cdot x=3\bmod 15 $ 並註意 $ \gcd(15,6)=3>1 $ .