期刊文献+

一种基于竞争策略的稀疏多元多项式插值算法 被引量:1

A Sparse Polynomial Interpolation Based on Racing Strategy
原文传递
导出
摘要 提出了一个有限域上的基于竞争策略的稀疏多元多项式插值算法,改进了Javadi和Monagan在2010年提出的概率性插值算法.对n个变元,t个非零项的多元多项式f进行插值,Javadi/Monagan算法要求给定f的全次数上界d,为确定变元x_j在第i个单项式中的次数,需要从O到d做d+1次根测试,每个变元测试次数为O(td).改进算法设计了两个子算法并采用竞争策略用尽可能少的插值点准确计算变元x_j在多项式f中的次数集,使得测试次数降为O(td'),其中d'为变元x_j在f中出现的次数集的基数,因而减小了测试次数及根冲突的概率.在Maple环境下实现了改进算法,Zippel算法和Javadi/Monagan算法,给出了测试用例对3种算法的插值点个数及其CPU运行时间进行了比较. In this paper, we present a sparse polynomial interpolation algorithm based on racing strategy over finite fields. Our algorithm modifies the probabilistic algorithm of Javadi and Monagan from 2010 for interpolating polynomials. To interpolate a polynomial f in n variables with t non-zero terms, Javadi/Monagan algorithm requires d the bound on the degree of f to be given in advance. To determine the degrees of each monomial of f in each variable, Javadi/Monagan algorithm needs to check the roots using O(td) probes in a loop from 0 to d. The improved algorithm contains two sub-algorithms and uses racing strategy to compute the exact degrees of each monomial of f in xj as small as probes possible. The total tests turn to be O(td’), where d’ is the cardinality of degree set of each variable in f. Thus the total tests and the probability of root clash of the improved algorithm are decreased. We have implemented the improved algorithm, Zippel’s algorithm and Javadi/Monagan algorithm in Maple. In the paper, we provide benchmarks comparing the number of probes and CPU running time our algorithm does with both Zippel’s algorithm and Javadi/Monagan algorithm.
作者 邓国强 唐敏 张永燊 DENG Guoqiang;TANG Min;ZHANG Yongshen(Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electrical Technology, Guilin 541004)
出处 《系统科学与数学》 CSCD 北大核心 2018年第12期1436-1448,共13页 Journal of Systems Science and Mathematical Sciences
基金 国家自然科学基金(11561015) 广西科技基地和人才专项(2018AD19050) 广西高校中青年教师基础能力提升项目(2018KY0210) 广西密码学与信息安全重点实验室研究课题(GCIS201615) 国家级大学生创新训练计划项目(201810595024)资助课题
关键词 稀疏多元多项式插值 竞争策略 Javadi/Monagan算法 Zippel算法 Sparse multivariate polynomial interpolation Racing strategy Javadi/ Monagan algorithm Zippel's algorithm
  • 相关文献

同被引文献10

引证文献1

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部