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

more time before exiting, if dividend is negative. Consider the earlier example
above of 17 % 7. The division operation proceeds as follows:

1. Left-shift (double) 7 until the result is greater than 17 (28)

2. Right- shift divisor once (14)

3. Subtract 14 from 17 (dividend 3)

4. Right-shift divisor again (7)

The division is complete because the divisor has shifted back to its initial posi-
tion. Now the dividend contains

3 — seven positions away from the desired
result of 4. Subtracting -divisor yields the correct answer, 4.
Unfortunately, in some contexts, specifi cally the extended Euclidean algorithm
developed here, the modulus of a negative and a positive must be negative. As a
result, you have to keep track of when and where you need the positive modulus
versus the negative modulus.
With signed-number support, you can now implement the extended Euclidean
algorithm for computing modular inverses for arbitrarily sized integers, as
shown in Listing 3-36.

Listing 3-36: “huge.c” inv routine

void inv( huge *z, huge *a )
{
huge i, j, y2, y1, y, quotient, remainder, a_temp;

set_huge( &i, 1 ); // initialize for copy
set_huge( &j, 1 ); // initialize for copy
set_huge( &remainder, 1 ); // initialize for copy
set_huge( &y, 1 );

set_huge( &a_temp, 1 );

set_huge( &y2, 0 );
set_huge( &y1, 1 );
copy_huge( &i, a );
copy_huge( &j, z );
if ( z->sign )
{
divide( &j, a, NULL );
// force positive remainder always
j.sign = 0;
subtract( &j, a );
}

while ( !( ( j.size == 1 ) && ( !j.rep[ 0 ] ) ) )
{
copy_huge( &remainder, &i );