Cryptography Reference
In-Depth Information
The integers
s
i
and
t
i
arising from the extended Euclidean algorithm are equal, up to
sign, to the convergents of the continued fraction expansion of
a/b
. To be precise, if the
convergents of
a/b
are denoted
h
i
/k
i
for
i
1)
i
−
1
k
i
−
1
and
=
0
,
1
,...
then, for
i
≥
1,
s
i
=
(
−
1)
i
h
i
−
1
. Therefore, the values (
s
i
,t
i
) satisfy various equations, summarised below,
that will be used later in the topic. We refer to Chapter 10 of [
250
] or Chapter 7 of [
420
]
for details on continued fractions.
t
i
=
(
−
Lemma 2.3.3
Let a,b
∈ N
and let r
i
,s
i
,t
i
∈ Z
be the triples generated by running Algo-
rithm
1
in the case of positive remainders
0
≤
r
i
<r
i
−
1
.
1. For i
≥
1
,
|
s
i
|
<
|
s
i
+
1
|
and
|
t
i
|
<
|
t
i
+
1
|
.
2. If a,b>
0
then t
i
>
0
when i
≥
1
is even and t
i
<
0
when i is odd (and vice versa for
s
i
).
3. t
i
+
1
s
i
−
1)
i
+
1
.
t
i
s
i
+
1
=
(
−
1)
i
b and r
i
t
i
−
1
−
1)
i
−
1
a. In other words, r
i
|
4. r
i
s
i
−
1
−
r
i
−
1
s
i
=
(
−
r
i
−
1
t
i
=
(
−
s
i
−
1
|+
r
i
−
1
|
s
i
|=
b and r
i
|
t
i
−
1
|+
r
i
−
1
|
t
i
|=
a.
5.
|
a/b
+
t
i
/s
i
|≤
1
/
|
s
i
s
i
+
1
|
.
6.
|
r
i
s
i
|
<
|
r
i
s
i
+
1
|≤|
b
|
and
|
r
i
t
i
|
<
|
r
i
t
i
+
1
|≤|
a
|
.
<
1
/
(2
s
2
)
then
(
s,t
)
is (up to sign) one of the pairs
(
s
i
,t
i
)
computed by Euclid's algorithm.
8. If r,s,t
7. If s,t
∈ Z
are such that
|
a/b
+
t/s
|
/
2
then
(
r,s,t
)
is (up to sign) one of the
triples
(
r
i
,s
i
,t
i
)
computed by Euclid's algorithm.
∈ Z
satisfy r
=
as
+
bt and
|
rs
|
<
|
b
|
1)
i
−
1
k
i
−
1
Proof
Statements
1,
2
and
3
are
proved
using
the
relation
s
i
=
(
−
and
1)
i
h
i
−
1
where
h
i
/k
i
are the continued fraction convergents to
a/b
. From Chap-
ter 10 of [
250
] and Chapter 7 of [
420
] one knows that
h
m
=
t
i
=
(
−
q
m
+
1
h
m
−
1
+
h
m
−
2
and
k
m
=
1 of Euclid's algo-
rithm. The first statement follows immediately and the third statement follows from the fact
that
h
m
k
m
−
1
−
q
m
+
1
k
m
−
1
+
k
m
−
2
where
q
m
+
1
is the quotient in iteration
m
+
1)
m
−
1
. The second statement follows since
a,b>
0 implies
h
m
−
1
k
m
=
(
−
h
i
,k
i
>
0.
Statement 4 can be proved by induction, using the fact that
r
i
+
1
s
i
−
r
i
s
i
+
1
=
(
r
i
−
1
−
q
i
r
i
)
s
i
−
r
i
−
1
s
i
). Statement 5 is the standard result (equa-
tion (10.7.7) of [
250
], Theorem 7.11 of [
420
]) that the convergents of
a/b
satisfy
|
r
i
(
s
i
−
1
−
q
i
s
i
)
=−
(
r
i
s
i
−
1
−
a/b
−
h
m
/k
m
|
<
1
/
|
k
m
k
m
+
1
|
. Statement 6 follows directly from statements 2 and 4.
1)
i
−
1
t
i
+
1)
i
t
i
and both terms on the right-hand side are
For example,
a
=
r
i
(
−
r
i
−
1
(
−
positive.
Statement 7 is also a standard result in diophantine approximation; see Theorem 184 of
[
250
] or Theorem 7.14 of [
420
].
Finally, to prove statement 8 suppose
r,s,t
∈ Z
=
+
|
|
are such that
r
as
bt
and
rs
<
|
|
b
/
2. Then
bs
2
<
1
/
(2
s
2
)
.
|
a/b
+
t/s
|=|
(
as
+
bt
)
/bs
|=|
r
|
/
|
bs
|=|
rs
|
/
|
|
The result follows from statement 7.
