NTRUEncrypt -选择初始随机多项式

Question

我正在尝试实现NTRUEncrypt，但遇到了一些问题。我已经完成了基于这个文档的方案所需的所有基本函数，但是我找不到一个算法来检查初始多项式f的有效性。

如果f不是限定的(逆mod p或逆mod q不存在)，那么计算逆模的函数就会在无限循环中结束。

我发现了一些关于ntru网的文档，但是他们太多了，我没有时间去浏览它们。如果有人能在算法方面帮助我，或者指出我应该阅读的文档，那将是有帮助的。

Answer 1

只要f(1)具有p和q的GCD为1，则f具有高概率的逆。(f( 1 ) =f按1计算，即f的系数之和)。

如果你认为f是df1s的二进制，那么df相对于p和q是素数。

如果f是三进制的，它有df1s和df-1 - 1s，那么f(1) =1，这将完全满足GCD的要求。

如果取f为1+ pF形式，f(1)为1 mod p，且完全满足这一要求。对于GCD要求模q，要么选择F为等于+1s和-1s的三进制(so f(1) = 1)，要么选择F为二进制，使1+ p*F(1)相对于q素数。

上面的“高概率”意味着，随着Q和N的增加，没有逆的概率会迅速下降。我已经在堆栈溢出(http://stackoverflow.com/questions/2754444/meet-in-the-middle-atack-on-an-ntru-private-key)上发布了玩具示例，当我生成它们时，我在第一次尝试N= 11，Q= 29时想出了可逆键。