Cryptography Reference
In-Depth Information
This means that we can compute 2
p
and—more interestingly—
p
if we know
φ
(
n
). Assuming the difficulty of factorization, we can assume that computing
φ
(
n
)
for any
n
with unknown factorization is also difficult (otherwise we could construct
an efficient factorization algorithm by first computing
φ
(
n
)). This property is used,
for example, in the RSA public key cryptosystem.
3.3
MODULAR ARITHMETIC
Modular arithmetic elaborates on the ring
23
Z
n
,
+
,
·
that consists of a complete
residue system modulo
n
(denoted as
Z
n
) and the two operations + and
·
.Inthis
setting, + refers to the addition modulo
n
,and
refers to the multiplication modulo
n
. In this section, we look at the aspects of modular arithmetic that are relevant for
contemporary cryptography.
·
3.3.1
Modular Congruence
Two in teg er s ar e
congruent
modulo a given natural number if they represent the same
value when computed modulo this number. This is formally expressed in Definition
3.29.
Definition 3.29
Let
a, b
∈
Z
and
n
∈
N
.
a
is
congruent to
b
modulo
n
, denoted
a
≡
b
(mod
n
)
,if
n
divides
a
−
b
(i.e.,
n
|
a
−
b
).
For example, 7
≡
12 (mod 5), 4
≡−
1(mod5), 12
≡
0(mod2),and
−
2
≡
19 (mod 21).
It can be shown that congruence modulo
n
defines an
equivalence relation
over
Z
. This means that for all
n
∈
N
and
a, b, c
∈
Z
1.
a
≡
a
(mod
n
) (i.e., the relation is
reflexive
);
2. If
a
≡
b
(mod
n
),then
b
≡
a
(mod
n
) (i.e., the relation is
symmetric
);
3. If
a
≡
b
(mod
n
) and
b
≡
c
(mod
n
),then
a
≡
c
(mod
n
) (i.e., the relation
is
transitive
).
It is well known that an equivalence relation over a set (e.g.,
Z
) partitions
the set into
equivalence classes
. In the case of
Z
, the equivalence classes are
also referred to as
residue classes
.Every
a
∈
Z
is congruent modulo
n
to some
b
∈{
0
,...,n
−
1
}
, and hence
R
n
(
a
) defines a residue class that consists of all
x
∈
Z
that are congruent to
a
modulo
n
. This can be formally expressed as follows:
23
Note that
Z
n
,
+
, ·
is a field if
n
is a prime.
