Function MontgomeryReduce

src/cryptlib/integer.cpp:739–748

// U[N] --- multiplicative inverse of M mod 2**(WORD_BITS*N)

void MontgomeryReduce(word *R, word *T, const word *X, const word *M, const word *U, unsigned int N)
{
    RecursiveMultiplyBottom(R, T, X, U, N);
    RecursiveMultiplyTop(T, T+N, X, R, M, N);
    if (Subtract(R, X+N, T, N))
    {
        word carry = Add(R, R, M, N);
        assert(carry);
    }
}

// R[N] --- result = X/(2**(WORD_BITS*N/2)) mod M
// T[2*N] - temporary work space