Classical-Cipher
所有仿射密碼都可以用這個公式表示嗎
有 $ 26! $ 英文字母的排列組合。在現代密碼學教科書中，William Easttom 指出
任何仿射密碼的基本公式是 $ ax + b \equiv \pmod{26} $ .
我想知道這個公式是否可以表達所有可能的排列。對於每個排列似乎並不明顯 $ \sigma $ 存在 $ a $ 和 $ b $ 能夠表達出來。如果這個說法是真的，可以用什麼方法找到 $ a $ 和 $ b $ ?
$ a\cdot x +b $ 表示仿射 而不是排列。和 $ a\cdot x +b \bmod 26 $ 是模仿射變換。
$ a\cdot x +b \bmod 26 $ 最多可以有 $ 26\cdot 26 $ 仿射變換其中一些沒有逆，因此沒有逆仿射變換不適用於已經不接近現代加密方法的加密。
要有一個逆必須有 $ \gcd(a,26)=1 $ . 這表示 $ a $ 不能被 2 或 13 整除。要找到實際數字，我們可以使用歐拉的 Totient 函式將正整數計數到給定整數 $ n $ 相對質數 $ n $ . 然後$$ \phi(26) = (13-1)\cdot (2-1) = 13 $$所以其實有 $ 26\cdot 12 =312 $ 可能的仿射變換。
無論如何，我們有 $ 26! = 403291461126605635584000000 $ 排列和 $ 312 $ 仿射變換，因此仿射變換不能涵蓋所有可能的排列。反過來是正確的；排列可以表示可逆仿射變換。