Cryptography Reference
In-Depth Information
Both relations are well-defined, since in each case the result is a residue
class modulo
m
. The set
Z
m
:=
{ r
|
r
is a residue modulo
m }
of residue
classes modulo
m
together with these relations forms a
finite commutative ring
(
Z
m
,
+
, ·
)
with unit, which in particular means that the following axioms are
satisfied:
1.
Closure with respect to addition
:
The sum of two elements of
Z
Z
m
is again in
m
.
2.
Associativity
o
f addition
:
For every
a, b, c
in
Z
m
one has
a
+
b
+
c
=
a
+
b
+
c.
3.
Existence of an additive identit
y
:
For every
a
in
Z
m
one has
a
+ 0=
a
.
4.
Existence of an additive inverse
:
For
ea
ch
e
lement
a
in
Z
m
there exists a unique element
b
in
Z
m
such that
a
+
b
= 0
.
5.
Commutativ
i
ty of addition
:
For every
a, b
in
Z
m
one has
a
+
b
=
b
+
a
.
6.
Closure with respect to multiplication
:
The product of two elements of
Z
m
is again an element of
Z
m
.
7.
Associativ
it
y
o
f
m
ultiplication
:
For every
a, b
,
c
in
·
b
c
=
a
b
·
Z
m
one has
a
·
·
c
.
8.
Existence of a multiplicative identity
: For every
a
in
Z
m
one has
a ·
1=
a
.
9.
Commutativity of multiplication
: For each
a, b
in
Z
m
one has
a · b
=
b · a
.
10.
In
(
Z
m
,
+
, ·
)
the
distributive law
holds:
a ·
(
b
+
c
)=
a · b
+
a · c
.
m
,
+)
is an
abelian
group
, where the term
abelian
refers to the commutativity of addition. From
property 4 we can define subtraction in
On account of properties 1 through 5 we have that
(
Z
Z
m
a
s
usual,
n
amely,
a
s addition of the
inverse element: If
c
is the additive inverse of
b
,then
b
+
c
= 0
, and so for each
a ∈
Z
m
we may define
a − b
:=
a
+
c.
In
(
Z
m
, ·
)
the group
l
aws 6, 7, 8, and 9 hold for multiplication, where the
multiplicative identity is
1
.However,in
Z
m
it does not necessarily hold that each
element possesses a multiplicative inverse, and thus in general,
(
Z
m
, ·
)
is not a
group, but merely a commutative
semigroup
with unit.
3
However, if we remove
Z
m
all the elements that have a common divisor with
m
greater than
1
,we
from
3
A semigroup
(
H,
∗
)
exists merely by virtue of there existing on the set
H
an associative
relation
∗
.
