Cryptography Reference
In-Depth Information
Z
p
= Z
p
−{
}
Observe now that, whenever
p
is a prime number,
0
and hence
φ(
)
=
−
p
p
1. This gives the following corollary of Euler's theorem:
Corollary 2.2
(Fermat's Little Theorem)
Let p be a prime number and a an integer
such that p does not divide a. Then a
p
−
1
≡
1
(
mod
p
).
Corollary 2.3
Let p be a prime and a, e, positive integers such that p does not
divide a. Then a
e
a
e
mod
(
p
−
1
)
(
≡
mod
p
).
Proof
We have that
e
=
(
p
−
1
)
q
+
e
mod
(
p
−
1
)
for some non-negative integer
q
.
Then, by Fermat's little theorem,
a
p
−
1
≡
1
(
mod
p
)
and we have:
a
e
a
(
p
−
1
)
q
a
e
mod
(
p
−
1
)
≡
a
e
mod
(
p
−
1
)
≡
(
mod
p
).
Exercise 2.19
Use the previous corollary to find the last decimal digit of 7
2574
.
(Hint: Compute 7
2574
mod 2 and 7
2574
mod 5 and use these values to compute
7
2574
mod 10.)
Remark 2.5
We see that Euler's theorem is really a particular case of Lagrange's
theorem for groups, obtained by applying the latter—or its Corollary 2.1—to the
group
Z
n
Z
p
, where
p
is
and similarly for Fermat's little theorem and the group
prime.
Example 2.13
InMaple, Euler's
φ
-function is given by the command
numtheory:
φ
-phi
. For example, the values of
on the first 20 positive integers are (
map
may
be used instead of ~ in Maple versions prior to v13):
> numtheory:-phi
∼
([$1 .. 20]);
[1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]
We show that the
φ
-function gives the number of generators in a finite cyclic
group:
Theorem 2.16
Let G be a finite cyclic group of order n and g
∈
G a generator.
Then the generators of G are the elements g
t
with t
∈{
1
,...,
n
−
1
}
such that
gcd
(
t
,
n
)
=
1
. In particular, G has
φ(
n
)
generators.
g
t
Proof
Since
G
. Among
these elements, the generators are those with order
n
which, by Proposition 2.5 are
the
g
t
=
g
and
|
G
|=
n
, we have that
G
={
|
0
≤
t
<
n
}
/
(
,
)
=
(
,
)
=
such that
n
gcd
n
t
n
, which in turn is equivalent to gcd
n
t
1. The
φ(
)
φ
number of generators is then equal to
n
by definition of
.
Exercise 2.20
Prove that, for each integer
n
≥
2, the additive group
Z
n
is cyclic
and its generators are the elements
g
∈ Z
n
such that gcd
(
g
,
n
)
=
1.
To derive a formula to compute
φ
we first observe that it is a
multiplicative
function
, namely:
