ntt不平衡乘法策略失效

[HJimmyK]

在3ntt-crt的不平衡处理策略中，参数 M 本意是一个阈值，作为处理不平衡分块的一个参考值，其尽可能接近 $\sqrt{\frac{len1}{len2}}$ 时，达到理论最优。
原因如下：（假定乘数的二进制长度分别为m,n ,且认为m >> n，假定 $m≈l\cdot n$ ）
不分块直接ntt乘法的复杂度： $O((m+n)\text{log}(m+n))$
分块块数假如为 t：

$$ O(t \cdot (\frac{m}{t}+n)) \text{log}(\frac{m}{t}+n) $$

当 $$t=\sqrt{l}$$ 时，其可以取至最低值。
同时分块还可以复用短乘数的变换结果，而不用重复计算。

原实现中的：lamp_ui min_sum = len2 + std::max(len2, M);实际并未起到作用，因为M为sqrt(len1/len2)，导致实际上min_sum=len2+len2，分块策略并未奏效。改为：lamp_ui min_sum = len2 + std::max(1ull, M) * len2;即可。

可以发现在大部分数据上，蓝色（原错误实现）耗时更长，

且原实现存在明显漏洞：即某些更长的数据计算反而更快，这都是不正确分块策略导致的结果。尽管此错误并不影响计算的正确性。

[HJimmyK]

需要注意的是，此函数 $O(t \cdot (\frac{m}{t}+n)) \text{log}(\frac{m}{t}+n)$ 并不是严格在 $\sqrt{\frac{m}{n}}$ 时取至最小值，但这个是一个对最小值点的非常不错的估计，读者可以自行验证。

即使 $m=n^2$，这是一个相当不平衡的乘法，其对最小值点的估计的偏差也不超过 $10$%，另一种有可能的考量就是 $\sqrt{\frac{m}{n}}$ 通常要大于最小值的对应的分块取值，这意味着更大的空间复杂度。如果进一步的测试表明取至理论最小值更好，将考虑更改策略。

[HJimmyK]

进一步的测试发现，两者在倍数相差不大时的确时间基本相近。

在更不平衡的数据集中，两者有大约百分之10到30不等的提升，考虑到由于分块数量的增加，空间复杂度大大降低，这是可以接受的。

对更不平衡数据测量发现，其能够带来将近大约 15% 的提升。