Cryptography Reference
In-Depth Information
More about rings and finite fields which are related to rings is discussed in
Sect. 4.2. At this point, the following properties of rings are important:
We can add and multiply any two numbers and the result is always in the ring. A
ring is said to be
closed
.
Addition and multiplication are
associative
, e.g.,
a
+(
b
+
c
)=(
a
+
b
)+
c
, and
a
·
(
b
·
c
)=(
a
·
b
)
·
c
for all
a
,
b
,
c
∈
Z
m
.
There is the
neutral element 0 with respect to addition
, i.e., for every element
a
∈
Z
m
it holds that
a
+ 0
≡
a
mod
m
.
For any element
a
in the ring, there is always the negative element
−
a
such that
a
+(
−
a
)
≡
0mod
m
, i.e., the
additive inverse
always exists.
There is the
neutral element 1 with respect to multiplication
, i.e., for every ele-
ment
a
∈
Z
m
it holds that
a
×
1
≡
a
mod
m
.
The
multiplicative inverse
exists only for some, but not for all, elements. Let
a
,theinverse
a
−
1
∈
Z
is defined such that
a
−
1
a
·
≡
1mod
m
a
−
1
If an inverse exists for
a
, we can divide by this element since
b
/
a
≡
b
·
mod
m
.
It takes some effort to
find
the inverse (usually employing the Euclidean algo-
rithm, which is taught in Sect. 6.3). However, there is an easy way of telling
whether an inverse for a given element
aexists
or not:
An element
a
has a multiplicative inverse
a
−
1
if and only if gcd(
a
,
m
)=1,
where gcd is the
greatest common divisor
, i.e., the largest integer that divides
both numbers
a
and
m
. The fact that two numbers have a gcd of 1 is of great
importance in number theory, and there is a special name for it: if gcd(
a
,
m
)=1,
then
a
and
m
aresaidtobe
relatively prime
or coprime.
∈
Z
Example 1.10.
Let's see whether the multiplicative inverse of 15 exists in
Z
26
.
Because
gcd(15
,
26)=1
the inverse must exist. On the other hand, since
gcd(14
,
26)=2
= 1
Z
the multiplicative inverse of 14 does not exist in
26
.
∈
Z
m
,
i.e., the
distributive law
holds. In summary, roughly speaking, we can say that the
ring
Another ring property is that
a
×
(
b
+
c
)=(
a
×
b
)+(
a
×
c
) for all
a
,
b
,
c
Z
m
is the set of integers
{
0
,
1
,
2
,...,
m
−
1
}
in which we can add, subtract,
multiply, and sometimes divide.
As mentioned earlier, the ring
Z
m
, and thus integer arithmetic with the modulo
operation, is of central importance to modern public-key cryptography. In practice,
