Cryptography Reference
In-Depth Information
3.3.5
Euler's Theorem
Fermat's Little Theorem was generalized by Leonhard Euler to be applied in
any ring
Z
n
,
+
,
·
(with
n
being a composite). The fact that
Z
n
,
+
,
·
is a
ring implies that
Z
n
,
+
is a group with identity element 0, and that
Z
n
,
·
is
Z
n
=
a monoid with identity element 1. If we restrict the set of numbers to
{
a
∈
Z
n
|
gcd
(
a, n
)=1
}
(i.e., the set of elements of
Z
n
that have inverse
Z
n
,
elements), then
represents a multiplicative group and inverse elements ex-
ist for all of its elements. The order of the the group can be computed using
Euler's totient function introduced in Section 3.2.6 (i.e.,
·
|
Z
n
|
=
φ
(
n
)). For ex-
1)
2
−
1
|
Z
45
|
ample,
φ
(45) = 3
·
(3
−
·
(5
−
1) = 24, and this value equals
=
|{
1
,
2
,
4
,
7
,
8
,
11
,
13
,
14
,
16
,
17
,
19
,
22
,
23
,
26
,
28
,
29
,
31
,
32
,
34
,
37
,
38
,
41
,
43
,
44
}|
=24.
In essence, Euler's Theorem as stated in Theorem 3.8 says that any element
a
Z
n
is equivalent to 1 modulo
n
if it is multiplied
φ
(
n
) times.
in
Theorem 3.8 (Euler's Theorem)
If
gcd
(
a, n
)=1
,then
a
φ
(
n
)
≡
1(mod
n
)
.
Z
n
.Also,
Proof.
Because
gcd
(
a, n
)=1,
a
(m o d
n
) must be an element in
|
Z
n
|
=
φ
(
n
). According to a corollary of Lagrange's Theorem, the order of every
element (in a finite group) divides the order of the group. Consequently, the order
of
a
(i.e.,
ord
(
a
) as introduced in Section 3.1.2.3) divides
φ
(
n
), and hence if we
multiply
a
modulo
nφ
(
n
) times we always get a value that is equivalent to 1 modulo
n
.
1 if
n
is a prime, Euler's Theorem is indeed a general-
ization of Fermat's Little Theorem.
Because
φ
(
n
)=
n
−
3.3.6
Finite Fields Modulo Irreducible Polynomials
Finite fields modulo irreducible polynomials are frequently used in contemporary
cryptography. The notion of a polynomial is introduced in Definition 3.30.
Definition 3.30 (Polynomial)
Let
A
be an algebraic structure with addition and
multiplication (e.g., a ring or a field). A function
p
(
x
)
is a
polynomial
in
x
over
A
if
it is of the form
n
a
i
x
i
=
a
0
+
a
1
x
+
a
2
x
2
+
...
+
a
n
x
n
p
(
x
)=
i
=0
