Information Technology Reference
In-Depth Information
The link between XL and computing Grobner bases was established in [12].
Their computer simulations show that XL do not seem to follow the proposed
bound D
n
m , but behave much worse. They also compare Faugeres F 4
Grobner basis algorithm with XL, and show that F 4 computes a Grobner basis
in less time, using less space. This conclusion is not very surprising, as XL tries
to compute a Grobner basis, but spends huge amount of time computing depen-
dent equations, such that the reduction step spends an equal amount of time
computing zero. The difference from other Grobner basis algorithms is that XL
contains no strategies nor avoid linear dependencies. So XL can be said to be a
worst kind of Grobner basis algorithm.
In [5], Yang and Chen describe a formula for estimating D , but as they men-
tion, their formula is neither trivialtousenorprovedtobecorrect.
2 Preliminaries
x i + x i } 1 ≤i≤n denote the ring of Boolean functions in
n variables x 1 ,x 2 ,...,x n which satisfy the relation x i
Let λ =
F 2 [ x 1 , ..., x n ] /
{
+ x i
=0since x i F 2 .
f
F 2 ,onthe n -dimensional vector space
2
Then an f
λ defines a function
F
F
2 ,withvaluesin
F 2 . We define a set of polynomials by
F =
{
f 1 ( x 1 , ..., x n ) , ..., f m ( x 1 , ..., x n )
}⊆
λ
and the associated system of equations
E =
{
f 1 ( x 1 , ..., x n )=0 , ..., f m ( x 1 , ..., x n )=0
}
.
We associate a function over
F 2 with its coecient vector, so to avoid confusion
we introduce notation for this.
λ .Wedenoteby [ f ] the vector indexed by the 2 n mono-
mials in λ , which contains a 1 at indices where the corresponding monomial
appear in f and 0 otherwise, with respect to some monomial ordering. We call
[ f ] the coecient vector of f .Whenwriting
Definition 1. Let f
m
[ f ] for a monomial
m
,wewill
mean [
f ] . This is well-defined, so for a polynomial g , g [ f ] (a sum of vectors)
is equal to [ gf ] .
m
2.1 The XL Algorithm
Let F be a system of m polynomials of degree D e . We associate a number D m
N
is a monomial.
Further let D = D e + D m ,andlet λ ≤d denote the span of the monomials of
degree less than or equal to d . XL will construct a new system U D ,formedby
multiplying each polynomial in F with all monomials of degree less than or equal
to D m ,thatis, U D = λ ≤D m
, such that XL is constrained by 1
deg(
m
)
D m ,where
m
F .Then U D will contain polynomials satisfying 0
deg( f i )
D . The version of XL defined in [10] consider only quadratic systems,
but we generalize our analysis and consider polynomial systems of any degree
D e . XL constructs a set of polynomials U D , satisfying the following properties:
Search WWH ::




Custom Search