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