Cryptography Reference
In-Depth Information
here the issue of having no common factors (that is, being relatively prime) is of
great significance: If we consider the subset
Z
n
:=
{ a ∈
Z
n
|
gcd(
a, n
)=1
}
of those elements
a
n
for which
a
has no common factor with
n
other than
1, then with the operation of multiplication one has an abelian group, which we
∈
Z
have denoted by
Z
n
,
·
already in Chapter 5. The properties of
(
Z
n
,
·
)
as an
abelian semigroup with unit,
•
associativity of
(
Z
n
, ·
)
,
•
commutativity of
(
Z
n
, ·
)
,
¯
1=
a
,
•
existence of a unit: For all
a ∈
Z
n
one has
a ·
carry over directly to
Z
n
,
·
. The existence of multiplicative inverses holds
because we have selected precisely those elements that have such inverses, so
that we have now only to demonstrate
closure
, namely, that for two elements
a
and
b
in
b
is again an element of
Z
n
. Closure is easily proved:
If
a
and
b
are relatively prime to
n
, then the product of
a
and
b
cannot have a
nontrivial factor in common with
n
,sothat
a ·
Z
n
the product
a ·
b
must belong to the set
Z
n
.The
group
Z
n
, ·
is called the
group of residue classes relatively prime to
n
.
The number of elements in
Z
n
, or, equivalently, the number of integers
relatively prime to
n
in the set
{
1
,
2
,...,n−
1
}
, is given by the Euler phi
function
φ
(
n
)
.For
n
=
p
e
1
p
e
2
p
e
t
t
written as a product of distinct primes
p
1
,...,p
t
to positive powers
e
i
,wehave
···
t
p
e
i
−
1
φ
(
n
)=
(
p
i
−
1)
i
i
=1
Z
p
(see, for example, [Nive], Sections 2.1 and 2.4). This means, for example, that
1
elements if
p
is a prime number.
1
If
gcd(
a, n
)=1
, then according to Euler's generalization of the little
theorem of Fermat,
2
a
φ
(
n
)
has
p
−
1mod
n
, so that the calculation of
a
φ
(
n
)
−
1
mod
n
determines the multiplicative inverse of
a
. For example, if
n
=
p · q
with
prime numbers
p
≡
=
q
and
a ∈
Z
n
, then
a
(
p
−
1)(
q
−
1)
≡
1mod
n
,and
therefore
a
(
p
−
1)(
q
−
1)
−
1
mod
n
is the inverse of
a
modulo
n
. However, this
calculation requires, even in the advantageous case that
φ
(
n
)
is known, a
modular exponentiation whose computational cost is
O
log
3
n
.
We do significantly better, namely with a computational cost of
O
log
2
n
and without knowing the value of the Euler phi function, by integrating the
Z
p
,
+)
and
Z
p
,
·
=(
1
)
are abelian
groups (see [Nive], Section 2.11). Finite fields have application, for example, to coding theory,
and they play an important role in modern cryptography.
Z
p
is in fact a
field
, since both
(
Z
p
\{
0
}
,
·
In this case
2
The little Fermat theorem states that for a prime number
p
and for any integer
a
one has
a
p
a
mod
p
.If
p
is not a divisor of
a
, then
a
p
−
1
1mod
p
(see [Bund], Chapter 2, §3.3).
The little theorem of Fermat and its generalization by Euler are among the most important
theorems of number theory.
≡
≡
