Cryptography Reference
In-Depth Information
Now that we have seen addition, we shall present the algorithm for
subtraction of two numbers
a
and
b
with representations
a
=(
a
m
−
1
a
m
−
2
...a
0
)
B
≥ b
=(
b
n
−
1
b
n
−
2
...b
0
)
B
to base
B
.
Algorithm for the subtraction
a − b
1.
Set
i ←
0
and
c ←
1
.
2.
If
c
=1
, set
t ← B
+
a
i
− b
i
; otherwise, set
t ← B −
1+
a
i
− b
i
.
3.
Set
d
i
← t
mod
B
and
c ←t/B
.
4.
Set
i ← i
+1
;if
i ≤ n −
1
, go to step 2.
5.
If
c
=1
, set
t ← B
+
a
i
; otherwise, set
t ← B −
1+
a
i
.
6.
Set
d
i
← t
mod
B
and
c ←t/B
.
7.
Set
i ← i
+1
;if
i ≤ m −
1
, go to step 5.
8.
Output
d
=(
d
m
−
1
d
m
−
2
...d
0
)
B
.
The implementation of subtraction is identical to that of addition, with the
following exceptions:
•
The
ULONG
variable
carry
is used to “borrow” from the next-higher digit of
the minuend if a digit of the minuend is smaller than the corresponding
digit of the subtrahend.
•
Instead of an overflow one must be on the lookout for a possible underflow,
in which case the result of the subtraction would actually be negative;
however, since
CLINT
is an
unsigned
type, there will be a reduction
modulo
(
N
max
+1)
(see Chapter 5). The function returns the error code
E_CLINT_UFL
to indicate this situation.
•
Finally, any existing leading zeros are eliminated.
Thus we obtain the following function, which subtracts a
CLINT
number
b_l
from
a number
a_l
.
