# Use of FFT with a different definition of multiplication operator

FFT enables us to perform multiplication of polynomials in O(nlogn), where "multiplication" is the standard multiplication over the complex numbers. Is there a general procedure to extend this use of FFT for cases where the "multiplication" is any arbitrary commutative binary operator? for example, for the case where we define ab = a+b (mod n) for an arbitrary n (assuming, in this case, the coefficients of the polynomials are integers)?

Thanks.

• No. What you need for making sense to the DFT of size $N$ is a primitive $N$th root of unity (replacing $e^{2i \pi / N}$). And see the number theoretic transform. – reuns Dec 18 '16 at 21:44
• That's true, yet there is a way, for example, to use FFT for string matching, where we define a*b = 1 iff a=b, else 0. The multiplication itself is still the standard multiplication, but there is a way to use it to calculate the desired operator, which differs from the standard multiplication: cs.stackexchange.com/questions/52775/… – user1767774 Dec 18 '16 at 21:48
• Not at all. The FFT string matching algorithm does nothing more than computing the correlation between shifts of two binary vectors $a(n),b(n) \in \{0,1\}^N$, and it reduces to computing the convolution $c(n) = a \ast b(n)$ seen as sequences of complex numbers, i.e. it is based on the complex multiplication. – reuns Dec 18 '16 at 22:11
• I understand, thanks. – user1767774 Dec 19 '16 at 16:36