Cryptography Reference
In-Depth Information
For completeness we need to realize that the “pedestrian” and “intellectual” ways
really define the same thing! This can be checked by the following properties
(
a
+
n
Z
)
+
(
b
+
n
Z
)
=
((
a
+
b
mod
n
)
+
n
Z
)
(
a
+
n
Z
)
×
(
b
+
n
Z
)
=
((
a
×
b
mod
n
)
+
n
Z
)
where
a
+
n
Z
is the residue class of
a
,(
a
+
n
Z
)
+
(
b
+
n
Z
) means the addition of
two residue classes in the “intellectual” sense, and
a
+
b
mod
n
is the “pedestrian”
addition.
6.2.3 Additions, Multiplications, Inversion
We can then realize that it is computationally easy to make simple operations on large
numbers. Let us first look at how additions can be carried out.
We assume that large numbers are represented as bitstrings. For instance, if
a
and
b
are
-bit numbers, we can represent them as
−
1
−
1
a
i
2
i
b
i
2
i
a
=
and
b
=
i
=
0
i
=
0
with
a
i
=
0or1and
b
i
=
=
,
,...,
−
1. Fig. 6.1 is an example of
an algorithm computing the addition of
a
and
b
. This program computes the addition
by managing carries from right to left. We can prove it by induction by showing that
when entering into loop
i
, the addition of the truncated parts of
a
and
b
is equal to the
truncated part of
c
plus
r
0or1for
i
0
1
2
i
.
and that
r
=
0 or 1, namely
i
−
1
i
−
1
i
−
1
a
j
2
j
b
j
2
j
c
j
2
j
r
2
i
+
=
+
.
j
=
0
j
=
0
j
=
0
Input
:
a
and
b
, two integers of at most
bits
Output
:
c
, an integer of at most
+
1 bits representing
a
+
b
Complexity
:
O
(
)
1:
r
←
0
2:
for
i
=
0to
−
1
do
d
←
a
i
+
b
i
+
r
3:
set
c
i
and
r
to bits such that
d
=
2
r
+
c
i
4:
5:
end for
6:
c
←
r
Figure 6.1.
Addition of big numbers.
Search WWH ::
Custom Search