Cryptography Reference
In-Depth Information
these rings can be done completely in hardware, without having to use multiprecision
arithmetic and, on the other, they can easily be parallelized.
Exercise 2.17
Write a Maple function that computes
n
!
for a large integer
n
(say
n
10000) by computing the result modulo a sufficient number of primes preced-
ing 2
31
(which may be estimated by means of Stirling's formula, see [94]). These
computations may be carried out with machine-size integers of type
integer[4]
and then the CRT may be used to compute the final result.
>
2.7 Euler's Theorem and Modular Exponentiation
2.7.1 Euler's Theorem
We have seen that the units of a commutative ring form an abelian group and, in
particular, the group of units of
Z
n
={
.
There is a result of Euler related to this group which, after being proved in the
first half of the eighteenth century, found an interesting cryptographic application
more than two centuries later for, as we shall see, it is crucial for the RSA encryption
scheme. In order to state and prove this result we need the following concept:
Z
n
is, by Theorem 2.11 ,
a
∈ Z
n
|
gcd
(
a
,
n
)
=
1
}
∈ Z
≥
φ
Definition 2.23
Let
n
,
n
2. The Euler
-function (also called totient function)
of
n
is defined by:
φ(
n
)
=|{
x
∈ Z|
1
≤
x
≤
n
and gcd
(
x
,
n
)
=
1
}|
.
Z
n
, i.e.
In other words,
φ(
n
)
is the order of
)
=|Z
n
|
.
φ(
n
Remark 2.4
Note that, although we do not consider congruences modulo 1, the
definition of Euler's
φ
-function extends naturally to all positive integers by setting
φ(
1
)
=
1.
Euler's theorem is then the following:
Theorem 2.15
(Euler's theorem)
Let a and n be positive integers such that n
≥
2
1
. Then a
φ(
n
)
≡
and
gcd
(
a
,
n
)
=
1
(
mod n
).
Proof
Observe that the statement of this theorem may be formulated in terms of
the group
Z
n
. Saying that gcd
(
a
,
n
)
=
1 is equivalent to saying that
a
mod
n
is an
Z
n
. The statement of the theorem is then equivalent to saying that, in the
element of
Z
n
we have
)
φ(
n
)
=
group
Exercise 2.18
Use Euler's theorem to compute the last (decimal) digit of 7
2010
.
(Hint: Apply Euler's theorem modulo 10.)
(
a
mod
n
1, and this follows from Corollary 2.1.
