Cryptography Reference
In-Depth Information
Z
/n
Z
=
{
x
+
n
Z
|
x
∈
Z
}
has the following
n
elements:
0+
n
Z
1+
n
Z
2+
n
Z
...
n
−
1+
n
Z
Z
/n
Z
is the formal and standard notation for the quotient group of
Z
modulo
n
Z
. However, for presentation convenience, we use the shorthand notation
Z
n
in
place of
for the purpose of this topic.
As corollaries of Lagrange's Theorem, one can show that the order of the
quotient group
G/H
equals
Z
/n
Z
and that in a finite group the order of every
element divides the group order. Fermat's Little Theorem (see Theorem 3.7) and
Euler's Theorem (see Theorem 3.8) take advantage of the second fact and form the
mathematical basis for the widely deployed RSA public key cryptosystem.
There are two important algebraic structures that comprise two operations:
rings and fields. They are addressed next.
|
G
|
/
|
H
|
3.1.2.4
Rings
The simpler algebraic structure that comprises two operations is the ring. It is
formally introduced in Definition 3.16.
Definition 3.16 (Ring)
A
ring
is an algebraic structure
S,
∗
1
,
∗
2
withaset
S
and
two associative binary operations
∗
1
and
∗
2
that fulfill the following requirements:
1.
S,
∗
1
is a commutative group with identity element
e
1
;
2.
is a monoid with identity element
e
2
;
3.
The operation
S,
∗
2
∗
2
is distributive over the operation
∗
1
. This means that for all
a, b, c
∈
S
the following two distributive laws must hold:
a
∗
2
(
b
∗
1
c
)=
a
∗
2
b
)
∗
1
(
a
∗
2
c
)
(
b
∗
1
c
)
∗
2
a
=
b
∗
2
a
)
∗
1
(
c
∗
2
a
)
