邓国强，唐敏，张永燊

桂林电子科技大学广西密码学与信息安全重点实验室, 桂林 541004

出版日期:2018-12-25发布日期:2019-02-22

A Sparse Polynomial Interpolation Based on Racing Strategy

DENG Guoqiang ,TANG Min, ZHANG Yongshen

Guangxi Key Laboratory of Cryptography and Information Security, Guilin University of Electrical Technology, Guilin 541004

Online:2018-12-25Published:2019-02-22







摘要
图/表
参考文献
相关文章
编辑推荐
-->Metrics
本文评论

提出了一个有限域上的基于竞争策略的稀疏多元多项式插值算法, 改进了Javadi和 Monagan在2010年提出的概率性插值算法. 对$n$个变元, $t$个非零项 的多元多项式$f$进行插值, Javadi/Monagan算法要求给定$f$的全次数上界$d$, 为确定变元$x_j$在第$i$个单项式中的次数, 需要从$0$到$d$做$d+1$次根测试, 每个变元测试次数为${\bm O}(td)$. 改进算法设计了两个子算法并采用竞争策略用尽可能少的插值点准确计算变元$x_j$在多项式$f$中的次数集, 使得测试次数降为${\bm O}(td')$, 其中$d'$为变元$x_j$在$f$中出现的次数集的基数, 因而减小了测试次数及根冲突的概率. 在Maple环境下实现了改进算法, Zippel算法和Javadi/Monagan算法, 给出了测试用例对3种算法的插值点个数及其CPU运行时间进行了比较.

分享此文:

()

No related articles found!

-->

PDF全文下载地址:

http://sysmath.com/jweb_xtkxysx/CN/article/downloadArticleFile.do?attachType=PDF&id=13500