二元域上Cantor型仿射空间中多项式插值的计算方法与流程

计算机科学。

背景技术：

0、技术背景

1、多项式插值的快速计算是计算机算法理论中的一个重要课题，它在计算机科学、编码理论和密码学等领域中都有关键性作用。在计算机科学中，该课题可应用于多项式快速求根、多项式快速乘法、多项式快速除法和快速欧几里得算法。在编码理论中，该课题可应用于reed-solomon码的快速编码和bch码的快速译码。在密码学中，该课题可应用于线性递归序列的快速还原。

2、1989年cantor,d.g.在j.combin.theory,ser.a第50卷第2期上发表了题为“onarithmetical algorithms over finite fields”的文章。该文章给出了一个计算二元域上cantor型仿射空间中多项式插值的方法。该方法需要的乘法数量是o(nlog2 n)，而需要的加法数量是cantor方法在多项式快速求根、多项式快速乘法、多项式快速除法、快速欧几里得算法、reed-solomon的快速编码和bch码的快速译码上都有应用。

3、2010年gao,s.和mateer,t.在ieee trans.inform.第56卷第12期上发表题为“additive fast fourier transforms over finite fields,t.”的文章。该文章给出了一个计算二元域上2l维cantor型仿射空间中多项式插值的方法。该方法需要的乘法数量是o(nlog2 n)，而需要的加法数量是o(n(log2 n)log2 log2 n)。gao-mateer的方法在多项式快速求根和reed-solomon的快速编码中有应用。

4、cantor给出的计算二元域上cantor型仿射空间中多项式插值的方法的核心思想是把cantor型仿射空间分解成两个低一维的cantor型仿射子空间的并，进而把问题归结为计算该多项式的两个余式在二个cantor型仿射子空间中的插值。

5、gao-mateer给出的计算二元域上2l维cantor型仿射空间中多项式插值的方法是把问题归结为计算该多项式的个gao-mateer多项式在2l-1维cantor型仿射空间中的插值以及计算该多项式的个余式在2l-1维cantor型仿射空间中的插值。

6、gao-mateer同时给出了计算一个多项式的gao-mateer多项式的算法，我们把这个算法称为gao-mateer算法。

7、本发明公开了一种二元域上的cantor型仿射空间中多项式插值的计算方法。该方法先把问题归结为计算该多项式模一个cantor型三项式组的余式以及计算这些在2l-1维cantor型仿射空间中的插值，然后又把计算该多项式模一个cantor型三项式组的余式归结为计算该多项式的个gao-mateer多项式在m-2l-1维cantor型仿射空间中的插值。这里，m是该仿射空间的维数，而

8、本发明给出的方法需要的乘法数量是o(nlog2 n)，但需要的加法数量是o(n(log2n)log2 log2 n)。本发明在多项式快速乘法、多项式快速除法、快速欧几里得算法、reed-solomon的快速编码和bch码的快速译码上都有应用。

9、名称解释

10、二元域上仿射空间称为cantor型仿射空间，如果它包含于一个形如的有限域中，且它的向量空间有一组基底β1,β2,…,βm满足β1＝1,β22-β2＝β1,…,βm2-βm＝βm-1.

11、一组三项式称为一个cantor型三项式组，如果有正整数l及二元域上的cantor型仿射空间b,使得这组三项式等于

12、一个多项式f(x)在的gao-mateer多项式是一个多项式组它满足

13、

技术实现思路

1、本发明公开了一种计算二元域上的cantor型仿射空间中多项式插值的方法，这个方法有以下特征：

2、a)调用了一个计算多项式模一个cantor型三项式组的余式的方法；

3、b)把该多项式在该二元域上cantor型仿射空间中插值的计算归结为这些余式在该仿射空间的子空间中的插值的计算。当该仿射空间的维数是m时,这些子空间的维数是本发明公开了一种计算多项式模一个cantor型三项式组的余式的方法，这个方法分以下几个步骤：

4、a)用gao-mateer算法计算该多项式在一个线性化二项式处的gao-mateer多项式，这个二项式是该三项式的共有的线性化部分；

5、b)调用本发明公开的方法来计算这些gao-mateer多项式在该三项式组的常数项系数组成的仿射空间中的插值；

6、c)把每个gao-mateer多项式在该三项式组的常数项系数组成的仿射空间中的插值按序排成一行，再把这些行按序排成一个矩阵；

7、d)用这个矩阵的每一列作为系数构造一个多项式，并把所有这些新构造的多项式作为所求余式。本发明公开的二元域上cantor型仿射空间中多项式插值的计算方法分以下几个步骤：

8、a)把该二元域上cantor型仿射空间的维数记为m；

9、b)把该二元域上cantor型仿射空间正交投影点记为a；

10、c)当m＝1时，把(f(a),f(a+1))作为该多项式在该仿射空间中的插值并结束进程；

11、d)当m>1时，取并继续以下步骤；

12、e)令

13、f)把含有b的m-2l-1维cantor型仿射空间记为b；

14、g)调用本发明公开的方法计算该多项式模三项式组

15、的余式；

16、h)对每个余式，递归调用本方法来计算该余式在该余式对应的三项式的零点组成的仿射子空间中的插值；

17、i)把每个余式的插值排成一行，把这些行按序排成一个矩阵；

18、j)把这个矩阵中的元逐列排序，得到的序列作为该多项式在该仿射空间中的插值。

1.一种二元域上cantor型仿射空间中多项式插值的计算方法，所述方法有以下特征：

2.权利要求1的特征a,其所述的计算多项式模一个cantor型三项式组的余式的方法分以下几个步骤：

3.权利要求1所述的二元域上cantor型仿射空间中多项式插值的计算方法，所述方法分以下几个步骤：