有限域上乘法噪音多项式插值算法的改进  

Improved multiplicative noisy polynomial interpolation algorithm in the finite field

作　　者：黄华伟[1] 李胜强[1] 陈汝伟[1] 肖国镇[1] 

机构地区：[1]西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071

出　　处：《西安电子科技大学学报》2007年第3期360-362,397,共4页Journal of Xidian University

基　　金：国家自然科学基金(60473028)

摘　　要：对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.

关 键 词：多项式插值 模乘近似黑盒 格归约 

分 类 号：TN918[电子电信—通信与信息系统]