分圓環中單位組的基數？
在 NTRU 密鑰生成中，人們從 $ K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1) $ 並測試它是否可逆。這種情況發生的可能性有多大？換句話說：
讓 $ q $ 成為素數並且 $ n>4 $ 成為 $ 2 $ . 什麼是基數 $ K^* $ ?
這 $ n $ th 分圓多項式 $ \Phi_n\in\mathbb Z[x] $ 是不可約的 $ \mathbb F_q[x] $ 當且僅當 $ q $ 是一個生成器 $ (\mathbb Z/n)^\times $ （證明）。因此，不幸的是，多項式 $ x^n+1 $ 永遠是不可約模 $ q $ 如果 $ n>4 $ 是二的冪：群 $ (\mathbb Z/n)^\times $ 在這種情況下不是循環的。因此，在 NTRU 中選擇的多項式確實可能是不可逆的。
由於我不知道任何確切的結果，我們將推導出基數的通用下限 $ (\mathbb F_q[x]/(x^n+1))^\times $ . （通過“通用”，我的意思是以下內容並不特定於分圓多項式。我懷疑通過使用分圓理論可以獲得更好的界限。）
我會假設 $ q\geq3 $ . 那麼多項式 $ x^n+1 $ 是無平方的 $ \mathbb F_q $ 自從 $ \gcd(x^n+1,nx^{n-1})=1 $ . 分解 $ x^n+1 $ 成（因此不同的）不可約因數 $ g_i\in\mathbb F_q[x] $ 度數 $ e_i:=\deg g_i $ . 根據中國剩餘定理，我們有一個同構
$$ \varphi\colon\quad \mathbb F_q[x]/(x^n+1) ;\cong; \prod_{i=1}^r\underbrace{\mathbb F_q[x]/g_i}{\cong\ \mathbb F{q^{e_i}}} \text. $$ 將這種同構與對直接因子的投影組合起來 $ \mathbb F_q[x]/g_i $ 產生環同態 $$ \pi_i\colon\quad \mathbb F_q[x]/(x^n+1) ;\to; \mathbb F_{q^{e_i}} $$ 具有一個元素的屬性 $ \mathbb F_q[x]/(x^n+1) $ 是可逆的當且僅當它的圖像在每個 $ \pi_i $ 是可逆的，即非零。因此，一個元素的機率 $ f\in\mathbb F_q[x]/(x^n+1) $ 隨機均勻選擇的是一個單位 $$ \Pr[\text{unit}] ;=; \prod_{i=1}^r (1-1/q^{e_i}) \text. $$ 這會變得多糟糕？在最壞的情況下，我們有 $ r=n $ 和所有 $ e_i=1 $ ， 因此 $$ \Pr[\text{unit}] ;\geq; (1-1/q)^n \text. $$ 當考慮小 $ q $ 和大 $ n $ ，這個界限很快就會變得很低，但請記住，這是一個最壞情況的估計。在實踐中，似乎 $ e_i $ 通常遠大於 $ 1 $ .
此外，在 NTRU 場景中， $ q $ 相當大：推薦的參數，根據來源，大致是 $ q\approx 2000 $ 和 $ n\approx 1000 $ , 產生
$$ \Pr[\text{unit}] ;\geq; \frac12 \text, $$ 所以人們可以很容易地在幾次嘗試中以非常大的機率找到一個單位。