Cryptography Reference
In-Depth Information
∈ Z
n
, which is denoted generically by
like the one for the opposite of an element
a
∈ Z
n
−
−
=
−
∈ Z
n
. Also, if
a
a
and is equal to
a
mod
n
n
a
is a unit of the ring
Z
n
, we will denote its inverse by
a
−
1
.
Z
n
are rings but, in some cases, they have an
additional structure which is useful in many cryptographic settings, namely, they are
fields. This happens whenever every nonzero element of the ring has a multiplicative
inverse. Thus it is easily seen that
We have just seen that all the
Z
n
is a field for
n
=
2
,
3 or 5 but it is not a field
when
n
=
4or
n
=
6. In the latter case we observe that, since
n
is not prime, it has
a decomposition
n
=
rs
where
r
,
s
>
1. Then we have that
r
,
s
∈ Z
n
and, in this
ring,
rs
0. This means that
r
and
s
are zero divisors and it is obvious that a zero
divisor cannot have a multiplicative inverse for, otherwise, multiplying both terms of
the equation
rs
=
0by
r
−
1
we would obtain
s
=
=
0, a contradiction. This shows that
n
being prime is a necessary condition for
Z
n
to be a field and, using the preceding
results, it is also easy to show that this condition is actually sufficient:
Z
n
is a field if and only if n is a prime number.
Theorem 2.10
Proof
We have already shown the necessity so, to complete the proof of the theorem,
we just have to show that if
n
is prime then every 0
=
a
∈ Z
n
has an inverse. By
Theorem 2.8 there are integers
r
,
s
such that 1
=
gcd
(
a
,
n
)
=
sa
+
tn
. Reducing
modulo
n
we obtain that 1
≡
sa
(
mod
n
)
≡
((
s
mod
n
)
·
a
)(
mod
n
)
which shows
that
s
mod
n
is the inverse of
a
in
Z
n
and completes the proof.
More generally we have the following theorem whose proof we leave as an exer-
cise:
Theorem 2.11
An element a
∈ Z
n
is a unit if and only if a and n are relatively
prime.
Example 2.10
Modular inverses can be easily computed inMaple. A straightforward
rendition of the above proof gives us the following function:
> modinv := proc(a::nonnegint, p::posint)
local d, u;
d:=igcdex(a, p, 'u') mod p;
if d<>1 then
error "%1 does not have an inverse modulo %2", a, p
end if;
u mod p;
end:
But Maple already has ways to compute these inverses directly, using built-in
functions. For example:
> modinv(3865,38984), modp(1/3865, 38984), 1/3865 mod 38984;
817, 817, 817
