# Toom-Cook Multiplication

## 1. Generalizing Karatsuba: Toom-$$n$$

The Toom–Cook algorithm generalizes [Karatsuba](/intro/primitives/abstract-algebra/extension-field/multiplication/karatsuba-multiplication.md) (which is Toom-2, where $$n=2$$). For an input polynomial of degree $$k-1$$, Toom-$$n$$ splits it into $$n$$ **sub-polynomials** and reduces the number of necessary recursive multiplications from $$n^2$$ to $$2n-1$$.

### Complexity Comparison

For multiplying two polynomials of size $$k$$ (degree $$k-1$$), the time complexity is determined by the split count $$n$$:

$$
T(k) = O\left(k^{\log\_n (2n-1)}\right)
$$

| Algorithm Name         | Split Count(n) | Recursive Calls(2n -1) | Exponent                    | Complexity       |
| ---------------------- | -------------- | ---------------------- | --------------------------- | ---------------- |
| **Karatsuba (Toom-2)** | $$n=2$$        | 3                      | $$\log\_2 3 \approx 1.585$$ | $$O(k^{1.585})$$ |
| **Toom-3**             | $$n=3$$        | 5                      | $$\log\_3 5 \approx 1.465$$ | $$O(k^{1.465})$$ |
| **Toom-4**             | $$n=4$$        | 7                      | $$\log\_4 7 \approx 1.404$$ | $$O(k^{1.404})$$ |

## 2. Toom–Cook Process in $$\mathbb{F}\_{P^k}$$ (Toom-3 Example)

Let $$A(x)$$ and $$B(x)$$ be elements in $$\mathbb{F}\_{P^k}$$, represented as polynomials of degree approximately $$k-1$$. We aim to compute the polynomial product $$C'(x) = A(x) \cdot B(x)$$ efficiently.

### Step 1: Splitting (Divide)

Divide $$A(x)$$ and $$B(x)$$ into $$n=3$$ **sub-polynomials** ($$A\_2, A\_1, A\_0$$ and $$B\_2, B\_1, B\_0$$) of degree less than $$m \approx k/3$$:

$$
A(x) = A\_2(x) x^{2m} + A\_1(x) x^m + A\_0(x) \\
B(x) = B\_2(x) x^{2m} + B\_1(x) x^m + B\_0(x)
$$

### Step 2: Evaluation

$$
C'(x) = C\_4(x) x^{4m} + C\_3(x) x^{3m} + C\_2(x) x^{2m} + C\_1(x) x^m + C\_0(x)
$$

The resulting product $$C'(x)$$ has a maximum degree of $$4m$$, meaning it has $$2n-1 = 5$$ unknown coefficients(from $$C\_0$$ to $$C\_4$$)that must be solved for. Therefore, we need to evaluate $$A(x)$$ and $$B(x)$$ at 5 distinct, carefully chosen **evaluation points** $$e\_i \in \mathbb{F}\_P$$ (or a small extension of $$\mathbb{F}\_P$$).

Commonly chosen evaluation points are $${0, 1, -1, 2, \infty}$$ for $$n=3$$ (Similarly, for $$n=4$$, we'll evaluate on $${0, 1, -1, 2, -2, 3, \infty}$$).

* **Compute** $$v\_i$$ **and** $$w\_i$$**:**

  $$
  v\_i = A(e\_i) \quad \text{and} \quad w\_i = B(e\_i) \quad \text{for } i = 0, \dots, 4
  $$
* **Evaluation at infinity:**

  $$
  A(\infty) = A\_{n-1}(x), \quad B(\infty) = B\_{n-1}(x)
  $$

### Step 3: Pointwise Multiplication

Perform the $$2n-1 = \mathbf{5}$$ **recursive multiplications** ($$U\_0, \dots, U\_4$$) on the evaluated results. This is where the bulk of the computational cost lies:

$$
U\_i = v\_i \cdot w\_i = C'(e\_i)
$$

* Each $$U\_i$$ is a product of polynomials (or numbers) of size $$m$$, and these recursive calls continue until the polynomials are small enough to be handled by a classical or base-case multiplication algorithm.

### Step 4: Interpolation (Solve)

Use the $$2n-1 = 5$$ calculated products $$U\_i$$ to find the $$2n-1$$ coefficient blocks ($$C\_0, \dots, C\_4$$) of the unreduced result $$C'(x)$$.

The relationship between the evaluated values $$U\_i = C'(e\_i)$$ and the unknown coefficients $$C\_j$$ is a **Vandermonde system of linear equations**:

$$
\begin{pmatrix}
e\_0^0 & e\_0^1 & \cdots & e\_0^4 \\
e\_1^0 & e\_1^1 & \cdots & e\_1^4 \\
\vdots & \vdots & \ddots & \vdots \\
e\_4^0 & e\_4^1 & \cdots & e\_4^4
\end{pmatrix}
\begin{pmatrix}
C\_0 \\
C\_1 \\
\vdots \\
C\_4
\end{pmatrix}
=============

\begin{pmatrix}
U\_0 \\
U\_1 \\
\vdots \\
U\_4
\end{pmatrix}
$$

By pre-calculating the **inverse of the Vandermonde matrix**, the interpolation is performed quickly using only linear combinations (additions and scalar multiplications) of the $$U\_i$$ values over $$\mathbb{F}\_P$$.

This above explains well why Karatuba is a specialized version of Toom-2.

$$
\begin{pmatrix}
1 & 0 & 0\\
1 & 1 & 1 \\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
C\_0 \\
C\_1 \\
C\_2
\end{pmatrix}
=============

\begin{pmatrix}
a\_0b\_0 \\
a\_0b\_0 + a\_0b\_1 + a\_1b\_0 + a\_1b\_1\\
a\_1b\_1
\end{pmatrix}
$$

### Step 5: Recomposition and Final Reduction

1. **Recomposition:** Combine the resulting coefficient blocks $$C\_j$$ using shifts:

   $$
   C'(x) = C\_4(x) x^{4m} + C\_3(x) x^{3m} + C\_2(x) x^{2m} + C\_1(x) x^m + C\_0(x)
   $$
2. **Reduction:** Apply the final modulo reduction to get the element in $$\mathbb{F}\_{P^k}$$:

   $$
   C(x) = C'(x) \pmod{f(x)}
   $$

## 3. Practical Considerations for $$\mathbb{F}\_{P^k}$$

In specialized hardware and software for finite field cryptography (like pairing-based cryptography which uses very large $$k$$), Toom–Cook is highly favored over Karatsuba because of its lower exponent.

* **Choice of** $$n$$**:** The optimal choice for the splitting factor $$n$$ depends on the size of the extension degree $$k$$ and the hardware architecture. Higher $$n$$ reduces the asymptotic complexity but increases the overhead of the Evaluation and Interpolation steps. Typically, $$n=3$$ or $$n=4$$ provides the best real-world performance gain before the overhead becomes prohibitive.
* **Base Field Operations:** All additions, subtractions, and scalar multiplications are performed within the base field $$\mathbb{F}\_P$$, which must itself be computed efficiently (often using Karatsuba or classical methods for the underlying integer arithmetic).

> Written by [Ryan Kim](mailto:undefined) of Fractalyze


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fractalyze.gitbook.io/intro/primitives/abstract-algebra/extension-field/multiplication/toom-cook-multiplication.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.