Cryptography Reference
In-Depth Information
Gathen and Gerhard [
220
], Section 5.3 of Schrijver [
478
], Kannan and Bachem [
297
],
Storjohann and Labahn [
533
] and Micciancio and Warinschi [
381
]. Naive algorithms to
compute the HNF suffer from coefficient explosion, so computing the HNF efficiently in
practice, and determining the complexity of the algorithm, is non-trivial. One solution is
to work modulo the determinant (or a subdeterminant) of the matrix
A
(see Section 2.4.2
of [
127
], [
247
]or[
533
] for further details). Let
A
=
(
A
i,j
)bean
n
×
m
matrix over
Z
and
define
. The complexity of the HNF algorithm of Storjohann and
Labahn on
A
(using naive integer and matrix multiplication) is
O
(
nm
4
log(
A
∞
=
max
i,j
{|
A
i,j
|}
∞
)
2
)bit
A
operations.
One can also use lattice reduction to compute the HNF of a matrix. For details see
page 74 of [
478
], Havas, Majewski and Matthews [
254
], or van der Kallen [
294
].
2.8 Modular exponentiation
Exponentiation modulo
n
can be performed in polynomial-time by the “square-and-
multiply” method. This method is presented in Algorithm
2
; it is called a “left-to-right”
algorithm as it processes the bits of the exponent
m
starting with the most significant bits.
Algorithm
2
can be applied in any group, in which case the complexity is
O
(log(
m
)) times
the complexity of the group operation. In this section we give some basic techniques to
speed-up the algorithm; further tricks are described in Chapter
11
.
Algorithm 2
Square-and-multiply algorithm for modular exponentiation
INPUT:
g,n,m
∈ N
OUTPUT:
b
≡
g
m
(mod
n
)
1:
i
1
2:
Write
m
in binary as (1
m
i
...m
1
m
0
)
2
3:
b
=
log
2
(
m
)
−
g
4:
while
(
i
=
≥
0)
do
b
2
b
=
(mod
n
)
5:
if
m
i
=
1
then
6:
b
=
bg
(mod
n
)
7:
end if
8:
i
=
i
−
1
9:
10:
end while
11:
return
b
Lemma 2.8.1
The complexity of Algorithm
2
using naive modular arithmetic is
O
(log(
m
) log(
n
)
2
)
bit operations.
Exercise 2.8.2
Prove Lemma
2.8.1
.
Lemma 2.8.3
If Montgomery multiplication (see Section
2.5
) is used then the complexity
of Algorithm
2.5
is O
(log(
n
)
2
+
log(
m
)
M
(log(
n
)))
.
