-
题名Dixon结式在密码学中的应用
被引量：9
- 1
-
-
作者
唐樨瑾
冯勇
-
机构
中国科学院成都计算机应用研究所自动推理实验室
-
出处
《软件学报》
EI
CSCD
北大核心
2007年第7期1738-1745,共8页
-
基金
国家重点基础研究发展计划(973)No.2004CB318003~~
-
文摘
针对密码学中的多变元多项式二次方程系统求解问题,基于扩展Dixon结式提出了一种求解算法DR(Dixon resultants).基本思想为对于MQ(multivariate quadratic)问题,把x1,x2,…,xn?1当作变元,而把xn当作参数,然后利用和改进扩展Dixon结式方法求解该类系统.分析了该算法对于一般情况的复杂度,并且基于实验证据猜测:对于某些稀疏问题,新算法的复杂度很有可能也是多项式的.实验结果表明,对于m=n的一般和稀疏的问题,DR效率优于已有的两种算法.除了高效性,新算法还具有复杂度容易度量、计算时间可以预测的优点.
-
关键词
多变元密码学
有限域上的多项式方程
代数攻击
DIXON
结式
DR(Dixon
resultants)
-
Keywords
multivariate cryptography
polynomial equations over finite field
algebraic attack
Dixon resultants
DR （Dixon resultants）
-
分类号
TP309
[自动化与计算机技术—计算机系统结构]
-
-
题名一种改进的伪除算法
- 2
-
-
作者
唐樨瑾
李永彬
-
机构
中国科学院成都计算机应用研究所
-
出处
《计算机应用》
CSCD
北大核心
2006年第B06期139-140,共2页
-
基金
国家973规划项目(2004CB318003)
-
文摘
近来提出了一个通过计算一种新型矩阵的行列式的值来计算伪余的伪除算法(newprem)。改进了newprem中利用高斯消元法的方式,尽量可能地克服过原算法中程膨胀,消除冗余运算。实验结果显示改进后的算法newprem2计算效率优于newprem算法。newprem2可以和原有经典算法prem形成互补,两者结合使用,可以提高众多消去法的效率。
-
关键词
多项式
行列式的值
伪除
高斯消元
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
