Multiplication algorithm: Difference between revisions

Revision as of 11:23, 24 March 2018

Revision as of 13:16, 24 April 2018

Line 359:

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²)'' time.

To remain in the modular setting of Fourier transforms, we look for a ring with a ''2m^th'' root of unity. henceHence 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 </math>