Cryptography Reference
In-Depth Information
This is a special case of Garner's algorithm (see Section 14.5.2 of [
376
] or Section 10.6.4
of [
16
]).
Exercise 2.6.1
Suppose
m
1
<m
2
and 0
c
i
<m
i
. What is the input size of the instance
of the CRT? What is the complexity of computing the solution?
≤
≤
···
Exercise 2.6.2
Let
n>
2 and suppose coprime integers 2
m
1
<
<m
n
and integers
=
i
=
1
m
i
.For1
≤
≤
≤
≤
≤
c
1
,...,c
n
such that 0
c
i
<m
i
for 1
i
n
are given. Let
N
i
n
N
−
1
i
define
N
i
=
N/m
i
and
u
i
=
(mod
m
i
). Show that
n
x
=
c
i
u
i
N
i
(2.1)
i
=
1
satisfies
x
n
.
Show that one can compute the integer
x
in equation (
2.1
)in
O
(
n
2
log(
m
n
)
2
) bit opera-
tions.
≡
c
i
(mod
m
i
) for all 1
≤
i
≤
Exercise 2.6.3
Show that a special case of Exercise
2.6.2
(which is recommended when
many computations are required for the same pair of moduli) is to precompute the integers
A
=
u
1
N
1
and
B
=
u
2
N
2
so that
x
=
c
1
A
+
c
2
B
(mod
N
).
Algorithm 10.22 of [
220
] gives an asymptotically fast CRT algorithm.
2.7 Linear algebra
Let
A
be an
n
×
n
matrix over a field
k
. One can perform Gaussian elimination to solve
the linear system
A
x
b
(or determine there are no solutions), to compute det(
A
)orto
compute
A
−
1
in
O
(
n
3
) field operations. When working over
=
a number of issues arise due
to rounding errors, but no such problems arise when working over finite fields. We refer to
Section 3.3 of Joux [
283
] for details.
A matrix is called
sparse
if almost all entries of each row are zero. To make this precise
one usually considers the asymptotic complexity of an algorithm on
m
R
n
matrices, as
m
and/or
n
tends to infinity, and where the number of non-zero entries in each row is bounded
by
O
(log(
n
)) or
O
(log(
m
)).
One can compute the kernel (i.e., a vector
x
such that
A
x
×
=
×
n
sparse
matrix
A
over a field in
O
(
n
2
) field operations using the algorithms of Wiedemann [
562
]
or Lanczos [
325
]. We refer to Section 3.4 of [
283
] or Section 12.4 of [
220
] for details.
0
)ofan
n
Hermite normal form
When working over a ring the Hermite normal form (HNF) is an important tool for solving
or simplifying systems of equations. Some properties of the Hermite normal form are
mentioned in Section
A.11
.
Algorithms to compute the HNF of a matrix are given in Section 2.4.2 of Cohen [
127
],
Hafner and McCurley [
247
], Section 3.3.3 of Joux [
283
], Algorithm 16.26 of von zur
