Cryptography Reference
In-Depth Information
Algorithm 1
Extended Euclidean algorithm
INPUT:
a,b
∈ Z
OUTPUT:
d
=
gcd(
a,b
) and
s,t
∈ Z
such that
d
=
sa
+
tb
1:
r
−
1
=
a, s
−
1
=
1
,t
−
1
=
0
2:
r
0
=
b, s
0
=
0
,t
0
=
1
3:
i
0
4:
while
(
r
i
=
=
0)
do
i
=
i
+
1
5:
find
q
i
,r
i
∈ Z
such that
−|
r
i
−
1
|
/
2
<r
i
≤|
r
i
−
1
|
/
2 and
r
i
−
2
=
q
i
r
i
−
1
+
r
i
6:
s
i
=
s
i
−
2
−
q
i
s
i
−
1
7:
t
i
=
t
i
−
2
−
q
i
t
i
−
1
8:
9:
end while
10:
return
r
i
−
1
,s
i
−
1
,t
i
−
1
By Lemma
2.2.2
this requires
≤
c
log(
r
i
−
1
)(log(
r
i
−
2
)
−
log(
r
i
−
1
)
+
1) bit operations for
some constant
c
∈ R
>
0
. Hence, the total running time is at most
c
i
≥
1
log(
r
i
−
1
)(log(
r
i
−
2
)
−
log(
r
i
−
1
)
+
1)
.
Rearranging terms gives
c
i
≥
1
c
log(
r
−
1
) log(
r
0
)
+
log(
r
i
−
1
)(1
+
log(
r
i
)
−
log(
r
i
−
1
))
.
Now, 2
|
r
i
|≤|
r
i
−
1
|
so 1
+
log(
r
i
)
≤
log(
r
i
−
1
); hence, all the terms in the above sum are
≤
0. It follows that the algorithm performs
O
(log(
a
)log(
b
)) bit operations.
Exercise 2.3.2
Show that the complexity of Algorithm
1
is still
O
(log(
a
)log(
b
)) bit oper-
ations even when the remainders in line 6 are chosen in the range 0
≤
r
i
<r
i
−
1
.
A more convenient method for fast computer implementation is the binary Euclidean
algorithm (originally due to Stein). This uses bit operations such as division by 2 rather
than taking general quotients; see Section 4.5.2 of [
308
], Section 4.7 of [
21
], Chapter 3
of [
220
], Section 9.4.1 of [
150
] or Section 14.4.3 of [
376
].
There are subquadratic versions of Euclid's algorithm. One can compute the extended
gcd of two
n
-bit integers in
O
(
M
(
n
) log(
n
)) bit operations. We refer to Section 9.4 of [
150
],
[
524
] or Section 11.1 of [
220
].
The rest of the section gives some results about diophantine approximation that are used
later (e.g., in the Wiener attack on RSA, see Section
24.5.1
). We assume that
a,b>
0
and that the extended Euclidean algorithm with positive remainders is used to generate the
sequence of values (
r
i
,s
i
,t
i
).
