Cryptography Reference
In-Depth Information
quotient->size = ( bit_size / 8 ) + 1;
quotient->rep = ( unsigned char * ) malloc( quotient->size );
memset( quotient->rep, 0, quotient->size );
}
...
9. Because you're keeping track of your own negative numbers, you don't
want subtract doing it for you:
if ( compare( divisor, dividend ) <= 0 )
{
subtract_magnitude( dividend, divisor ); // dividend -= divisor
10. Finally, you need to account for negative modulus operations. As it turns
out, although negative number modulus operations come up in computa-
tions, they're not that well defi ned. Consider, for example, 17 % 7. This
is equal to 3 because 7
2
14 and 17
14
3. Now, you might be
tempted to say that
17 % 7
3 because
17 / 7
round(
2.42 )
3.
Although that's a perfectly valid defi nition of the modulus operation, it's not
the one that's been standardized on (at least not for cryptographic computa-
tions — it
is
the standard that the C programming language follows!). Instead,
2, 7
2
14, and
17
(
14)
17 % 7
4. Why? 7
3
21, and
17
(
21)
4.
Supporting Negative Remainders
If you view this on a number line, this starts to make (some) sense, as shown
in Figure 3-8.
−
3 * 7
−
21
−
2 * 7
−
14
−
1 * 7
−
7
0 * 7
0
1 * 7
7
2 * 7
14
3 * 7
21
4 * 7
28
−
17 % 7 = 4
17 % 7 = 3
Figure 3-8:
Positive remainder operations
To fi gure the remainder, fi nd the fi rst multiple, on the number line, to the
left
of your target and then fi gure the distance between the two points. This means,
fi rst of all, that modulus operations always return positive values and second that
(
x % y) !
(x % y)
(as convenient as that would have been when coding it). This also means that
you can't rely on the dividend being updated to be the modulus when one of the
parameters is negative. However, there's a simple solution: subtract divisor one
Search WWH ::
Custom Search