Cryptography Reference
In-Depth Information
We will need the following in the text, for example, when we talk about
secret-sharing schemes on page 215.
Theorem A.26
(
Cramer's Rule
)
Let
A
=(
a
i,j
)
be the
coeGcient matrix
of the following system of
n
linear
equations in
n
unknowns:
a
1
,
1
x
1
+
a
1
,
2
x
2
+
···
+
a
1
,n
x
n
=
b
1
a
2
,
1
x
1
+
a
2
,
2
x
2
+
···
+
a
2
,n
x
n
=
b
2
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
a
n,
1
x
1
+
a
n,
2
x
2
+
···
+
a
n,n
x
n
=
b
n
,
over a field
F
.If
det(
A
)
=0
, then the system has a solution given by
n
1)
i
+
j
b
i
det(
A
i,j
)
,
(1
1
det(
A
)
x
j
=
(
−
≤
j
≤
n
)
.
i
=1
Of particular importance is a special matrix called the
Vandermonde matrix
,
of order
t>
1, which is given as follows:
x
t
−
1
1
1
x
1
···
x
t
−
1
2
1
x
2
···
A
=
,
.
.
.
.
x
t
−
1
t
1
x
t
···
where
det(
A
)=
1
(
x
k
−
x
i
)
≤
≤
i<k
t
is the
Vandermonde determinant
.
A notion that uses vector spaces and matrix theory is the following, which
we will use in Appendix C, for instance.
Gaussian Elimination
The term
Gaussian elimination
refers to an eGcient algorithm for finding
linear dependency relations among vectors in a vector space over a suitable field.
Suppose that we have vectors
v
j
=(
v
1
,j
,v
2
,j
,...,v
n,j
) for
j
=1
,
2
,...,m
over
a field
F
. We seek field elements
c
1
,c
2
,...,c
m
∈
F
such that
m
c
j
v
j
=
0
,
(A.4)
i
=
j
Search WWH ::
Custom Search