Fast modular transforms

摘要

It is shown that if division and multiplication in a Euclidean domain can be performed in O(N loga N) steps, then the residues of an N precision element in the domain can be computed in O(N loga+1 N) steps. A special case of this result is that the residues of an N precision integer can be computed in O(N log2 N log log N) total operations. Using a polynomial division algorithm due to Strassen [24], it is shown that a polynomial of degree N−1 can be evaluated at N points in O(N log2 N) total operations or O(N log N) multiplications.Using the methods of Horowitz [10] and Heindel [9], it is shown that if division and multiplication in a Euclidean domain can be performed in O(N loga N) steps, then the Chinese Remainder Algorithm (CRA) can be performed in O(N loga+1 N) steps. Special cases are: (a) the integer CRA can be performed in O(N log2 N log log N) total operations, and (b) a polynomial of degree N−1 can be interpolated in O(N log2 N) total operations or O(N log N) multiplications. Using these results, it is shown that a polynomial of degree N and all its derivatives can be evaluated at a point in O(N log2 N) total operations.