Cryptography Reference
In-Depth Information
One can show that the complexity is
O
(
M
(
n
) log(
n
)) operations in
k
. For details see
Theorem 4 of [
549
], Section 10.1 of [
220
] or Corollary 4.5.4 of [
83
].
Exercise 2.16.2
Show that Theorem
2.16.1
also holds when the field
k
is replaced by a
ring.
2.17 Pseudorandom generation
Many of the above algorithms, and also many cryptographic systems, require generation of
random or pseudorandom numbers. The precise definitions for random and pseudorandom
are out of the scope of this topic, as is a full discussion of methods to extract almost perfect
randomness from the environment and methods to generate pseudorandom sequences from
a short random seed.
There are pseudorandom number generators related to RSA (the Blum-Blum-Shub
generator) and discrete logarithms. Readers interested to learn more about this topic should
consult Chapter 5 of [
376
], Chapter 3 of [
308
], Chapter 30 of [
16
], or [
359
].
2.18 Summary
Table
2.16
gives a brief summary of the complexities for the algorithms discussed in this
chapter. The notation used in the table is
n
∈ N
∈ Z
,
a,b
,
p
is a prime,
q
is a prime power
k
and
is a field. Recall that
M
(
m
) is the number of bit operations to multiply two
m
-bit
integers (which is also the number of operations in
k
to multiply two degree
m
polynomials
over a field
). Similarly,
M
(
d,q
) is the number of bit operations to multiply two degree
d
polynomials in
k
F
q
[
x
].
Table
2.16
gives the asymptotic complexity for the algorithms that are used in crypto-
graphic applications (i.e., for integers of, say, at most 10 000 bits). Many of the algorithms
are randomised and so the complexity in those cases is the expected complexity. The reader
is warned that the best possible asymptotic complexity may be different: sometimes it is
sufficient to replace
M
(
m
)by
m
log(
m
) log(log(
m
)) to get the best complexity, but in other
cases (such as constructing a polynomial basis for
F
q
m
) there are totally different meth-
ods that have better asymptotic complexity. In cryptographic applications,
M
(
m
) typically
behaves as
M
(
m
)
O
(
m
2
)or
M
(
m
)
O
(
m
1
.
585
).
=
=
The words “
k
-operations” includes additions, multiplications and inversions in
k
.If
inversions in
k
are not required in the algorithm then we say “
k
multiplications”.
