Cryptography Reference
In-Depth Information
Input
:
a
and
b
, two integers of at most
bits
Output
:
d
,
u
,v
such that
d
=
au
+
b
v
=
gcd(
a
,
b
)
Complexity
:
O
(
2
)
x
←
(
a
,
1
,
0),
y
←
(
b
,
0
,
1)
1:
2:
while
y
1
>
0
do
make an Euclidean division
x
1
=
qy
1
+
r
3:
do
x
←
x
−
q
y
and exchange
x
and
y
4:
5:
end while
6:
(
d
,
u
,v
)
←
x
Figure 6.4.
Extended euclid algorithm.
thus lesser than
. Thus
y
1
eventually reaches zero and the program halts. Finally, we
notice that the gcd of
x
1
and
y
1
remains unchanged throughout the computation since
|
y
1
|
gcd(
x
1
,
y
1
)
=
gcd(
y
1
,
x
1
−
qy
1
)
.
When the computation starts, the gcd of
x
1
and
y
1
is the gcd of
a
and
b
. When the
computation ends, the gcd of
x
1
and
y
2
is the gcd of
d
and 0 which is
d
. Therefore
the computation eventually halts with
d
=
gcd (
a
,
b
)
=
au
+
b
v
. Finally, we prove that
2
) (the
complexity of the Euclidean division). We thus have to prove that the maximal number
of iterations is
3
). For this we notice that every loop is of complexity
the complexity is
O
(
O
(
O
). For this, let us consider the sequence (
z
0
,
z
1
,...,
(
z
i
) of all values
taken by
y
1
. We know that it is a decreasing sequence such that
z
0
<
2
,
z
i
=
0, and
z
j
+
1
=
z
j
−
1
−
q
j
z
j
with
z
j
−
1
z
j
q
j
=
.
Note that
q
j
can never be zero, but for the first iteration, thus we have
z
j
+
1
+
z
j
≤
z
j
−
1
for
j
=
1
,
2
,...,
i
−
1. Let us define
t
i
=
z
i
=
0,
t
i
−
1
=
z
i
−
1
=
d
, and
t
j
−
1
=
t
j
+
1
+
2
. This
t
j
for
j
=
i
−
1
,
i
−
2
,...,
1. We have
z
j
≥
t
j
for
j
=
0
,
1
,...,
i
, thus
t
0
≤
t
j
sequence is a Fibonacci sequence which resolves into
⎛
i
−
j
⎞
⎠
.
1
i
−
j
1
+
√
5
2
−
√
5
2
d
√
5
⎝
t
j
=
−
Hence
⎛
i
⎞
⎠
1
i
1
+
√
5
2
−
√
5
2
1
√
5
⎝
2
≥
t
0
≥
−
which ends up with
i
=
O
(
).
Search WWH ::
Custom Search