NTT模数限制

为什么有些模数被称为NTT模数呢?因为他们都是这样一个形式:\(P=2^a∗X+1\)

为什么要有这样一个条件呢,因为只有这样,才能找到所需的原根。

所以对于一般的一个模数 \(P=2^a∗X+1\),能适用的最大的多项式长度(包括结果)是 \(2^a\)

所以 \(1e9+7\) 就是不行的,其只能分解出一个 \(2\)

原文地址:https://www.cnblogs.com/mamamoo/p/15783149.html