关于 【离散小波变换】题解中提到的 Bonus 部分：

参考 Pohlig–Hellman algorithm 算法。

设 $mod-1=\prod\limits_{i=1}^k p_i^{e_i}$。

则这个算法能做到 $O\left(\sum\limits_{i=1}^k e_i(\log mod+\sqrt {p_i} )\right)$ 的复杂度。

而 NTT 模数其实是非必要条件，就是这个算法能有优良性质当且仅当 $mod-1$ 的最大素因子较小即可。