# How the FFT constants were found

We have chosen to implement the FFT algorithm using the ring of integers mod 70383776563201. Here, we discuss how we discovered this value and other constants used in the algorithm.

First, it is a well-known fact from number theory that in a ring of integers mod m, a value i has a multiplicative inverse iff i is relatively prime to m. Thus, if m is an odd number greater than 230, every power of 2 up to 230 will have a multiplicative inverse.

The more challenging problem is finding a sufficiently large m such that the modular ring contains a principal 230th root of unity. Some basic group theory becomes helpful here. First, in any ring containing a principal nth root of unity r, the values r, r2, ..., rn form a cyclic group of order n. Thus, we need a ring whose multiplicative group (i.e., the set of elements with multiplicative inverses together with the multiplication operation) has a cyclic subgroup of order 230 containing m-1. A generator of this cyclic subgroup will then be a principal 230th root of unity. More generally, if the multiplicative group contains a cyclic subgroup whose order is 230i for some positive integer i, and which contains m-1, we can obtain a principal 230th root of unity by raising a generator of this cyclic subgroup to the ith power.

In order to simplify the task of finding a cyclic subgroup of a proper order, we restrict our attention to prime moduli. Clearly, m is prime iff it is relatively prime to every positive integer less than m. Thus, if m is prime, the multiplicative group contains all of the nonzero elements of the ring. Thus, the ring is a field. Furthermore, it is the case that the multiplicative group of nonzero elements in any finite field is cyclic. Thus, if m is prime, the multiplicative group of nonzero elements is a cyclic group of order m-1 containing m-1.

We therefore need a prime number m > 246 that is one greater than a multiple of 230. This program automates the process we now describe for finding such a prime number and the related constants.

The first step is to find a number m > 246 that is one greater than a multiple of 230, and is "probably" prime. We use the BigInteger.isProbablePrime(int) method in the java.math package to accomplish this. Assuming m is prime, the multiplicative group must have a generator. In order to find a generator, we need an efficient test to determine whether a given number is a generator. It is easily seen that for a prime modulus m, k is a generator iff km-1 mod m = 1 and for every prime factor p of m-1, k(m-1)/p mod m ≠ 1. Furthermore, the existence of a k satisfying these properties is proof that m is prime. Finding the prime factors of m-1 is simplified by the fact that m-1 = 230i; hence, we only need to factor i, which is likely to be little more than 216 (it is, in fact 65550). Once a generator g is found, a principal 230th root of unity is found by computing gi mod m. The other principal roots of unity are found by repeated squaring mod m, and all of the inverses are found using the BigInteger.modInverse(BigInteger) method in the java.math package.

Note (2/11/12): The above could have been simplified if, instead of looking for a generator, we had looked for a value a such that a229i mod m = m-1, where i and m are as above. Once we find such an a, then ai mod m is a principal 230th root of unity. To see why this is an effective strategy, suppose m is prime. Then the multiplicative group is cylic with order m-1. Let g be a generator for this group. Then gm-1 mod m = g0 mod m = 1. Furthermore, because (m-1)2 mod m = 1, g(m-1)/2 mod m = m-1. Now given a random positive a < m, there is a unique k < m-1 such that gk mod m = a. Furthermore, gk(m-1)/2 mod m = m-1 iff k is odd. Because (m-1)/2 = 229i, it follows that ai mod m is a principal 230th root of unity with probability 1/2. By contrast, because there are exactly 229 principal 230th roots of unity and m > 246, the probability that a is a principal 230th root of unity is at most 2-17. (While this approach does not appear to prove that m is prime, that really doesn't matter, as only the probability that ai is a principal 230th root of unity depends on that assumption.)