摘要
对J.von zur Gathen和I.E.Shparlinski提出的有限域上乘法噪音多项式插值算法进行了分析,提出了改进算法.利用L.Babai最近向量格归约算法得到更精确的估计向量,再计算出插值多项式的倍数多项式的系数,从而计算出原插值多项式的系数.改进算法降低了原算法中有限域阶的下界,对较小阶有限域上的多项式也可以进行乘法噪音插值.
This paper analyses a multiplicative noisy polynomial interpolation algorithm in the finite field presented by J. yon zur Gathen and I. E. Shparlinski and presents an amended algorithm. By the lattice reduction algorithm on the nearest vector presented by L. Babai, a more accurate estimate vector can be obtained and the coefficients of the multiple polynomial of the interpolation polynomial can be computed. Then the coefficients of the original interpolation polynomial can be computed. The amended algorithm reduces the lower bound of the order of the finite field and can apply to the polynomials in the finite field whose order is lower.
出处
《西安电子科技大学学报》
EI
CAS
CSCD
北大核心
2007年第3期360-362,397,共4页
Journal of Xidian University
基金
国家自然科学基金(60473028)
关键词
多项式插值
模乘近似黑盒
格归约
polynomial interpolation
modular multiplicatively approximate black box（MMABB）
lattice reduction
