david wong

Hey! I'm David, cofounder of zkSecurity and the author of the Real-World Cryptography book. I was previously a crypto architect at O(1) Labs (working on the Mina cryptocurrency), before that I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

Toom-Cook multiplication for dummies posted April 2014

We're learning a lot of algorithm in my algebre et calcul formel class. One of them is the Toom-Cook algorithm used for multiplication of large integers.

I found a super simple explanation of it on a forum, it helps:

Say, we want to multiply 23 times 35.
We write,
p(x) = 2x + 3,
q(x) = 3x + 5.
We are using our realization that any integer can be written as a polynomial.
Here, p(x), represents 23, and q(x), represents 35, when x equals 10.
We write,
p(x)q(x) = r(x).
That is, p(x) times q(x), equals r(x).
So,
(2x + 3)(3x + 5) = ax^2 + bx + c = r(x).
Now,
p(0)q(0) = r(0).
So,
(20 + 3)(30 + 5) = a0 + b0 + c.
Therefore,
c = 15.
Now,
p(1)q(1) = r(1).
Therefore, when we do the substitutions (for x and c),
a + b = 25.
Now,
p(-1)q(-1) = r(-1).
Therefore, when we do the substitutions (for x and c),
a - b = -13.
Now, we already know c, and we just need to find a and b.
We have two linear equations and two unknowns,
a + b = *25,
a - b = -13.
We just add the two equations and we get,
2a = 12.
Therefore,
a = 6.
Now, we can substitute 6 for a in,
a + b = 25,
and we get,
b = 19.
So,
r(x) = 6x^2 + 19x + 15.
Now, we substitute 10 for x in r(x), and we are done,
r(10) = 600 + 190 + 15 = 805.
Believe it or not!

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

Chris

Isn't a, b and c more simply found by multiplying out (2x + 3)(3x + 5)= 6x^2 + 19x + 15 = r(x)?

Mark

For a small number like this of course you can simply multiply the two polynomials. But for larger numbers it's more efficient to follow the above steps. (Nice article btw. More info can be found also on wikipedia with a bigger example: https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication)

Ben Macintosh

It wasnt working with 14 and 21

Jay

a(x) = x + 4;
b(x) = 2x + 1;

(x + 4)(2x + 1) = p(x^2) + qx + r = c(x)
a(0)b(0) = c(0)
(1*0 + 4)(2*0 + 1) = p*0 + q*0 + r
r = 4

putting x = 1,
(1*1 + 4)(2*1 + 1) = p*1 + q*1 + 4
p + q = 11......(i)

putting x = -1,
(1*(-1) + 4)(2*(-1) + 1) = p - q + 4
p - q = -7......(ii)

Solving (i) and (ii),
p = 2 and q = 9

c(x) = 2(x^2) + 9x + 4
c(10) = 2*100 + 9*10 + 4
therefore, 14*21 = 294

leave a comment...