LWE 矩陣是原始機率的下界
對於正整數 $ q, n, m>n $ ，我們如何得出下界 $ Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] \geq 1 - \frac{1}{q^{m-n}} $ 對於均勻隨機矩陣 $ A \in \mathbb Z_q^{n \times m} $ ?
我知道這個機率等於每行有 gcd 1 和 q 的機率， $ gcd(a_{i,1}, \dots, a_{i,m}, q) = 1 $ . 此外，totient 函式有一個下界， $ \varphi(q) \geq \sqrt q/\sqrt 2 $ ，但這並沒有讓我找到我們想要的界限的解決方案。
我覺得你想多了。
暗示
其中的事件 $ A\cdot \mathbb Z_q^m \neq \mathbb Z_q^n $ 是矩陣的事件 $ A $ 有一個等級缺陷，如果（比如說）第一行是其他行的線性組合，則它是“包含”的。現在，後一個事件的機率是多少？
一個問題是，您要證明的公式通常不正確。
一個不正確的例子是 $ q=8, m=2, n=1 $ .
在這種情況下，隨機矩陣 $ A $ 由兩個值組成；它生成整個空間 $ \mathbb Z_q^n $ 如果這兩個值中的至少一個是奇數；這很有可能發生 $ \frac{3}{4} $ .
但是，您的公式表明機率是 $ \ge 1 - \frac{1}{q^{m-n}} = \frac{7}{8} $ ; 顯然，這不是真的。
現在，如果我們限制它是真的 $ q $ 成為素數。
我能想到的最簡單的方法是推導出確切的機率
$$ Pr[A\cdot \mathbb Z_q^m = \mathbb Z_q^n] = 1 - \sum_{i = m-n+1}^m \frac{1}{q^i} $$ （可以通過模擬第一個來完成 $ n $ 高斯消除的迭代；如果任何步驟失敗（和步驟 $ i $ 會失敗的機率 $ \frac{1}{q^{m-i}} $ )，然後我們可以生成一個無法用該隨機矩陣生成的後圖像；如果所有步驟都失敗了，那麼對於任何可能的後像，我們都可以生成原像）。
然後，我們只注意到這個確切的機率是 $ \ge $ 到給定的近似值。