Title :
Independence analysis of equations extended by XL algorithm
Author :
Zhang, Fan ; Guo, Xuzhan ; Song, Junhui
Author_Institution :
Coll. of Comput. & Inf. Technol., Xinyang Normal Univ., Xinyang, China
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.
Keywords :
computational complexity; cryptography; polynomials; NP-hard; XL algorithm; cryptosystems; equations independence analysis; extended linearization algorithm; multiple quadratic equation systems; n-variable quadratic equations; Algorithm design and analysis; Computational complexity; Computer science; Cryptography; Polynomials; Redundancy;
Conference_Titel :
Advanced Computational Intelligence (IWACI), 2011 Fourth International Workshop on
Conference_Location :
Wuhan
Print_ISBN :
978-1-61284-374-2
DOI :
10.1109/IWACI.2011.6160093
