is, a2n = 1 and a to all smaller powers is not 1). Then we can define a third vector A, called the weight vector, as: A = (aj), 0 ≤ j < n A−1 = (a−j), 0 ≤ j < n Now, we can state: NegacyclicConvolution(X, Y) = A−1 · IDFT(DFT(A · X) · DFT(A · Y)) In other words, it's the same as before except that the inputs are first multiplied by A, and the result is multiplied by A−1. Choice of ring The discrete Fourier transform is an abstract operation that can be performed in any algebraic ring; typically it's performed in the complex numbers, but actually performing complex arithmetic to sufficient precision to ensure accurate results for multiplication is slow and error-prone. Instead, we will use the approach of the number theoretic transform, which is to perform the transform in the integers mod N for some integer N. Just like there are primitive roots of unity of every order in the complex plane, given any order n we can choose a suitable N such that b is a primitive root of unity of order n in the integers mod N (in other words, bn ≡ 1 (mod N), and no smaller power of b is equivalent to 1 mod N). The algorithm will spend most of its time performing recursive multiplications of smaller numbers; with a naive algorithm, these occur in a number of places: Inside the fast Fourier transform algorithm, where the primitive root of unity b is repeatedly powered, squared, and multiplied by other values. When taking powers of the primitive root of unity a to form the weight vector A and when multiplying A or A−1 by other vectors. When performing element-by-element multiplication of the transformed vectors. The key insight to Schönhage–Strassen is to choose N, the modulus, to be equal to 2n + 1 for some integer n that is a multiple of the number of pieces P=2p being transformed. This has a number of benefits in standard systems that represent large integers in binary form: Any value can be rapidly reduced modulo 2n + 1 using only shifts and adds, as explained in the next section. All roots of unity used by the transform can be written in the form 2k; consequently we can multiply or divide any number by a root of unity using a shift, and power or square