Karatsuba method

1. The problem statement, all variables and given/known data

For polynomials f(x),g(x) of degree d = 2^(r−1)−1, check that multiplying f(x) and g(x) by the Karatsuba method requires 3^(r-1) multiplications in the field F.





2. Relevant equations

You can can more clearly see problem on page 383 #10:

http://igortitara.files.wordpress.co...r-algebra1.pdf





3. The attempt at a solution

I understand Karatsuba method is

(a₁r+a₀)(b₁r+b₀) = a₁b₁r² +(a₁b₀+a₀b₁)r+a₀b₀

= a₁b₁r² +(a₁b₁r+a₀b₀r−(a₁−a₀)(b₁−b₀)r)+a₀b₀

= (a₀b₀r+a₀b₀)+(a₁b₁r²+a₁b₁r)−(a₁−a₁)(b₁−b₀)r

but I do not understand how to implement this with only the degree given in the problem.