係數增長
在這個調查中，我不明白係數（第 4.1.2 段）增長的必要性和選擇 $ X^d\pm 1 $ 或者 $ X^d \pm X^{d/2} +1 $ , 因為後面介紹 $ q $ 這沒有提到係數增長。我想了解這一段及其重要性。
提前致謝
這裡的目標是對於任何兩個多項式 $ a(X),b(X)\in \mathcal R_f:=\mathbb Z[X]/f(X) $ 應該有一個乘積，其係數在絕對大小上盡可能由係數的絕對大小控制 $ a $ 和 $ b $ . 這應該意味著具有非常小的係數的多項式的乘積相對於 $ q $ 相對於 $ q $ 和係數減少模 $ q $ 不會影響這個屬性。我們將要求此屬性持有多種選擇 $ a $ 和 $ b $ , 我們想選擇一個多項式 $ f(X) $ 這保證了所有人 $ a(X) $ 和 $ b(X) $ .
如果我們看一下係數 $ X^{d-1} $ 在產品中 $ a(X) $ 和 $ b(X) $ 減模前 $ f(X) $ ， 說 $ c(X):=a(X)b(X) $ 它是由 $$ c_{d-1}=\sum_{i=0}^{d-1}a_ib_{d-i-1}. $$ 這是一個總和 $ d $ 每個項都是兩個係數的乘積，這導致我們期望我們不能希望更好地約束乘積的係數 $ d||a||\infty||b||\infty $ . 減模 $ f $ 通過累積項和按整數倍縮放可能會使事情變得更糟。我們可以通過寫出乘法的效果來使這種感覺更精確 $ a\mod f $ 作為矩陣，它作用於係數 $ b $ 這就是論文所做的。
最好的情況是 a) $ f(X)=X^d-1 $ 當一般係數為 $ j $ 產品的第一項是 $$ c_j=\sum_{i=0}^{d-1}a_ib_{j-i\mod d}, $$ 這與我們在歸約之前的天真界限相匹配，或者 b) 當 $ f(X)=X^d+1 $ 當一般係數為 $ j $ 產品的第一項是 $$ c_j=\sum_{i=0}^{j}a_ib_{j-i}-\sum_{i=j+1}^{d-1}a_ib_{j+d-1-i}, $$ 在絕對值減少之前再次匹配我們的幼稚界限，或者 c) 當 $ f(X)=X^d $ 當一般係數為 $ j $ 產品的第一項是 $$ c_j=\sum_{i=0}^{j}a_ib_{j-i} $$ 在絕對值減少之前匹配我們的幼稚界限 $ j=d-1 $ ，但由於其他原因，這是非常糟糕的選擇。對於任何其他選擇 $ f(X) $ 將有一個係數表達式，其中總和中的項數大於 $ d $ 或者總和的一部分由一個係數縮放 $ f(X) $ 即絕對值大於 1。
形式的多項式 $ f(X)= 𝑋^𝑑\pm X^{𝑑/2}\pm 1 $ 創建係數表達式，它們最多為 $ 2d $ 導致邊界稍差的術語。