具有循环卷积特性(CCP)的矩形变换

本文提出了一个计算卷积的新方法,它是Cook-Toom法的改进,但比后者简便,且可利用已知短卷积的结果,所需乘法次数与Cook-Toom一样为2N-1;然后一般地讨论了矩形变换y=C{(Ah)(?)(Bx)}具有CCP的条件,并且用此条件证明DFT及NTT具有CCP;再给矩形变换更多的限制,证明了变换A具有CCP的充要条件,并证明了这时必有逆,同时给出了逆的形式;最后将上面讨论的结果推广到整数环Z_p中去,得出了Z_p中具有CCP的可逆变换的一般形式。