Function HalfMontgomeryReduce

src/cryptlib/integer.cpp:757–803

// V[N] --- 2**(WORD_BITS*3*N/2) mod M

void HalfMontgomeryReduce(word *R, word *T, const word *X, const word *M, const word *U, const word *V, unsigned int N)
{
    assert(N%2==0 && N>=4);

#define M0      M
#define M1      (M+N2)
#define V0      V
#define V1      (V+N2)

#define X0      X
#define X1      (X+N2)
#define X2      (X+N)
#define X3      (X+N+N2)

    const unsigned int N2 = N/2;
    RecursiveMultiply(T0, T2, V0, X3, N2);
    int c2 = Add(T0, T0, X0, N);
    RecursiveMultiplyBottom(T3, T2, T0, U, N2);
    RecursiveMultiplyTop(T2, R, T0, T3, M0, N2);
    c2 -= Subtract(T2, T1, T2, N2);
    RecursiveMultiply(T0, R, T3, M1, N2);
    c2 -= Subtract(T0, T2, T0, N2);
    int c3 = -(int)Subtract(T1, X2, T1, N2);
    RecursiveMultiply(R0, T2, V1, X3, N2);
    c3 += Add(R, R, T, N);

    if (c2>0)
        c3 += Increment(R1, N2);
    else if (c2<0)
        c3 -= Decrement(R1, N2, -c2);

    assert(c3>=-1 && c3<=1);
    if (c3>0)
        Subtract(R, R, M, N);
    else if (c3<0)
        Add(R, R, M, N);

#undef M0
#undef M1
#undef V0
#undef V1

#undef X0
#undef X1
#undef X2
#undef X3
}

#undef A0
#undef A1