Cryptography Reference
In-Depth Information
Then comes the subtraction of
qhat
b
from the part
u
:= (
a
i
a
i
−
1
...a
i
−
n
)
B
of
the dividend, which is replaced by the difference thus calculated. There are two
things to note:
·
•
The products
qhat
b
j
can have two digits. Both digits are saved for the time
being in the
ULONG
variable
carry
. The more-significant word of
carry
is dealt
with as a carry in the subtraction of the next-higher digit.
·
•
For the case that
qhat
is still too large by
1
and the difference
u −
qhat
· b
is
negative, as a precaution the value
u
:=
B
n
+1
+
u −
qhat
· b
is calculated
and the result considered modulo
B
n
+1
as the
B
complement
u
of
u
. After
the subtraction the highest digit
u
i
+1
of
u
is located in the most-significant
word of the
ULONG
variable
borrow
. Finally, that
qhat
is here too large by
1
is recognized in that
u
i
+1
=0
. In this case the result is corrected in the
following by the addition
u ← u
+
b
modulo
B
n
+1
.
borrow = BASE;
carry = 0;
for (bptr_l = LSDPTR_L (b_l), rptr_l = lsdptrr_l;
bptr_l <= msdptrb_l; bptr_l++, rptr_l++)
{
if (borrow >= BASE)
{
*rptr_l = (USHORT)(borrow = ((ULONG)*rptr_l + BASE -
(ULONG)(USHORT)(carry = (ULONG)*bptr_l *
qhat + (ULONG)(USHORT)(carry >> BITPERDGT))));
}
else
{
*rptr_l = (USHORT)(borrow = ((ULONG)*rptr_l + BASEMINONEL -
(ULONG)(USHORT)(carry = (ULONG)*bptr_l * qhat +
(ULONG)(USHORT)(carry >> BITPERDGT))));
}
}
if (borrow >= BASE) {
*rptr_l = (USHORT)(borrow = ((ULONG)*rptr_l + BASE -
(ULONG)(USHORT)(carry >> BITPERDGT)));
}
else
{
*rptr_l = (USHORT)(borrow = ((ULONG)*rptr_l + BASEMINONEL -
(ULONG)(USHORT)(carry >> BITPERDGT)));
}
