由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还不可逆