Cryptography Reference
In-Depth Information
Appendix A
Background mathematics
For convenience, we summarise some notation, conventions, definitions and results that
will be used in the topic. This chapter is for reference only.
A.1 Basic notation
We write
R
for the real numbers and define
R
≥
0
={
x
∈ R
:
x
≥
0
}
and similarly for
R
>
0
.
We write
Z
for the integers and
N = Z
>
0
={
n
∈ Z
:
n>
0
}={
1
,
2
,
3
,...
}
for the natural
numbers.
We write #
S
for the number of elements of a finite set
S
.If
S,T
are sets we write
S
−
T
{
∈
∈
}
∅
for the set difference
s
S
:
s
T
. We denote the empty set by
.
Z
Z
Z
n
). When
n
is
We write
/n
for the ring of integers modulo
n
(many authors write
a prime and we are using the field structure of
Z
/n
Z
we prefer to write
F
n
. The statement
a
≡
b
(mod
n
) means that
n
|
(
a
−
b
). We follow a common mis-use of this notation by
writing
b
(mod
n
) for the integer
a
∈{
0
,
1
,...,n
−
1
}
such that
a
≡
b
(mod
n
). Hence,
the statement
a
b
(mod
n
) is an assignment of
a
to the value of the operator
b
(mod
n
)
and should not be confused with the predicate
a
=
≡
b
(mod
n
).
Y
means a function on some subset of
X
. In other words, a
map is not necessarily defined everywhere. Usually the word
function
implicitly means
“defined everywhere on
X
”, though this usage does not apply in algebraic geometry where
a rational function is actually a rational map. If
f
:
X
The word
map
f
:
X
→
→
Y
is a map and
U
⊂
X
then we
write
f
|
U
for the restriction of
f
to
U
, which is a map
f
|
U
:
U
→
Y
.
(
x
P
,y
P
) is a point and
f
is a function on points then we write
f
(
x
P
,y
P
)
rather than
f
((
x
P
,y
P
)) for
f
(
P
). We write
f
If
P
=
◦
g
for composition of functions (i.e., (
f
◦
g
)(
x
)
f
(
P
)
g
(
P
)).
The notation
f
n
usually means exponentiating the value of the function
f
to the power
n
, except when
f
is an endomorphism of an elliptic curve (or Abelian variety), in which
context it is standard to write
f
n
for
n
-fold composition. Hence, we prefer to write
f
(
P
)
n
than
f
n
(
P
) when denoting powering (and so we write log(
x
)
n
rather than log
n
(
x
)).
=
f
(
g
(
x
))); the notation
fg
will always mean product (i.e.,
fg
(
P
)
=
A.2 Groups
g
a
:
a
Let
G
be a group and
g
∈
G
.The
subgroup generated by
g
is
g
={
∈ Z}
.The
order
of the element
g
is the number of elements in the group
g
.The
exponent
of a finite
group is the smallest positive integer
n
such that
g
n
=
1 for all
g
∈
G
.
