Content deleted Content added
mNo edit summary |
clarification |
||
Line 24:
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 cyclic convolution exactly by zero-padding it into a linear convolution of at least twice the length, 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.
This algorithm, then, requires O(''n'') additions plus O(''n'' log ''n'') time for the convolution. In practice, the O(''n'') additions can often be performed
If Rader's algorithm is performed by using FFTs of size ''n''-1 to compute the convolution, rather than by zero padding as mentioned above, the efficiency depends strongly upon ''n'' and the number of times that Rader's algorithm must be applied recursively. The worst case would be if ''n''-1 were 2''n''<sub>2</sub> where ''n''<sub>2</sub> is prime, with ''n''<sub>2</sub>-1 = 2''n''<sub>3</sub> where ''n''<sub>3</sub> is prime, and so on. In such a case, the application of Rader's algorithm would actually require O(''n''<sup>2</sup>) time. Such ''n''<sub>j</sub> are called [[Sophie Germain prime|Sophie Germain primes]], and the sequence of them is called a [[Cunningham chain]]. The length of Cunningham chains, however, grows more slowly than log<sub>2</sub>(''n''), so Rader's algorithm applied in this way is not O(''n''<sup>2</sup>), but it is probably worse than O(''n'' log ''n'') for the worst cases. Fortunately, a guarantee of O(''n'' log ''n'') complexity can be achieved by using zero padding.
| |||