[attachment=8371]

Abstract
There are a number algorithms used for multiplication of large integers, Toom Cook
Multiplication Algorithm is one of them. What this algorithm does is that it divides
large numbers into smaller parts and perform operations on the parts. Multiplication
operations on smaller parts can be done using Toom Cook algorithm recursively.
General Toom Cook algorithm is also known as Toom-k algorithm where k represents
the number of parts into which large number is divided. Complexity of Toom-k
algorithm is (nlog(2k−1)/log(k)).

Chapter 1
Introduction
This seminar describes about Toom Cook Multiplication algorithm. Toom Cook Multiplication
algorithm is used for multiplying large integers. It was Andrei Toom who
first described this algorithm, later Stephen Cook improved the algorithm and thus
the name Toom Cook Algorithm. Toom Cook algorithm (Toom-k) divide numbers
to be multiplied into k smaller parts and does some operations on the parts. Toom
Cook algorithm can be used recursively for doing the operations on sub parts.
Toom-3 which is illustrated using examples in this report is a single instance of
Toom Cook algorithms where a number is divided into three parts. Using ordinary
multiplication(known as grade school multiplication) requires nine multiplication to
find product of two 3 digit numbers. Toom-3 reduces nine multiplications into three
and its complexity is (nlog(5)/log(3))=(n1.465).
Steps involved in Toom Cook algorithm are:
1. Splitting
2. Evaluation
3. Pointwise Multiplication
4. Interpolation
5. Recomposition
1.1 Organization Of the report
Here after each chapter in this report describes each step involved in the algorithm.
For illustration purposes, I used following two numbers throughout this report:
m = 12 3456 7890 1234 5678 9012 and
n = 9 8765 4321 9876 5432 1098

section 1.1 Seminar Report 2010
1. Chapter 2 is on Splitting.
2. Chapter 3 describes Evaluation step.
3. Chapter 4 is on Pointwise multiplication step.
4. Chapter 5 discusses Interpolation.
5. Chapter 6 explains Recomposition step.
6. Chapter 7 is on applications of the algorithm.
Dept. of CSE, GEC, Thrissur 2
Seminar Report 2010
Chapter 2
Splitting
First step in the algorithm is splitting. In splitting each number is split in to k sub
parts.
• First we have to select a base B=bi such that number of digits of both the
numbers are atmost k where i is given by following formula.
i=max{⌊⌈logbm⌉/k⌋, ⌊⌈logbn⌉/k⌋}
• Then use these digits as coefficients in degree k-1 polynomials p and q such that
p(B)=m and q(B)=n.
• Our aim is to find out a polynomial r such that r(x)=p(x)q(x). Then r(B)=m∗n
will be our result.
2.1 Toom-3 illustration
In Toom-3, k=3 and so we choose i=b6/3=108
• Now we seperate m and n into their base B digits.
m0=56789012 m1=78901234 m2=123456
n0=54321098 n1=43219876 n2=98765
Dept. of CSE, GEC, Thrissur 3
section 2.1 Seminar Report 2010
• Now using this digits in degree 2 polynomial
p(x) = m2x2 + m1x + m0 = 123456x2 + 78901234x + 56789012
q(x) = n2x2 + n1x + n0 = 98765x2 + 43219876x + 54321098
Dept. of CSE, GEC, Thrissur 4
Seminar Report 2010
Chapter 3
Evaluation
In this step, we evaluate the polynomials formed in earlier step at various points.
• We evaluate both polinomials at deg(p) + deg(q) + 1 = km+kn-1 points.
• Choosing small integers like 0, 1, -1 and -2 will make algorithm easy.
• Also infinity is choosen as a point.
Value of a polynomial at infinity is computed by evaluating
limit of polynomial/xdegreeofpolymomial as x goes to infinity.
As a result value of polynomial at infinity will be always the value of highest
degree coefficient.
3.1 Toom-3 illustration
For Toom-3 we use km + kn-1 = 5 points.
We take the points 0, 1, -1, -2, ∞.
p(0) = m0 + m1(0)+m2(0)2 = m0 = 56789012
p(1) = m0 + m1(1)+m2(1)2 = m0 + m1 + m2 = 135813702
Dept. of CSE, GEC, Thrissur 5
section 3.1 Seminar Report 2010
p(-1) = m0 + m1(-1)+m2(-1)2 = m0 - m1 + m2 = 21988766
p(-2) = m0 + m1(-2)+m2(-2)2 = m0 - 2m1 + 4m2 = 100519632
p(∞) = m2 = 123456
Similarly
q(0) = n0 = 54321098
q(1) = n0 + n1 + n2 = 97639739
q(-1) = n0 - n1 + n2 = 11199987
q(-2) = n0 - 2n1 + 4n2 = 31723594
q(∞) = n2 = 98765

Chapter 4
Pointwise Multiplication
In this step we multiply values of both polynomial at each point to get value of the
product polynomial at corresponding point, ie we multiply p(a) and q(a) to get r(a)
for all ’a’ in the set of selected points in previous step.
This step just involves multiplication of integers. It can be done by using Toom
Cook algorithm recursively.
4.1 Toom-3 illustration
r is the product polynomial.
r(0) = p(0)q(0) = 56789012 ∗ 54321098 = 3084841486175176
r(1) = p(1)q(1) = 135813702 ∗ 97639739 = 13260814415903778
r(-1) = p(-1)q(-1) = -21988766 ∗ 11199987 = -246273893346042
r(-2) = p(-2)q(-2) = -100519632 ∗ -31723594 = 3188843994597408
r(∞) = p(∞)q(∞) = 123456 ∗ 98765 = 12193131840

Chapter 5
Interpolation
This step is actually the reverse of evaluation step. Now we have values of product
polynomial at various points. So we can find out the coefficients of product polynomial
and that process is called interpolation.
5.1 Toom-3 illustration
We have to solve the following matrix equation:
26666664
r(0)
r(1)
r(−1)
r(−2)
r(∞)
37777775
=
26666664
00 01 02 03 04
10 11 12 13 14
(−1)0 (−1)1 (−1)2 (−1)3 (−1)4
(−2)0 (−2)1 (−2)2 (−2)3 (−2)4
0 0 0 0 1
37777775
26666664
r0
r1
r2
r3
r4
37777775
=
26666664
1 0 0 0 0
1 1 1 1 1
1 −1 1 −1 1
1 −2 4 −8 16
0 0 0 0 1
37777775
26666664
r0
r1
r2
r3
r4
37777775
where r0, r1, r2, r3, r4 are coefficients of product polynomial r.
Using Gaussian elimination method to solve above equation is too expensive. So
what we do is, when selecting points in evaluation step, we choose suitable points
such that the matrix is invertible.
Dept. of CSE, GEC, Thrissur 8
section 5.3 Seminar Report 2010
So coefficients of product polynomial can be computed as follows:
26666664
r0
r1
r2
r3
r4
37777775
=
26666664
1 0 0 0 0
1 1 1 1 1
1 −1 1 −1 1
1 −2 4 −8 16
0 0 0 0 1
37777775
−1
26666664
r(0)
r(1)
r(−1)
r(−2)
r(∞)
37777775
=
26666664
1 0 0 0 0
1/2 1/3 −1 1/6 −2
−1 1/2 1/2 0 −1
−1/2 1/6 1/2 −1/6 2
0 0 0 0 1
37777775
26666664
r(0)
r(1)
r(−1)
r(−2)
r(∞)
37777775
5.2 Marco Bodrato’s sequence for matrix product
Finding an efficient sequence of operations to compute matrix product is a difficult
design challenge. Marco Bodrato proposed a sequence for computing matrix product
in his paper Towards Optimal Toom Cook Matrices for Integer and Polynomial Multiplication
which is applied here for our example:
r0 ← r(0) = 3084841486175176
r4 ← r() = 12193131840
r3←(r(-2) - r(1))/3 = (3188843994597408 - 13260814415903778)/3= -3357323473768790
r1←(r(1) - r(-1))/2 = (13260814415903778- (-246273893346042))/2= 6753544154624910
r2 ← r(-1) - r(0) = -246273893346042 - 3084841486175176 = -3331115379521218
r3←(r2 - r3)/2 + 2r() = (-3331115379521218 - (-3357323473768790))/2+ 212193131840
= 13128433387466
r2 ← r2 + r1 - r() = -3331115379521218 + 6753544154624910 - 12193131840
= 3422416581971852
r1 ← r1 - r3 = 6753544154624910 - 13128433387466 = 6740415721237444
Dept. of CSE, GEC, Thrissur 9
section 5.3 Seminar Report 2010
5.3 Product polynomial
Now we computed all coefficients of product polynomial. Thus the product polynomial
is :
r(x) = 3084841486175176 + 6740415721237444x
+ 3422416581971852x2 + 13128433387466x3
+ 12193131840x4

Chapter 6
Recomposition
We got product polynomial in previous step. All that remains to do is that we have
to find out r(B). But in first step, we selected B as a power of b. So multiplication by
powers of B (during computation of r(B)) is nothing but shifts by a whole number of
digits in base b.
6.1 Final Answer
Here we shift numbers by 8 digits and find their sum to get final result.
3084 8414 8617 5176 +
6740 4157 2123 7444
3422 4165 8197 1852
13 1284 3338 7466
121 9313 1840
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
121 9326 3124 6761 1632 4937 6009 5208 5858 8617 5176
Dept. of CSE, GEC, Thrissur 11
Seminar Report 2010
Chapter 7
Conclusion
7.1 Applications of Toom Cook algorithm
Toom Cook Multiplication Algorithm is having a several applications in calculations
involving large integers. Typical application areas are:
• Big Num arithmatic
• Cryptography like PGP, SSL, IPSec for dealing with keys having large length.
• For calculation of mathematical constants like , e etc.
Seminar described each step in Toom Cook algorithm illustrating Toom-3 algorithm
which is a special instance of general Toom Cook algorithm.

References
[1] Marco Bodrato, Alberto Zanoni Towards Optimal Toom-Cook Matrices for Integer
and Polynomial Multiplication, Springer 2006
[2] Marco Bodrato Towards Optimal Toom-Cook Multiplication for Univariate 2. and
Multivariate Polynomials in Characteristic 2 and 0, WAIFI’07, Springer 2007.