Complexity
當係數不是可逆元素時，求解模線性方程是否是一個難題？
假設我們有一個像這樣的線性方程：
$$ ax=b \pmod n $$ 什麼時候 $ x $ 是未知數，並且 $ a $ 不是可逆元素 $ n $ .
正在尋找 $ x $ 一個難題？
（通過解決我的意思是找到一個 $ x $ 滿足方程）
計算 $ g = GCD(a, n) $ 和 $ n^\prime = n / g $ . 如果 $ b \not\equiv 0 \pmod g $ ，則無解。
將整個方程除以 $ g $ 給你 $ a^\prime· x_0 = b^\prime \pmod{n^\prime} $ 並解決 $ x_0 $ . 然後解決方案 $ x $ 是 $ x_0 + k· n^\prime $ 為了 $ k = 0, 1, …, g-1 $ .
一般來說，這個問題在計算上很容易。很容易判斷是否存在解決方案，如果存在，至少要找到一個解決方案。
如果您想找到一種解決方案（一個 $ x $ 滿足方程），假設存在解，這很容易。@CodesInChaos 解釋瞭如何。
如果您想找到所有解決方案，那麼很容易列舉所有解決方案。但是，請注意，將有 0 或 $ n/\gcd(a,n) $ 解決方案。如果有指數級的解決方案，列出所有解決方案將花費指數級時間。
最後，如果一個特定的解決方案是“特殊的”並且你想找到它（例如，也許 Alice 隨機選擇一個 $ x $ 滿足這個方程，現在挑戰你找到它），你能做的最好的就是在所有的 $ n/\gcd(a,n) $ 解決方案，或列舉它們。如果它們的數量成倍增加，您可能無法知道哪一個是“特殊”的（哪一個是 Alice 的）。