Secure Key Exchange over an Insecure Medium with Public Key Cryptography - Implementing SSL/TLS Using Cryptography and PKI - page 108

the discussion of the importance of modular arithmetic to the RSA cryptosys-
tem? As it turns out, you almost never call divide for the quotient. Instead, you
are interested in the remainder (or modulus ). The complete division routine is
implemented in Listing 3-13.
Listing 3-13: “huge.c” divide
/**
* dividend = numerator, divisor = denominator
*
* Note that this process destroys divisor (and, of course,
* overwrites quotient). The dividend is the remainder of the
* division (if that's important to the caller). The divisor will
* be modified by this routine, but it will end up back where it
* “started”.
*/
void divide( huge *dividend, huge *divisor, huge *quotient )
{
int bit_size, bit_position;
// “bit_position” keeps track of which bit, of the quotient,
// is being set or cleared on the current operation.
bit_size = bit_position = 0;
// First, left-shift divisor until it's >= than the dividend
while ( compare( divisor, dividend ) < 0 )
{
left_shift( divisor );
bit_size++;
}
// overestimates a bit in some cases
quotient->size = ( bit_size / 8 ) + 1;
quotient->rep = ( unsigned char * )
calloc(quotient->size, sizeof( unsigned char ) );
memset( quotient->rep, 0, quotient->size );
bit_position = 8 - ( bit_size % 8 ) - 1;
do
{
if ( compare( divisor, dividend ) <= 0 )
{
subtract( dividend, divisor ); // dividend -= divisor
quotient->rep[ ( int ) ( bit_position / 8 ) ] |=
( 0x80 >> ( bit_position % 8 ) );
}
if ( bit_size )
{