Cryptography Reference
In-Depth Information
Definition A.21
(
Modular Multiplicative Inverses)
Suppose that
a
.A
multiplicative inverse of the integer
a
modulo
n
is an integer
x
such that
ax
∈
Z
, and
n
∈
N
1 (mod
n
)
.If
x
is the least positive
such inverse, then we call it
the least multiplicative inverse of the integer
a
modulo
n
, denoted by
x
=
a
−
1
.
≡
Example A.5
Consider
n
= 26,
a
=
7, and suppose that we want to find the
least multiplicative inverse of
a
modulo
n
. Since
−
1 (mod 26) and no
smaller natural number than 11 satisfies this congruence, then
a
−
1
= 11 modulo
26.
−
7
·
11
≡
When
n
is prime
Z
/n
Z
takes on a new character (see page 483).
Theorem A.11
(
The Field
Z
/p
Z
)
If
n
∈
N
, then
Z
/n
Z
is a field if and only if
n
is prime.
Proof
. See page 599.
✷
We employ the notation
F
∗
to denote the multiplicative group of nonzero
elements of a given field
F
. In particular, when we have a finite field
Z
/p
Z
=
F
p
)
∗
denotes the multiplicative group
of
p
elements for a given prime
p
, then (
Z
/p
Z
)
∗
of nonzero elements of
F
p
.
This is tantamount to saying that (
Z
/p
Z
is the
)
∗
is cyclic. Thus, this notation and notion may
group of units in
F
p
, and (
Z
/p
Z
be generalized as follows.
Let
n
∈
N
and let the group of units of
Z
/n
Z
be
)
∗
(see page 483). Then
denoted by (
Z
/n
Z
)
∗
=
Z
Z
{
∈
Z
Z
≤
}
(
/n
a
/n
:0
a<n
and gcd(
a,n
)=1
.
(A.2)
Numerous times we will need to solve systems of congruences for which the
following result from antiquity is most useful.
Theorem A.12
(
Chinese Remainder Theorem
)
Let
n
i
∈
N
for natural numbers
i
≤
k
∈
N
be pairwise relatively prime, set
n
=
j
=1
n
j
and let
r
i
∈
Z
for
i
≤
k
. Then the system of
k
simultaneous linear
congruences given by
x
≡
r
1
(mod
n
1
)
,
x
≡
r
2
(mod
n
2
)
,
.
.
.
x
≡
r
k
(mod
n
k
)
,
has a unique solution modulo
n
.
Search WWH ::
Custom Search