Cryptography Reference
In-Depth Information
4.1 Addition and Subtraction
This notion of “further counting” means, “to the integer
n
1
add the integer
n
2
,” and the integer
s
at which one arrives by this further counting is called
“the result of addition” or the “sum of
n
1
and
n
2
” and is represented by
n
1
+
n
2
.
—Leopold Kronecker,
On the Idea of Number
Since addition and subtraction are in principle the same operation with differing
signs, the underlying algorithms are equivalent, and we can deal with them
together in this section. We consider operands
a
and
b
with representations
m
−
1
a
i
B
i
,
a
:= (
a
m
−
1
a
m
−
2
...a
0
)
B
=
0
≤
a
i
<B,
i
=0
n
−
1
b
i
B
i
,
b
:= (
b
n
−
1
b
n
−
2
...b
0
)
B
=
0
≤ b
i
<B,
i
=0
where we assume
a ≥ b
. For addition this condition represents no restriction,
since it can always be achieved by interchanging the two summands. For
subtraction it means that the difference is positive or zero and therefore can be
represented as a
CLINT
object without reduction modulo
(
N
max
+1)
.
Addition consists essentially of the following steps.
Algorithm for the addition
a
+
b
1.
Set
i ←
0
and
c ←
0
.
2.
Set
t ← a
i
+
b
i
+
c
,
s
i
← t
mod
B
,and
c ←t/B
.
3.
Set
i ← i
+1
;if
i ≤ n −
1
, go to step 2.
4.
Set
t
←
a
i
+
c
,
s
i
←
t
mod
B
,and
c
←
t/B
.
5.
Set
i
←
i
+1
;if
i
≤
m
−
1
, go to step 4.
6.
Set
s
m
←
c
.
7.
Output
s
=(
s
m
s
m
−
1
...s
0
)
B
.
The digits of the summands, together with the carry, are added in step 2, with
the less-significant part stored as a digit of the sum, while the more-significant
part is carried to the next digit. If the most-significant digit of one of the
summands is reached, then in step 4 any remaining digits of the other summand
are added to any remaining carries one after the other. Until the last summand
digit is processed, the less-significant part is stored as a digit of the sum, and
the more-significant part is used as a carry to the next digit. Finally, if there is a
