Cryptography Reference
In-Depth Information
It is trivial for
i
=
0. Assuming that this holds for
i
, we can prove it for
i
+
1 by noticing
that
i
i
i
−
1
i
−
1
a
j
2
j
b
j
2
j
a
j
2
j
a
i
2
i
b
j
2
j
b
i
2
i
+
=
+
+
+
j
=
0
j
=
0
j
=
0
j
=
0
i
−
1
c
j
2
j
r
2
i
a
i
2
i
b
i
2
i
=
+
+
+
j
=
0
i
−
1
c
j
2
j
r
)2
i
=
+
(
a
i
+
b
i
+
.
j
=
0
The parenthesis
a
i
+
r
corresponds to the new
d
value. Since
a
i
,
b
i
, and
r
are not
greater than 1, the new
d
is at most 3. Thus, we can compute the Euclidean division of
d
by 2:
b
i
+
d
=
2
r
+
c
i
.
Thus, with the new
r
value, we have
i
i
i
−
1
a
j
2
j
b
j
2
j
c
j
2
j
c
i
2
i
r
2
i
+
1
+
=
+
+
j
=
0
j
=
0
j
=
0
and
r
=
0 or 1. This completes the induction. Then, the induction equation for
i
=
raises
−
1
c
j
2
j
c
2
a
+
b
=
+
j
=
0
which means
a
+
b
=
c
.
This program uses elementary operations (like the addition of bits). Its complexity
is
O
(
). We can thus compute
a
+
b
within a linear time in the sizes of
a
and
b
.
)
operations by comparing bits from left to right until we have a difference. Then, if
a
If
n
is a number of exactly
bits, we can compare
a
+
b
with
n
within
O
(
+
O
b
is greater than
n
, we can subtract
n
within
(
) operations. Therefore, if
a
and
b
are smaller than
n
, we can compute
a
+
b
mod
n
within
O
(
) operations.
We can generalize this method for the multiplication. We have indeed two possible
iterative algorithms for multiplying
a
by
b
. One looks at all bits of
b
iteratively from
the rightmost to the leftmost (see Fig. 6.2), the other does the same from the leftmost
to the rightmost (see Fig. 6.3). For multiplication in
Z
n
, we just have to replace the
regular additions by the addition in our group: the addition modulo
n
.
Search WWH ::
Custom Search