Cryptography Reference
In-Depth Information
,
∈
(
+
)
=
(
)
+
(
)
1. For all
x
y
R
,
f
x
y
f
x
f
y
(i.e.,
f
is a group homomorphism
between the additive groups of
R
and
S
).
2. For all
x
,
y
∈
R
,
f
(
xy
)
=
f
(
x
)
f
(
y
)
.
3.
f
(
1
R
)
=
1
S
(where 1
R
and 1
S
denote the identity elements of
R
and
S
, respec-
tively).
If, moreover,
f
is bijective, then
f
is said to be an
isomorphism
.
A class of rings which is especially important is the following:
Definition 2.20
A
field
is a commutative ring with identity in which every nonzero
element is invertible.
Example 2.9
is a commutative ring which is not a field because the only invertible
elements are 1 and
Z
−
1
.
R
and
C
are both fields.
Exercise 2.13
Prove that a commutative ring
(
R
,
+
,
·
)
is a field if and only if
(
R
−
is a group (in this case
R
∗
=
{
0
}
,
·
)
R
−{
0
}
is called the multiplicative group of
R
).
Exercise 2.14
Consider the bitwise Xor operation defined on
N
as follows. Given
two non-negative integers
a
, compute their binary expansions and make
them of equal length by adding leading zeros if necessary to the expansion of the
smaller number. Then
a
,
b
∈ N
b
is the integer whose binary expansion is the bit string
of the same length which in each position has a 1 if the corresponding bits in the
expansions of
a
and
b
are different and a 0 if these bits are equal (i.e., the exclusive
OR of the corresponding bits of the two expansions is computed). Prove that
⊕
(
N
,
⊕
)
is an abelian group but show that
(
N
,
⊕
,
·
)
(where
·
is the multiplication of integers)
is not a ring.
2.5.2 Congruences and the Residue Class Ring
All the examples of groups, rings and fields mentioned so far (excluding the trivial
group
) are infinite but the examples of cryptographic interest are usually finite.
In order to introduce some of the more important ones we start with the definition of
congruence.
{
1
}
Definition 2.21
Let
a
,
b
∈ Z
and
n
∈ Z
,
n
≥
2. We say that
a is congruent to b
modulo n
, written
a
≡
b
(
mod
n
)
, whenever
n
|
a
−
b
.If
n
does not divide
a
−
b
thenwe
say that
a
is not congruent to
b
modulo
n
and we denote this fact by
a
≡
b
(
mod
n
)
.
The formula
a
≡
b
(
mod
n
)
is called a
congruence
and the integer
n
is the
modulus
of the congruence.
We will not make an exhaustive listing of the properties of congruences, many
of which can be found, for example, in [194]. But we recall that the congruence
relation modulo
n
(when viewed as a binary relation on
) is reflexive, symmetric
and transitive, and hence is an equivalence relation. Thus it defines a partition, namely,
Z
