Fast modular transforms via division
- 1 October 1972
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02724847,p. 90-96
- https://doi.org/10.1109/swat.1972.5
Abstract
It is shown that the problem of evaluating an Nth degree polynomial is reducible to the problem of dividing the polynomial. A method for dividing an Nth degree polynomial by an N/2 degree polynomial in O(N log 2N) steps is given. Using this it is shown that the evaluation of an Nth degree polynomial at N points can be done in O(N log 3N). The related problem of computing of computing the resides of an N precision integer is handed by the same algorithm in O(N log2N loglogN) steps. Using the methods of Horowitz11 and Heindel8 it is shown that interpolation of an Nth degree polynomial is redicible to the problem of evaluating an Nth degree polynomial at N points. An algorithm for preconditioned polynomial interpolation requiring O(N log 2N) steps is presented. This is then extended to perform the complete interpolation in O(N log 3N) steps. A modified version of Reminider Problem in O(N log 2N loglogN) steps.Keywords
This publication has 9 references indexed in Scilit:
- A fast method for interpolation using preconditioningInformation Processing Letters, 1972
- Polynomial evaluation via the division algorithm the fast Fourier transform revisitedPublished by Association for Computing Machinery (ACM) ,1972
- Evaluating polynomials at many pointsInformation Processing Letters, 1971
- The Calculation of Multivariate Polynomial ResultantsJournal of the ACM, 1971
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- Schnelle Multiplikation großer ZahlenComputing, 1971
- The Fast Fourier Transform in a Finite FieldMathematics of Computation, 1971
- Exact solution of linear equationsPublished by Association for Computing Machinery (ACM) ,1971
- Chinese remainder and interpolation algorithmsPublished by Association for Computing Machinery (ACM) ,1971