a root of unity by operating only on its exponent. The element-by-element recursive multiplications of the transformed vectors can be performed using a negacyclic convolution, which is faster than an acyclic convolution and already has "for free" the effect of reducing its result mod 2n + 1. To make the recursive multiplications convenient, we will frame Schönhage–Strassen as being a specialized multiplication algorithm for computing not just the product of two numbers, but the product of two numbers mod 2n + 1 for some given n. This is not a loss of generality, since one can always choose n large enough so that the product mod 2n + 1 is simply the product. Shift optimizations In the course of the algorithm, there are many cases in which multiplication or division by a power of two (including all roots of unity) can be profitably replaced by a small number of shifts and adds. This makes use of the observation that: (2n)k ≡ (−1)k mod (2n + 1) Note that a k-digit number in base 2n written in positional notation can be expressed as (dk−1,...,d1,d0). It represents the number . Also note that for each di we have 0 ≤ di < 2n. This makes it simple to reduce a number represented in binary mod : take the rightmost (least significant) n bits, subtract the next n bits, add the next n bits, and so on until the bits are exhausted. If the resulting value is still not between 0 and 2n, normalize it by adding or subtracting a multiple of the modulus . For example, if n=3 (and so the modulus is 23+1 = 9) and the number being reduced is 656, we have: 656 = 10100100002 ≡ 0002 − 0102 + 0102 − 12 = 0 − 2 + 2 − 1 = −1 ≡ 8 (mod 23 + 1). Moreover, it's possible to effect very large shifts without ever constructing the shifted result. Suppose we have a number A between 0 and 2n, and wish to multiply it by 2k. Dividing k by n we find k = qn + r with r < n. It follows that: A(2k) = A(2qn + r) = A[(2n)q(2r)] ≡ (−1)q Shift Left(A, r) (mod 2n + 1). Since A is ≤ 2n and r < n, A shift-left r has at most 2n−1 bits, and so only one shift and subtraction (followed