Function RecursiveInverseModPower2

src/cryptlib/integer.cpp:715–731

// A[N] ----- an odd number as input

void RecursiveInverseModPower2(word *R, word *T, const word *A, unsigned int N)
{
    if (N==2)
        AtomicInverseModPower2(R, A[0], A[1]);
    else
    {
        const unsigned int N2 = N/2;
        RecursiveInverseModPower2(R0, T0, A0, N2);
        T0[0] = 1;
        SetWords(T0+1, 0, N2-1);
        RecursiveMultiplyTop(R1, T1, T0, R0, A0, N2);
        RecursiveMultiplyBottom(T0, T1, R0, A1, N2);
        Add(T0, R1, T0, N2);
        TwosComplement(T0, N2);
        RecursiveMultiplyBottom(R1, T1, R0, T0, N2);
    }
}

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