**Authors:** Sean Murphy and Maura Paterson

**Reference: **RHUL-MA-2007-4

**Abstract**

This paper considers the geometric properties of the

Relinearisation algorithm and of the XL algorithm used in

cryptology for equation solving. We give a formal description of

each algorithm in terms of projective geometry, making particular

use of the Veronese variety. We establish the fundamental

geometrical connection between the two algorithms and show how

both algorithms can be viewed as being equivalent to the problem

of finding a matrix of low rank in the linear span of a collection

of matrices, a problem sometimes known as the MinRank problem.

Furthermore, we generalise the XL algorithm to a geometrically

invariant algorithm, which we term the GeometricXL algorithm. The

GeometricXL algorithm is a technique which can solve certain

equation systems that are not easily soluble by the XL algorithm

or by Groebner basis methods.

Download the full report from this page.

_{posted 21 May 2007}