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

copy_huge( &i, &j );
divide( &remainder, &j, &quotient );
multiply( &quotient, &y1 ); // quotient = y1 * quotient
copy_huge( &y, &y2 );
subtract( &y, &quotient ); // y = y2 - ( y1 * quotient )
copy_huge( &j, &remainder );
copy_huge( &y2, &y1 );
copy_huge( &y1, &y );
}
copy_huge( z, &y2 );
copy_huge( &a_temp, a );
divide( z, &a_temp, NULL ); // inv_z = y2 % a
if ( z->sign )
{
z->sign = 0;
subtract( z, &a_temp );
if ( z->sign )
{
z->sign = 0;
}
}
}
Fundamentally, this works the same as the native int algorithm presented
in Listing 3-28; I've added the equivalent operations as comments so that you
can compare the two. The only difference is that I moved the assignment of
i to j up to the top because the subsequent divide overwrites j . This doesn't
affect functionality because i isn't used again in the body of the loop. The only
reason for coding it this way is to cut down on the number of temporary huge s
that need to be allocated and freed.
Finally, notice the last section where inv z is computed:
divide( inv_z, &a_temp, NULL ); // inv_z = y2 % a
if ( inv_z->sign )
{
inv_z->sign = 0;
subtract( inv_z, &a_temp );
}
The default divide operation returns the negative modulus. You need the
positive one (if it's negative), which you can recover by swapping the signs and
subtracting a one more time. The divide call inside the loop, however, must
preserve negative moduli or the routine doesn't work correctly.