Fast modular transforms*

https://doi.org/10.1016/S0022-0000(74)80029-2Get rights and content
Under an Elsevier user license
open archive

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.

Cited by (0)

*

This research was supported by NRC Grants Nos. A-5549, A-7631, A-7641.