How the FFT constants were found

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 2³⁰, every power of 2 up to 2³⁰ will have a multiplicative inverse.

The more challenging problem is finding a sufficiently large m such that the modular ring contains a principal 2³⁰th 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, r², ..., rⁿ 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 2³⁰ containing m-1. A generator of this cyclic subgroup will then be a principal 2³⁰th root of unity. More generally, if the multiplicative group contains a cyclic subgroup whose order is 2³⁰i for some positive integer i, and which contains m-1, we can obtain a principal 2³⁰th 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 > 2⁴⁶ that is one greater than a multiple of 2³⁰. 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 > 2⁴⁶ that is one greater than a multiple of 2³⁰, 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 k^m-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 = 2³⁰i; hence, we only need to factor i, which is likely to be little more than 2¹⁶ (it is, in fact 65550). Once a generator g is found, a principal 2³⁰th root of unity is found by computing gⁱ 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 a²²⁹ⁱ mod m = m-1, where i and m are as above. Once we find such an a, then aⁱ mod m is a principal 2³⁰th 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 g^m-1 mod m = g⁰ mod m = 1. Furthermore, because (m-1)² 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 g^k mod m = a. Furthermore, g^k(m-1)/2 mod m = m-1 iff k is odd. Because (m-1)/2 = 2²⁹i, it follows that aⁱ mod m is a principal 2³⁰th root of unity with probability 1/2. By contrast, because there are exactly 2²⁹ principal 2³⁰th roots of unity and m > 2⁴⁶, the probability that a is a principal 2³⁰th 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 aⁱ is a principal 2³⁰th root of unity depends on that assumption.)

Oracle and Java are registered trademarks of Oracle and/or its affiliates. Other names may be trademarks of their respective owners.