Function RecursiveMultiply

libcryptopp/cryptopp/integer.cpp:2059–2095

// B[N] --- multiplicant

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

	if (N <= s_recursionLimit)
		s_pMul[N/4](R, A, B);
	else
	{
		const size_t N2 = N/2;

		size_t AN2 = Compare(A0, A1, N2) > 0 ?  0 : N2;
		Subtract(R0, A + AN2, A + (N2 ^ AN2), N2);

		size_t BN2 = Compare(B0, B1, N2) > 0 ?  0 : N2;
		Subtract(R1, B + BN2, B + (N2 ^ BN2), N2);

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

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

		int c2 = Add(R2, R2, R1, N2);
		int c3 = c2;
		c2 += Add(R1, R2, R0, N2);
		c3 += Add(R2, R2, R3, N2);

		if (AN2 == BN2)
			c3 -= Subtract(R1, R1, T0, N);
		else
			c3 += Add(R1, R1, T0, N);

		c3 += Increment(R2, N2, c2);
		assert (c3 >= 0 && c3 <= 2);
		Increment(R3, N2, c3);
	}
}

// R[2*N] - result = A*A
// T[2*N] - temporary work space