Cryptography Reference
In-Depth Information
For the time being, we are interested in a number-theory theorem that is not
proved here. You presumably remember from school that a number (greater
than 1) is called a
prime number
if it is divisible only by 1 and itself without
remainder.
Fermat's little theorem
applies to prime numbers and states that
if
p
is a prime number and
a
cannot be divided by
p
, then
a
p
−
1
= 1 mod p
holds. Euler proved an important generalization of this theorem, which applies
also to non-prime modules:
A number,
m
,is
relatively prime
to
n
if there is no integer greater than 1,
by which both
m
and
n
are divisible. So, 12 and 7 are relatively prime, while
12 and 8 are not. The amount of all numbers from the set 1
,...,n
, which are
relatively prime to
n
, is called
Euler's function
of
n
, written as
φ(n)
. Fermat's
little theorem can now be generalized as follows:
a
φ(
n
)
= 1 mod n
holds for every natural number,
n
, and every
a
that is relatively prime to it.
When
n
is a prime, then
φ(n)
−
1 holds. We can see that it is actually a
generalization of Fermat's little theorem.
=
n
We can also use Euler's generalization to compute the modular reciprocal of a
number, i.e., we can determine
x
that meets
ax = 1 mod n
for given
a
and
n
. The solution is
x
=
a
φ(n)
−
1
.
This should do for a preparation.
Reaching the Goal With Ease
There is often no direct way to a solution in mathematics; instead, solutions are
found by apparently aimless experimenting. We'll take good heed of this, and
just see what we can do with Euler's generalization of Fermat's little theorem
