由NTT变换想到的问题

ssikkiss

已知有个数组A,长度为2^n, 并已知一数论变换,参数为N=2^n(长度),M(模),g(N次跟). 正变换记为NTT(),逆变换记为invNTT(). 现在若对数组A应用逆变换,即invNTT(),将得到数组B. 请问是否有快速的方法判断: 1. 如果,B的每一位都是小于某个已知值Max,则返回TRUE 2. 否则,返回FALSE 当然,这里说的"快速的方法",是指比计算B=invNTT(A)更快的方法 不知是否存在这种快速的方法?

gxqcn

既然是数论变换，那么得到的数组就是经过模变换处理的， 想先问一下：比较模的剩余类可有实际意义？

无心人

对，这个问题无意义 实现选择了参数使得不存在截断 则肯定可求出 不限定则无法求出

ssikkiss

当然这个问题对乘法或其他的东东没有实际意义. 老实说吧,这其实是我正探寻的另一个问题的根本. 因为这里大家都对NTT熟悉,贴在这里大家都能读懂 而且最重要的是这里有很多数学高手 如果能够证明,找不到这样一种快速的方法,那么我正探寻的另一个问题就不必探寻了.

ssikkiss

也可以用另一种形式: 如果要构造一个数组B,使得A=invNTT(B)的每一位都小于已知值Max, 请问你将遵循怎样的规则来构造?

无心人

根据数论变换的定义 则显然 你要求的是一个NTT逆矩阵和A的矩阵积 那问题转化为一个$N=2^n$的矩阵和一个$2^n$的向量的积中求最大的项 我知道的知识是这个问题不会有比NTT更快的方法吧

无心人

能说你想做的另外一个问题么？

ssikkiss

这里我说的另一个问题,说出来可能大家会笑话我. 我想用NTT来做因子分解 我是这样想的: 如果两个数A,B,A*B=C,这就是乘法 现自把A,B都看作2进制数组,并且补零使长度可以适合NTT变换 用NTT来做乘法大家都知道的,就是 1. 求a=NTT(A),b=NTT(B), 2. 然后求数组c,使得c(i)=a(i) * b(i) 3. 求数组C,使得C=invNTT(c) 4. 对数组C进行2进制规整,就得到C=A*B 我的想法是对以上过程进行逆运算,试图分解C得到A和B 发现这种方法比试除法还慢,所以就提出了上面的问题,希望在对上面的第2步进行逆运算的时候,找到一种构造数组a和b的方法 不够就目前我的经验来看,这个方法似乎行不通 刚开始我以为NTT把要分解的数C切成一小段一小段的,以为会更好的分解

无心人

NTT的结构比因子分解的结构还复杂 不客气的说，从NTT逆向还原算法 比MD5还不可逆