Content deleted Content added
The article titled modulo is not mainly about modular arithmetic; fixing the link. |
|||
Line 26:
:<math>b_q = e^{-\frac{2\pi i}{n} g^{-q} }.</math>
===Evaluating the
Since ''n''–1 is composite, this convolution can be performed directly via the [[convolution theorem]] and more conventional FFT algorithms. However, that may not be efficient if ''n''–1 itself has large prime factors, requiring recursive use of Rader's algorithm. Instead, one can compute a length-(''n''–1) cyclic convolution exactly by zero-padding it to a length of at least 2(''n''–1)–1, say to a [[power of two]], which can then be evaluated in O(''n'' log ''n'') time without the recursive application of Rader's algorithm.
| |||