Content deleted Content added
CLCStudent (talk | contribs) m Reverted 1 edit by 2605:E000:1317:83B6:34CA:E3EC:B754:A9A0 (talk) to last revision by Matthiaspaul (TW) |
|||
Line 347:
Then we can then say that,
: <math>ab=\sum_{i=0}^{m-1} \sum_{j=0}^{m-1} a_i b_j x^{(i+j)} = \sum_{k=0}^{2m-2} c_k x^{k}
Clearly the above setting is realized by polynomial multiplication, of two polynomials ''a'' and ''b''. The crucial step now is to use [[Discrete Fourier transform#Polynomial multiplication|Fast Fourier multiplication]] of polynomials to realize the multiplications above faster than in naive ''O(m<sup>2</sup>)'' time.
Line 353:
To remain in the modular setting of Fourier transforms, we look for a ring with a ''2m<sup>th</sup>'' root of unity. Hence we do multiplication modulo ''N'' (and thus in the ''Z/NZ'' [[Ring (mathematics)|ring]]). Further, N must be chosen so that there is no 'wrap around', essentially, no reductions modulo N occur. Thus, the choice of N is crucial. For example, it could be done as,
: <math> N = 2^{3w} + 1
The ring ''Z/NZ'' would thus have a ''2m<sup>th</sup>'' root of unity, namely 8. Also, it can be checked that ''c<sub>k</sub> < N'', and thus no wrap around will occur.
| |||