Information Technology Reference
In-Depth Information
To finish, we need to compute
b
i
,thenumberofrowsin
H
i
.Therowsof
H
i
are
indexed by
D
e
and
j
=1
e
j
=
i
+1.
r
(
f
e
1
i
1
f
e
2
f
e
s
m
·
···
i
s
), where deg(
m
)
≤
D
m
−
i
·
i
2
j
=0
j
.Thenumberofwaystomakea
product of
i
+ 1 equations by picking equations from the total set of
m
equations
is
D
m
−i·D
e
The number of choices for
m
is the number of ways to throw
i
+ 1 balls into
m
bins. This number is
m
+
i
i
+1
by
[9]. We then get
b
i
=
m
+
i
i
+1
D
m
−i·D
e
n
j
,
j
=0
and substituting this into (7) gives us the desired expression.
We restrict our analysis to systems which only contain trivial dependencies. This
means that our formula is not correct for initial systems containing other types
of dependencies. One example of non-trivial dependencies are systems containing
nonlinear dependencies.
6 Linking Theorem 2 to Theorem/Conjecture from
Related Work
We are aware of three papers by Yang and Chen (one also with Courtois) [5],
[6] and [7] which, among other things, try to estimate the number of linearly
independent equations generated by the XL-method. Their result uses the no-
tation [
t
D
]
p
(
t
), which represents the coecient of the
D
'th-degree term in the
polynomial (or series)
p
(
t
). For an instance of the XL algorithm where the initial
equations all have degree
k
,let
T
be the number of monomials generated, and
let
I
be the number of linearly independent equations. For
F
2
, their result from
[5] is as follows.
Theorem 3
[
t
D
]
1
n
1
m
t
2
t
k
1
−
−
T
−
I
≥
1
−
t
1
−
t
1
−
t
2
k
when
D<D
reg
,where
D
reg
is the degree of the first term with a negative
coecient in the series.
In [5] there is a proof of the theorem for
k
= 2, but this proof has been shown
to be flawed. In [6] they write “As pointed out by C. Diem, the [5] proof is
inaccurate.... In any event, since it is also confirmed by many simulations we
will henceforth assume Theorem 3 holds in general...” In [7] they write “The [5]
proof was faulty...”
Theorem 3 seeks to give an upper bound on the number of linearly indepen-
dent equations we can get from XL. With the extra assumption in Theorem 2,
saying that the only linear dependencies occurring are the ones we can identify,
Theorem 3 could be stated with equality. Below we will find the link between
Theorems 2 and 3, showing that these two results indeed say the same things
