作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2011, Vol. 37 ›› Issue (16): 60-61. doi: 10.3969/j.issn.1000-3428.2011.16.020

• 软件技术与数据库 • 上一篇    下一篇

XL算法的冗余分析与改进?

张 帆,李 蕾,熊 炎   

  1. (信阳师范学院计算机与信息技术学院,河南 信阳 464000)
  • 收稿日期:2011-01-12 出版日期:2011-08-20 发布日期:2011-08-20
  • 作者简介:张 帆(1982-),女,讲师、硕士,主研方向:信息安全;李 蕾、熊 炎,讲师、硕士
  • 基金资助:
    河南省自然科学基金资助项目(102102210242)

Redundancy Analysis and Improvement of XL Algorithm

ZHANG Fan, LI Lei, XIONG Yan   

  1. (College of Computer and Information Technology, Xinyang Normal University, Xinyang 464000, China)
  • Received:2011-01-12 Online:2011-08-20 Published:2011-08-20

摘要: 针对多变量二次方程组的求解问题,对XL算法的冗余性进行分析与改进。用XL算法扩展方程组存在冗余现象,采用该算法扩展由m个方程构成的n元二次方程组,所得到的新方程组中线性独立方程个数的上界为[mn(n+3)?m(m?3)]/2。基于此,对XL算法进行改进。分析表明,改进后的XL算法能降低求解多变量二次方程组的计算复杂性。

关键词: 重复线性化, XL算法, 代数攻击, 高斯消元, 计算复杂性

Abstract: Aiming at problems of solving multiple quadratic equation systems, the redundancy of extending equations by Extended Linearization (XL) algorithm is analyzed. It is proved that there is redundancy in equations extended by XL algorithm. The upper bound, [mn(n+3)?m(m?3)]/2, of the number of linearly independent equations in the new system of equations, which extends from n-variable quadratic equations consisting of m equations, is given. The algorithm is obtained to overcome the redundancy problem and XL algorithm is improved, which effectively reduces the computational complexity of solving multi-variable quadratic equation system.

Key words: relinearization, Extended Linearization(XL) algorithm, algebraic attack, Gaussian elimination, computational complexity

中图分类号: