A=(an,an-1,an-2................a0)2 and B=(bn,bn-1,.....................b0) be 2 n bit no
then A can be written as A=2^n/2Amsb+Alsb
Amsb is the n/2 most significant bit of A ie n/2 leftmost bit of the no.
Alsb is the n/2 least significant bit of A ie is n/2 rightmost bit of the no.
so A*B=(2^n/2Amsb + Alsb )( 2^n/2Bmsb + Blsb ) = 2^n*Amsb*Bmsb + 2^n/2(Amsb * Blsb + Alsb *Bmsb) + Alsb Blsb
this equation says that mul of 2 n bit no can be carried out using mul of 4 n/2 digit no +some shift operatin
so the required corresponding recurrence if T(n)= time complexity to mul 2 n bit no
T(n) = 4*T(n/2) +Cn
but it can also be solved in T(n)= 3*T(n/2) +cn
for more optimiation ---https://en.wikipedia.org/wiki/Karatsuba_algorithm