Cryptography Reference
In-Depth Information
i
r
i
−
2
=
q
i
−
1
·
r
i
−
1
+
r
i
r
i
= [
s
i
]
r
0
+[
t
i
]
r
1
2 973 = 3
·
301 + 70
70 = [1]
r
0
+[
−
3]
r
1
3 301 = 4
·
70 + 21
21 = 301
−
4
·
70
−
−
=
r
1
4(1
r
0
3
r
1
)
−
= [
4]
r
0
+[13]
r
1
4 70
= 3
·
21 + 7
7=70
−
3
·
21
= (1
r
0
−
3
r
1
)
−
3(
−
4
r
0
+ 13
r
1
)
= [13]
r
0
+[
−
42]
r
1
21
= 3
·
7 + 0
The algorithm computed the three parameters gcd(973
,
301)=7,
s
= 13 and
t
=
−
42. The correctness can be verified by:
gcd(973
,
301)=7 =[13]973 +[
−
42]301 = 12649
−
12642
.
You should carefully watch the algebraic steps taking place in the right column
of the example above. In particular, observe that the linear combination on the right-
hand side is always constructed with the help of the
previous
linear combinations.
We will now derive recursive formulae for computing
s
i
and
r
i
in every iteration.
Assume we are in iteration with index
i
. In the two previous iterations we computed
the values
r
i
−
2
=[
s
i
−
2
]
r
0
+[
t
i
−
2
]
r
1
(6.2)
r
i
−
1
=[
s
i
−
1
]
r
0
+[
t
i
−
1
]
r
1
(6.3)
In the current iteration
i
we first compute the quotient
q
i
−
1
and the new remainder
r
i
from
r
i
−
1
and
r
i
−
2
:
·
r
i
−
1
+
r
i
.
r
i
−
2
=
q
i
−
1
This equation can be rewritten as:
r
i
=
r
i
−
2
−
q
i
−
1
·
r
i
−
1
.
(6.4)
Recall that our goal is to represent the new remainder
r
i
as a linear combination of
r
0
and
r
1
as shown in Eq. (6.1). The core step for achieving this happens now: in
Eq. (6.4) we simply substitute
r
i
−
2
by Eq. (6.2) and
r
i
−
1
by Eq. (6.3):
r
i
=(
s
i
−
2
r
0
+
t
i
−
2
r
1
)
−
q
i
−
1
(
s
i
−
1
r
0
+
t
i
−
1
r
1
)
If we rearrange the terms we obtain the desired result:
r
i
=[
s
i
−
2
−
q
i
−
1
s
i
−
1
]
r
0
+[
t
i
−
2
−
q
i
−
1
t
i
−
1
]
r
1
(6.5)
r
i
=[
s
i
]
r
0
+[
t
i
]
r
1
Eq. (6.5) also gives us immediately the recursive formulae for computing
s
i
and
t
i
, namely
s
i
=
s
i
−
2
−
q
i
−
1
s
i
−
1
and
t
i
=
t
i
−
2
−
q
i
−
1
t
i
−
1
. These recursions are valid
