Multiplication using FFT in integer rings

2
votes

I need to multiply long integer numbers with an arbitrary BASE of the digits using FFT in integer rings. Operands are always of length n = 2^k for some k, and the convolution vector has 2n components, therefore I need a 2n'th primitive root of unity.

I'm not particularly concerned with efficiency issues, so I don't want to use Strassen & Schönhage's algorithm - just computing basic convolution, then some carries, and that's nothing else.

Even though it seems simple to many mathematicians, my understanding of algebra is really bad, so I have lots of questions:

  1. What are essential differences or nuances between performing the FFT in integer rings modulo 2^n + 1 (perhaps composite) and in integer FIELDS modulo some prime p?

    I ask this because 2 is a (2n)th primitive root of unity in such a ring, because 2^n == -1 (mod 2^n+1). In contrast, integer field would require me to search for such a primitive root.

    But maybe there are other nuances which will prevent me from using rings of such a form for the FFT.

  2. If I picked integer rings, what are sufficient conditions for the existence of 2^n-th root of unity in this field?

    All other 2^k-th roots of unity of smaller order could be obtained by squaring this root, right?..

  3. What essential restrictions are imposed on the multiplication by the modulo of the ring? Maybe on their length, maybe on the numeric base, maybe even on the numeric types used for multiplication.

    I suspect that there may be some loss of information if the coefficients of the convolution are reduced by the modulo operation. Is it true and why?.. What are general conditions that will allow me to avoid this?

  4. Is there any possibility that just primitive-typed dynamic lists (i.e. long) will suffice for FFT vectors, their product and the convolution vector? Or should I transform the coefficients to BigInteger just in case (and what is the "case" when I really should)?

If a general answer to these question takes too long, I would be particularly satisfied by an answer under the following conditions. I've found a table of primitive roots of unity of order up to 2^30 in the field Z_70383776563201:

http://people.cis.ksu.edu/~rhowell/calculator/roots.html

So if I use 2^30th root of unity to multiply numbers of length 2^29, what are the precision/algorithmic/efficiency nuances I should consider?..

Thank you so much in advance! I am going to award a bounty to the best answer - please consider helping out with some examples.

2
mathfftmultiplicationarbitrary-precision
Try here for more theoretical numerical analysis questions: scicomp.stackexchange.com – tskuzzy
This is a very advanced question - and I'm probably one of the few people who has actual hands-on experience in this area to be able to answer it. But it's too big to be answered on SO. It would require pages and pages of text + diagrams... – Mysticial
I see... But will the basic facts without proofs take this many pages? Maybe, for proofs, I could find directions with your help. Also, I put a special restriction at the end of the question which particularly concerns me. I owe some beers to he who would answer this even in a not particularly deep manner. – wh1t3cat1k

2 Answers

2
votes

First, an arithmetic clue about your identity: 70383776563201 = 1 + 65550 * 2^30. And that long number is prime. There's a lot of insight into your modulus on the page How the FFT constants were found.

Here's a fact of group theory you should know. The multiplicative group of integers modulo N is the product of cyclic groups whose orders are determined by the prime factors of N. When N is prime, there's one cycle. The orders of the elements in such a cyclic group, however, are related to the prime factors of N - 1. 70383776563201 - 1 = 2^31 * 3^1 * 5^2 * 11 * 13, and the exponents give the possible orders of elements.

(1) You don't need a primitive root necessarily, you need one whose order is at least large enough. There are some probabilistic algorithms for finding elements of "high" order. They're used in cryptography for ensuring you have strong parameters for keying materials. For numbers of the form 2^n+1 specifically, they've received a lot of factoring attention and you can go look up the results.

(2) The sufficient (and necessary) condition for an element of order 2^n is illustrated by the example modulus. The condition is that some prime factor p of the modulus has to have the property that 2^n | p - 1.

(3) Loss of information only happens when elements aren't multiplicatively invertible, which isn't the case for the cyclic multiplicative group of a prime modulus. If you work in a modular ring with a composite modulus, some elements are not so invertible.

(4) If you want to use arrays of long, you'll be essentially rewriting your big-integer library.

1
votes

Suppose we need to calculate two n-bit integer multiplication where 

n = 2^30;
m = 2*n; p = 2^{n} + 1

Now, w = 2, x =[w^0,w^1,...w^{m-1}] (mod p).

The issue, for each x[i], it will be too large and we cannot do w*a_i in O(1) time.