Fast Modular Transforms via Division
Fast Modular Transforms via Division
复制标题
通过除法进行快速模块化转换
DOI：
10.1109/swat.1972.5
复制
发表时间：
1972
期刊：
影响因子：
--
通讯作者：
A. Borodin
中科院分区：
文献类型：
--
作者：
R. Moenck;A. Borodin
它表明，评估一个N次多项式的问题是可约化的多项式的划分问题。给出了一种用N/2次多项式除N次多项式的方法，时间复杂度为O（Nlog 2N）。使用这表明，在N点的N次多项式的评价可以在O（N log 3 N）。计算N精度整数的余数的相关计算问题也可以通过相同的算法以O（N log 2N loglogN）步来处理。利用Horowitz [11]和Heindel [8]的方法，证明了N次多项式的插值可归结为在N个点上求N次多项式的值的问题。提出了一种预条件多项式插值的算法，该算法需要O（Nlog 2N）步。然后，这是扩展到执行完整的插值在O（N log 3 N）的步骤。一个修改版本的Reminider问题，时间复杂度为O（N log 2N loglogN）。
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.