View Single Post
Old 2002-10-28, 21:03   #10
ewmayer's Avatar
Sep 2002
Rep├║blica de California

2D8A16 Posts

Originally Posted by Kevin
I believe for the example given, a FFT size of 2 was used. The general formula uses cos(pi/n)+i sin(pi/n) , which reduces to i for a FFT size of 2.
No, the (n)th complex roots of unity are given by
exp(i*2*pi/n) = cos(2*pi/n)+i*sin(2*pi/n). The reason one sees the i's
in my example is that to DFT-multiply two general length-2 numbers, one
must zero-pad the input vectors to double the number of input digits, i.e.
one must use a length-4 DFT. Note that for modular multiplication
for certain moduli of special form (which happen to include the Mersenne
numbers), one can use additional clever tricks to avoid the zero-padding.
That's because a length-n discrete cyclic convolution (working with base-X
inputs, where X need not be 10) is really a polynomial multiplication
modulo X^n - 1. That means that in my example, if I had used a length-2
DFT instead of length-4 (and recall that I was using X = 10), I would have
still obtained the correct result, but only in the sense that it is correct
modulo 10^2 - 1 = 99. Let's try it:

We again DFT-multiply 12 and 23 using base-10 arithmetic,
but this time we don't pad our input vectors with zeros.
Thus, our input vectors are A = (2,1) and B = (3,2), where the
least-significant digit of each number is leftmost. The Fourier transform
of a length-2 vector (a,b) is given in matrix-multiply form as

|+1 +1| |a| a+b
|+1 -1|*|b|=a-b .

Doing this for our two input vectors, our transformed vectors are
A^ = (3, 1) and B^ = (5, 1). The Fourier-transformed discrete
convolution of A and B is then simply A^*B^, where the '*' means dyadic
multiply, which gives (15, 1). To get the digits of the product
we're after, we need to inverse-Fourier-transform this vector. For length-2
vectors, the IFT looks just like the FT, but with a factor of one-half
multiplying the whole thing.

That is, the length-2 IFT of our vector (15, 1) has entries (16, 14)/2 = (8, 7).

Since all the output digits happen to be < 10 and nonnegative, we don't
need to do any carry step, and since the outputs are least-significant
first, our result (written in normal decimal order) is 78. The exact
(full) product is 12*23 = 276, which indeed == 78 modulo 99.

ewmayer is online now   Reply With Quote