摘要: 针对多变量二次方程组的求解问题,对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
中图分类号:
张帆, 李蕾, 熊炎. XL算法的冗余分析与改进?[J]. 计算机工程, 2011, 37(16): 60-61.
ZHANG Fan, LI Lei, XIONG Tan. Redundancy Analysis and Improvement of XL Algorithm[J]. Computer Engineering, 2011, 37(16): 60-61.