Information Technology Reference
In-Depth Information
We then examine the parity of the number of 1's in these columns. After substi-
tuting, (4) can be written as
s
s
f
e
j
−
1
i
j
f
e
k
−
1
i
k
m
·
(
f
i
j
+(
e
j
−
1mod2 )
(
f
i
k
+(
e
k
−
1mod2
r
(
···
···
···
)
j
=1
k
=1
,k
=
j
t
f
e
j
−
2
i
j
+
m
·
(
f
i
j
+(
e
j
−
1
mod 2))(
f
i
j
+(
e
j
−
2mod2
r
(
···
···
)
.
(5)
j
=1
Each term in (5) represents a 1 in the column in
H
i−
1
corresponding to the
same term. In the double sum where
j
f
e
j
−
1
i
j
f
e
k
−
1
i
k
) will
occur exactly twice, once when
j<k
and once when
j>k
.Bothtimesthe
polynomials to be multiplied with
r
(
=
k
,each
r
(
···
···
···
f
e
j
−
1
i
j
f
e
k
−
1
i
k
···
···
···
) will be
m
(
f
i
j
+(
e
j
−
1 mod 2))(
f
i
k
+(
e
k
−
1 mod 2)), so the number of 1's in columns involving
f
e
j
−
1
i
j
f
e
k
−
1
i
k
r
(
···
···
···
) is even. For the remaining single sum, we note that
f
i
j
f
i
j
2 is 1 mod 2 and the other is
0 mod 2. Multiplying out the brackets in the single sum we get
=
f
i
j
and that exactly one of
e
j
−
1and
e
j
−
m
(
f
i
j
+
f
i
j
)=0
f
e
j
−
2
i
j
mod 2 in front of each
r
(
···
···
), so the number of 1's in columns involving
f
e
j
−
2
i
j
r
(
···
···
)isalsoeven.
We are now ready to proceed to the main result, an estimation of the number
of linearly independent equations generated by the XL-method.
Theorem 2.
Let
I
be the number of linearly independent equations generated by
the XL-method on a system of
m
equations in
n
variables, where each equation
has degree
D
e
and we multiply with all monomials of degree
D
m
.Iftheonly
linear dependencies among the rows of
H
i−
1
are the ones indicated by
H
i
,then
≤
1)
i
m
+
i
i
+1
D
m
−i·D
e
n
j
.
D
D
e
I
=
−
(
i
=0
j
=0
Proof.
By the construction of the matrices
H
i
,wehave
I
=rank(
H
0
). Let
the number of rows in
H
i
be
b
i
.Ifalltherowsof
H
i
are linearly independent
we will have rank(
H
i−
1
)=
b
i−
1
−
b
i
. However, there will in general be linear
dependencies also between the rows of
H
i
, so the correct expression will be
D
D
e
rank(
H
i−
1
)=
b
i−
1
−
rank(
H
i
)
,i
=1
,...
.
(6)
The matrix
H
since there is no
H
-matrix coming
after it. By recursively using (6) for substituting the expressions for rank(
H
i
)
we have the following formula
will have full rank
b
D
D
e
D
D
e
D
D
e
1)
i
b
i
.
I
=rank(
H
0
)=
(
−
(7)
i
=0
