NTRUEncrypt证明了有足够的密钥

Question

在NTRU算法中，假设生成一个在(\mathbb{Z}/p\mathbb{Z})[x]/(x^n-1)和(\mathbb{Z}/q\mathbb{Z})[x]/(x^n-1)中可逆为多项式的向量。但是，在这方面，f是否有适当的概率的数学下限？

Answer 1

是。设x^n-1=r_0^{e_0}(x)r_1^{e_1}(x)\cdots r_k^{e_k}(x)\pmod p是\mathbb F_p[x]中多项式x^n-1分解为不可约的因子，则多项式f(x)在(\mathbb Z/p\mathbb Z[x])^\times/(x^n-1)中是可逆的当且仅当f(x)不能被\mathbb F_p中的任何r_i(x)整除。如果f(x)\mod p是随机从\mathbb F_p中最多为n-1的多项式中随机选择的(例如，每个系数都在一个带有概率1/p的剩余类中)，那么r_i(x)|f(x)是一个概率p^{-\deg(r_i)}事件，并且从同质性来看，这些事件对于不同的r_i,r_j是独立的。因此，可逆性模p的概率是

\prod_{i=0}^k\left(1-\frac1{p^{\deg(r_i)}}\right).

考虑到p^n对f(x)\mod p的可能选择，这仍然代表了可能的选择的很大一部分。最坏的情况是当x^n-1因子变成n不同的线性因子时(这对NTRU来说是个糟糕的选择)。在这种情况下，我们仍然有一个概率(1-1/p)^n和至少(p-1)^n可逆多项式模p。

一个类似的，独立的概率可以计算的模式q。