by normalization) is needed. Finally, to divide by 2k, observe that squaring the first equivalence above yields: 22n ≡ 1 (mod 2n + 1) Hence, A/2k = A(2−k) ≡ A(22n − k) = Shift_Left(A, 2n − k) (mod 2n + 1). Algorithm The algorithm follows a split, evaluate (forward FFT), pointwise multiply, interpolate (inverse FFT), and combine phases similar to Karatsuba and Toom-Cook methods. Given input numbers x and y, and an integer N, the following algorithm computes the product xy mod 2N + 1. Provided N is sufficiently large this is simply the product. Split each input number into vectors X and Y of 2k parts each, where 2k divides N. (e.g. 12345678 → (12, 34, 56, 78) for 2k=4). In order to make progress, it's necessary to use a smaller N for recursive multiplications (denoted n below). For this purpose choose n as the smallest integer at least 2N/2k + k and divisible by 2k. Compute the product of X and Y mod 2N + 1 using the negacyclic convolution: Multiply X and Y each by the weight vector A using shifts (shift the jth entry left by jn/2k). Compute the DFT of X and Y using the number-theoretic FFT (perform all multiplications using shifts; for the 2k-th root of unity, use 22n/2k). Recursively apply this algorithm to multiply corresponding elements of the transformed X and Y. Compute the IDFT of the resulting vector to get the result vector C (perform all multiplications using shifts). This corresponds to interpolation phase. Multiply the result vector C by A−1 using shifts. Adjust signs: some elements of the result may be negative. We compute the largest possible positive value for the jth element of C, , and if it exceeds this we subtract the modulus 2n + 1. Finally, perform carrying mod 2N + 1 to get the final result. The optimal number of pieces to divide the input into is proportional to , where N is the number of input bits, and this setting achieves the running time of O(N log N log log N), so the parameter k should be set accordingly. In practice, it is set empirically based on the input sizes and the architecture, typically to a value between 4 and 16. In step 2, the observation is used that: Each element of the input vectors has at most N/2k bits; The product of any two input