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^{30}, every power of 2 up to
2^{30} will have a multiplicative inverse.

The more challenging problem is finding a sufficiently large *m*
such that the modular ring contains a principal 2^{30}th root
of unity. Some basic group theory becomes helpful here. First, in
any ring containing a principal *n*th root of unity *r*, the
values *r*, *r*^{2}, ...,
*r*^{n} 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^{30} containing *m*-1. A generator of this cyclic subgroup will then be
a principal 2^{30}th root of unity. More generally, if the
multiplicative group contains a cyclic subgroup whose order is
2^{30}*i* for some positive integer *i*, and which
contains *m*-1, we can obtain a principal 2^{30}th root
of unity by raising a generator of this cyclic subgroup to the
*i*th 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^{46} that is
one greater than a multiple of 2^{30}. 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^{46} that
is one greater than a multiple of 2^{30}, 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^{30}*i*; hence, we only need to factor *i*, which
is likely to be little more than 2^{16} (it is, in fact
65550). Once a generator *g* is found, a principal
2^{30}th root of unity is found by computing
*g ^{i}* mod

**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*^{229i} mod *m* =
*m*-1, where *i* and *m* are as above. Once we find
such an *a*, then *a*^{i} mod *m* is a
principal 2^{30}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*^{0} 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 *g*^{k} mod
*m* = *a*. Furthermore,
*g*^{k(m-1)/2} mod *m* = *m*-1
iff *k* is odd. Because (*m*-1)/2 = 2^{29}*i*,
it follows that *a*^{i} mod *m* is a
principal 2^{30}th root of unity with probability 1/2. By
contrast, because there are exactly 2^{29} principal
2^{30}th roots of unity and *m* > 2^{46}, the
probability that *a* is a principal 2^{30}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*^{i} is a principal
2^{30}th root of unity depends on that assumption.)

Copyright © Rod Howell, 2001, 2012. All rights reserved.

Rod Howell (rhowell@ksu.edu)

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