Cryptography Reference
In-Depth Information
Proof
. See [167, Theorem 1.3.3, page 37].
✷
It is easily seen that any common divisor of
a,b
∈
Z
is also a common divisor
of an expression of the form
ax
+
by
for
x,y
. Such an expression is called
a
linear combination
of
a
and
b
. The greatest common divisor is a special kind
of linear combination, which can be computed using a more general form of
Theorem A.3, as follows.
∈
Z
Theorem A.4
(
The Extended Euclidean Algorithm)
Let
a,b
, and let
q
i
for
i
=1
,
2
,...,n
+1
be the quotients obtained from
the application of the Euclidean algorithm to find
g
= gcd(
a,b
)
, where
n
is the
least nonnegative integer such that
r
n
+1
=0
.If
s
−
1
=1
,
s
0
=0
, and
∈
N
s
i
=
s
i
−
2
−
q
n
−
i
+2
s
i
−
1
,
for
i
=1
,
2
,...,n
+1
, then
g
=
s
n
+1
a
+
s
n
b.
Proof
. See [167, Theorem 1.3.4, page 38].
✷
Corollary A.1
If
c
a
and
c
b
, then
c
(
ax
+
by
)
for any
x,y
∈
Z
.In
particular, the least positive value of
ax
+
by
is
g
.
We will also need the following notion (see Exercise 4.28 on page 575 in
Appendix G, for instance).
(
The Least Common Multiple
)
If
a,b
, then the smallest natural number, which is a multiple of both
a
and
b
, is the
least common multiple
of
a
and
b
, denoted by lcm(
a,b
).
∈
Z
The Sigma Notation
We can write
n
=1+1+
+ 1 for the sum of
n
copies of 1. We use the
Greek letter upper case
sigma
to denote
summation
. For instance,
i
=1
1=
n
would be a simpler way of stating the above. Also, instead of writing the sum
of the first one hundred natural numbers as 1 + 2 +
···
···
+ 100, we may write it
as
100
i
=1
i
. In general, if we have numbers
a
m
,a
m
+1
,
···
,a
n
(
m
≤
n
), we may
write their sum as
n
···
a
i
=
a
m
+
a
m
+1
+
a
n
,
i
=
m
and by convention,
n
a
i
=0if
m>n.
i
=
m
The letter
i
is the
index of summation
(and any letter may be used here),
n
is
the upper limit of summation
,
m
is
the lower limit of summation
, and
a
i
is a
summand
. In the previous example,
i
=1
1, there is no
i
in the summand since
Search WWH ::
Custom Search