Cryptography Reference
In-Depth Information
Input
:
a
and
b
, two integers of at most
bits
Output
:
c
=
a
×
b
Complexity
:
O
(
2
)
1:
x
←
0
2:
y
←
a
3:
for
i
=
0to
−
1
do
if
b
i
=
1
then
4:
x
←
x
+
y
5:
end if
6:
y
←
y
+
y
7:
8:
end for
9:
c
←
x
Figure 6.2.
Multiplication from right to left.
Division is harder but generalizes as well.
Finally, Fig. 6.4 depicts a program performing the
Extended Euclid Algorithm
.
This enables us to compute the
greatest common divisor (gcd)
of
a
and
b
together with
an integral relationship (called
Bezout relationship
)
au
+
b
v
=
gcd (
a
,
b
)
.
The
program
manipulates
three-dimensional
vectors
x
=
(
x
1
,
x
2
,
x
3
)
and
y
=
(
y
1
,
y
3
). We can prove by induction that the above algorithm works. We first have
to notice that we have
y
2
,
x
1
=
ax
2
+
bx
3
and
y
1
=
ay
2
+
by
3
at any time. Thus, if the program halts, we have
d
y
1
|
decreases at every step 4, since the new
y
1
is the remainder of the division of
x
1
by
y
1
,
=
au
+
b
v
. Then, we notice that
|
Input
:
a
and
b
, two integers of at most
bits
=
×
Output
:
c
a
b
Complexity
:
O
(
2
)
1:
x
←
0
2:
for
i
=
−
1 downto 0
do
x
←
x
+
x
3:
if
b
i
=
1
then
4:
x
←
x
+
a
5:
6:
end if
7:
end for
8:
c
←
x
Figure 6.3.
Multiplication from left to right.
Search WWH ::
Custom Search