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

easier because the interim multiplications — the multiplication by the digits of
456 — are unnecessary. You either multiply by 1 or 0 at each step, so the answer
is either the fi rst number or just 0. Consider the multiplication of 12 (binary
1100) by 9 (1001):

1100
1001
1100
00000
000000
1100000

1101100

Here, the 12 is left-shifted 0 times and 3 times, because the bits at positions 0 and 3
of the multiplicand 1001 are set. The two resulting values — 1100 and 1100000 — are
added together to produce 2 6 108, the expected answer.

Now you've reduced what might have been an O(2 n ) operation to a simple
O( n ) operation, where n is the number of bits of the smaller of the two operators.
In practice, it really doesn't matter if you try to optimize and use the smaller
number to perform the multiplication, so this implementation just takes the
numbers as given.
In code, this algorithm is implemented as shown in Listing 3-9 and illustrated
in Figure 3-3.

2 5 2 3 2 2

Listing 3-9: “huge.c” multiply

/**
* Multiply h1 by h2, overwriting the value of h1.
*/
void multiply( huge *h1, huge *h2 )
{
unsigned char mask;
unsigned int i;
huge temp;

set_huge( &temp, 0 );
copy_huge( &temp, h1 );

set_huge( h1, 0 );

i = h2->size;
do
{