# Karatsuba Multiplication

## 1. Field Context: $$\mathbb{F}\_{P^k}$$ Multiplication

In the extension field $$\mathbb{F}\_{P^k}$$, an element $$A$$ is represented as a polynomial of degree up to $$k-1$$ with coefficients in the base field $$\mathbb{F}\_P$$:

$$
A(x) = a\_{k-1}x^{k-1} + \dots + a\_1 x + a\_0
$$

Multiplying two elements $$A$$ and $$B$$ in $$\mathbb{F}\_{P^k}$$ involves two steps:

1. **Polynomial Multiplication:** Compute $$C'(x) = A(x) \cdot B(x)$$.
2. **Reduction:** Compute $$C(x) = C'(x) \pmod{f(x)}$$, where $$f(x)$$ is the irreducible polynomial of degree $$k$$ defining the extension.

The **Karatsuba algorithm** is used to speed up the **Polynomial Multiplication** step (Step 1).

## 2. Karatsuba Algorithm for Polynomials

We aim to compute $$C'(x) = A(x) \cdot B(x)$$, where $$A(x)$$ and $$B(x)$$ are polynomials of degree $$N=k-1$$. We assume $$k$$ is an even number for simplicity, and let $$m = k/2$$.

### Step 1: Splitting (Divide)

The polynomials $$A(x)$$ and $$B(x)$$ are split into two halves, where $$A\_1(x), A\_0(x), B\_1(x), B\_0(x)$$ are polynomials of degree less than $$m$$

$$
A(x) = A\_1(x) \cdot x^m + A\_0(x), \quad B(x) = B\_1(x) \cdot x^m + B\_0(x)
$$

The product $$C'(x) = A(x)B(x)$$ expands algebraically as:

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

The classical method would require **four** recursive polynomial multiplications of size $$m$$.

### Step 2: Three Recursive Multiplications

Karatsuba reduces this to **three** recursive polynomial multiplications, where the coefficients of the polynomials are in $$\mathbb{F}\_P$$ (or another base field).

1. $$M\_1(x)$$ **(High Part):**

   $$
   M\_1(x) = A\_1(x) \cdot B\_1(x)
   $$
2. $$M\_2(x)$$ **(Low Part):**

   $$
   M\_2(x) = A\_0(x) \cdot B\_0(x)
   $$
3. $$M\_3(x)$$ **(Middle Part – The Karatsuba Trick):**

   $$
   M\_3(x) = (A\_1(x) + A\_0(x)) \cdot (B\_1(x) + B\_0(x))
   $$

### Step 3: Combination (Conquer)

The middle term is extracted by performing polynomial additions and subtractions over $$\mathbb{F}\_P$$:

$$
A\_1(x) B\_0(x) + A\_0(x) B\_1(x) = M\_3(x) - M\_1(x) - M\_2(x)
$$

The final unreduced product $$C'(x)$$ is then constructed:

$$
C'(x) = M\_1(x) \cdot x^{2m} + (M\_3(x) - M\_1(x) - M\_2(x)) \cdot x^m + M\_2(x)
$$

(Multiplication by $$x^m$$ or $$x^{2m}$$ is a simple coefficient shift.)

### Step 4: Final Reduction

After obtaining the unreduced product $$C'(x)$$, the result must be reduced modulo the defining polynomial $$f(x)$$ to get the final result $$C(x) \in \mathbb{F}\_{P^k}$$:

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

## 3. Complexity in $$\mathbb{F}\_{P^k}$$ Context

For a base field $$\mathbb{F}\_P$$, the Karatsuba algorithm reduces the complexity of polynomial multiplication from $$O(k^2)$$ base field operations (classical) to $$O(k^{\log\_2 3})$$ base field operations.

* **Recursive Call Size:** The size of the polynomials in the recursive calls is reduced from degree $$k-1$$ to approximately degree $$k/2 - 1$$.
* **Base Operations:** The "cost" of addition/subtraction ($$O(k)$$) and the recursive multiplications ($$3 \cdot T(k/2)$$) is measured in terms of operations within the base field $$\mathbb{F}\_P$$.

The overall time complexity for the polynomial multiplication step remains:

$$
T(k) = O(k^{\log\_2 3}) \approx O(k^{1.585})
$$

Karatsuba is highly effective in cryptographic contexts (like Elliptic Curve Cryptography) that extensively rely on fast finite field arithmetic in $$\mathbb{F}*{P^k}$$ or $$\mathbb{F}*{2^k}$$.

> Written by [Ryan Kim](https://app.gitbook.com/u/cPk8gft4tSd0Obi6ARBfoQ16SqG2 "mention") of Fractalyze