Cryptography Reference
In-Depth Information
implies
i
=
1
log
2
q
i
=
(
(
))
O
len
a
. Replacing these equalities in the time estimate
(
(
)
(
))
above we obtain the estimate
O
len
b
len
a
.
From the Euclidean algorithm one easily obtains that gcd
(
a
,
b
)
is a linear com-
bination of
a
and
b
, namely:
Theorem 2.8
Let a
,
b
∈ Z
such that a
≥
b
>
0
. Then there exist s
,
t
∈ Z
such that
gcd
(
a
,
b
)
=
sa
+
tb.
,
keeping all the intermediate results of the divisions and then backtrack by substituting
each remainder in terms of the two previous ones until reaching
r
0
=
To prove this result it suffices to use the Euclidean algorithm to compute gcd
(
a
,
b
)
b
,
at which moment one has the required linear combination. A more efficient way to
carry out this computation is by using the following algorithm in which, following
Klappenecker, we use matrix notation:
a
and
r
1
=
Algorithm 2.3. Extended Euclidean algorithm
.
Input
:Integers
a
≥
b
>
0.
Output
:Integers
d
,
s
,
t
such that
d
=
gcd
(
a
,
b
)
=
sa
+
tb
.
⎛
⎝
⎞
⎠
:=
⎛
⎝
⎞
⎠
;
su
tv
dx
10
01
ab
while
x
=
0
d
x
q
:=
;
⎛
⎝
⎞
⎠
:=
⎛
⎝
⎞
⎠
01
1
;
su
tv
dx
su
tv
dx
−
q
end while
;
return
(
d
,
s
,
t
)
.
To see that the algorithm works as expected note that at the start of the loop we
have
d
=
a
and
x
=
b
and, after the first step the new values of
d
and
x
are
01
1
(
,
)
=
(
,
)
=
(
,
)
=
(
r
1
,
r
2
),
d
x
a
b
b
a
mod
b
−
q
a
where
q
and we have used our earlier notation for the remainders. After the
next step we similarly have
:=
b
(
d
,
x
)
=
(
r
2
,
r
3
)
and upon termination of the loop we
have that
.
Furthermore, at the start of the loop, the following equations hold:
as
(
d
,
x
)
=
(
r
n
,
0
)
=
(
gcd
(
a
,
b
),
0
)
, so that
d
=
gcd
(
a
,
b
)
+
bt
=
d
,
au
+
bv
=
x
. Subtracting the second equation
q
times from the first we obtain the
equation
a
qx
which, taking into account the assignments
to the variables
u
,
v
and
x
made in the while loop, means that after each iteration of
the loop we still have
au
(
s
−
qu
)
+
b
(
t
−
qv
)
=
d
−
+
bv
=
x
. After the assignments
s
:=
u
,
t
:=
v
,
d
:=
x
in
