Algorithm to multiply 2 numbers with n bits using Strassen's algorithm

Question

Design and analyze an algorithm to multiply 2 numbers A and B, each n bits longs, but partitioning them into 3 equal sized pieces each and using the Strassen's algorithm. What is the best running time you can get?

I have two numbers that are n length and separated them into three equal parts. For example, 123 separates into 1, 2, and 3. From my understanding, I have to use matrices. However, Strassen's algorithm does not make any sense to me.

I have watched videos and read lectures but still have no clue on how to proceed. Any help would be appreciated, thank you!

Answer 1

Since this is homework, I'll give just a hint at first:

Dividing two n-bit numbers into three blocks means representing them as X = x_0 + x_1 b + x_2 b^2 and Y = y_0 + y_1 b + y_2 b^2 where b is a base, for example b = 2^(n/3). Compute their product XY. It will be a 4-degree polynomial in base b.

The coefficients of this polynomial can be computed with addition and subtraction from these 6 products:

x_0 y_0
x_1 y_1
x_2 y_2
(x_0 + x_1)(y_0 + y_1)
(x_0 + x_2)(y_0 + y_2)
(x_1 + x_2)(y_1 + y_2)

This way the work of computing the product of XY has been reduced from computing 9 products of n/3 bit numbers to only 6, making it faster than the O(n^2) method taught in school.