Function RecursiveMultiply

src/cryptlib/integer.cpp:451–512

// B[N] --- multiplicant

void RecursiveMultiply(word *R, word *T, const word *A, const word *B, unsigned int N)
{
    assert(N>=2 && N%2==0);

    if (N==2)
        AtomicMultiply(R, A[0], A[1], B[0], B[1]);
    else if (N==4)
        CombaMultiply(R, A, B);
    else
    {
        const unsigned int N2 = N/2;
        int carry;

        int aComp = Compare(A0, A1, N2);
        int bComp = Compare(B0, B1, N2);

        switch (2*aComp + aComp + bComp)
        {
        case -4:
            Subtract(R0, A1, A0, N2);
            Subtract(R1, B0, B1, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            Subtract(T1, T1, R0, N2);
            carry = -1;
            break;
        case -2:
            Subtract(R0, A1, A0, N2);
            Subtract(R1, B0, B1, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            carry = 0;
            break;
        case 2:
            Subtract(R0, A0, A1, N2);
            Subtract(R1, B1, B0, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            carry = 0;
            break;
        case 4:
            Subtract(R0, A1, A0, N2);
            Subtract(R1, B0, B1, N2);
            RecursiveMultiply(T0, T2, R0, R1, N2);
            Subtract(T1, T1, R1, N2);
            carry = -1;
            break;
        default:
            SetWords(T0, 0, N);
            carry = 0;
        }

        RecursiveMultiply(R0, T2, A0, B0, N2);
        RecursiveMultiply(R2, T2, A1, B1, N2);

        // now T[01] holds (A1-A0)*(B0-B1), R[01] holds A0*B0, R[23] holds A1*B1

        carry += Add(T0, T0, R0, N);
        carry += Add(T0, T0, R2, N);
        carry += Add(R1, R1, T0, N);