inverse - 如何加快 NTL 中的分圆多项式反演？

Question

我正在计算在第 n 次分圆多项式上构建的环中的多项式模逆，n 为 2 的幂。这些逆是针对系数 x^0 等于 (x+1) 的多项式计算的，而其他多项式是从一些随机抽样的分布，但对于某个整数 x，总是等于 0 或 x。

我可以使用 NTL 的 InvMod 来计算多个多项式的逆，但是对于所描述的大型实例，它只需要永远返回。我确实用 GMP 6.1.1 编译了 NTL 9.10.0。我可以在 NTL 上使用任何优化来更快地解决此操作吗？

这是最低限度的代码：

#include <NTL/ZZ_p.h>
#include <NTL/ZZ_pEX.h>
#include <ctime>

NTL_CLIENT

int main(){

    int degree = 4095;
    int nphi = 8192;
    int nq = 127;

    // Sets q as the mersenne prime 2^nq - 1
    ZZ q = NTL::power2_ZZ(nq) - 1;
    ZZ_p::init(q);

    // Sets phi as the n-th cyclotomic polynomial
    ZZ_pX ring;
    NTL::SetCoeff(ring,0,1);
    NTL::SetCoeff(ring,nphi/2,1);
    ZZ_pE::init(ring);

    ZZ_pEX ntl_phi;
    NTL::SetCoeff(ntl_phi,0,conv<ZZ_p>(1));
    NTL::SetCoeff(ntl_phi,nphi/2,conv<ZZ_p>(1));

    // Initializes f
    std::srand(std::time(0)); // use current time as seed for random generator

    ZZ_pEX f;
    NTL::SetCoeff(f,0,conv<ZZ_p>(1025));
    for(int i = 1; i <= degree; i++){
        int random_variable = std::rand();
        NTL::SetCoeff(f,i,conv<ZZ_p>(1024*(random_variable%2 == 1)));
    }

    // Computes the inverse of f
    ZZ_pEX fInv = NTL::InvMod(f, ntl_phi);

    return 0;
}