Reduced and Refined Karatsuba - Simple Micro-optimization of Karatsuba Multiplication

Introduction

Karatsuba multiplication is a famous algorithm for efficient bignum multiplication. In most descriptions, it’s said to reduce 4 multiplications to 3 multiplications, 4 additions and 2 subtractions.

In fact, there’s an extremely simple and less-known micro-optimization known as Refined Karatsuba that only uses 3.5 additions. It can be useful in high-speed cryptography in general, and in embedded systems with limited resource. A reader may find it’s trivial, but it’s almost never documented in most textbooks or tutorials, thus often missed. This article attempts to raise its awareness.

For modular multiplication in a finite field, an extra technique called Reduced Refined Karatsuba further reduces the cost to 3 additions.

Standard Karatsuba

First, let’s have a quick review. In standard Karatsuba multiplication, we have two integers $a$$a$ and $b$$b$. For simplicity, assume both integers have even numbers of digits, not odd.

$$\begin{array}{r}a=7670\\ b=2196\end{array}$$$$\begin{array}{r}a=7670\\ b=2196\end{array}$$

First, we “split” both integers at the middle into two parts of equal size: $a_h$$a_h$, $a_l$$a_l$, $b_h$$b_h$, and $b_l$$b_l$. Specifically, we rewrite the integer $a$$a$ in the form of $a=a_h\times {10}^n+a_l$$a=a_h\times {10}^n+a_l$, and same for $b$$b$.

$$\begin{array}{rr}a=a_h\times {10}^n+a_l& a=76\times {10}^2+70\\ b=b_h\times {10}^n+b_l& b=21\times {10}^2+96\end{array}$$$$\begin{array}{rr}a=a_h\times {10}^n+a_l& a=76\times {10}^2+70\\ b=b_h\times {10}^n+b_l& b=21\times {10}^2+96\end{array}$$

Second, independently multiply the low and high parts of the result.

$$\begin{array}{rr}L=a_l\times b_l& L=70\times 96=6720\\ H=a_h\times b_h& H=76\times 21=1596\end{array}$$$$\begin{array}{rr}L=a_l\times b_l& L=70\times 96=6720\\ H=a_h\times b_h& H=76\times 21=1596\end{array}$$

Third, calculate the middle part. There are two equivalent ways to calculate this: addition and subtraction. We use the subtractive variant.

$$\begin{array}{rl}M& =(a_l-a_h)\times (b_h-b_l)\\ M& =(70-76)\times (21-96)\\ & =(-6)\times (-75)\\ & =450\end{array}$$$$\begin{array}{rl}M& =(a_l-a_h)\times (b_h-b_l)\\ M& =(70-76)\times (21-96)\\ & =(-6)\times (-75)\\ & =450\end{array}$$

The final result is:

$$\begin{array}{rl}& H\times {10}^{2n}+(M+H+L)\times {10}^n+L\\ & 1596\times {10}^4+8766\times {10}^2+6720\\ =& 16843320\end{array}$$$$\begin{array}{rl}& H\times {10}^{2n}+(M+H+L)\times {10}^n+L\\ & 1596\times {10}^4+8766\times {10}^2+6720\\ =& 16843320\end{array}$$

This is the Karatsuba Identity. Using the schoolbook algorithm, it requires 4 half word multiplications (16 digits in total), as the high and low parts of the results must all be multiplied with each other. The Karatsuba algorithm needs just 3 half-word multiplications (12 digit) at the expense of 4 additions and 2 subtractions. But we can do better.

Refined Karatsuba

Note that in our final formula,

$$H\times {10}^{2n}+(M+H+L)\times {10}^n+L$$$$H\times {10}^{2n}+(M+H+L)\times {10}^n+L$$

both $H$$H$ and $L$$L$ have $2n$$2n$ digits. And in $H\times {10}^{2n}$$H\times {10}^{2n}$, we add exactly $2n$$2n$ digits of zero at the end. Therefore, computing $H\times {10}^{2n}+L$$H\times {10}^{2n}+L$ is simple - write $H$$H$ on the left and $L$$L$ on the right.

$$\begin{array}{ll}H\times {10}^{2n}+L& 1596\times {10}^4+6720\\ =H\parallel L& =15966720\end{array}$$$$\begin{array}{ll}H\times {10}^{2n}+L& 1596\times {10}^4+6720\\ =H\parallel L& =15966720\end{array}$$

Then, we can calculate $(M+H+L)\times {10}^n$$(M+H+L)\times {10}^n$ in place, by adding it in the middle of our intermediate result. Let $l_i$$l_i$, $h_i$$h_i$ and $m_i$$m_i$ represents each digit of the number, then see the visualization below.

$$\begin{array}{rrrrrrrrr}{h}_4& h_3& \boxed{{\displaystyle h_2}}& \boxed{{\displaystyle h_1}}& \overline{)l_4}& \overline{)l_3}& l_2& l_1& 15\underset{―}{\underset{―}{9667}}20\\ & +& h_4& h_3& \boxed{{\displaystyle h_2}}& \boxed{{\displaystyle h_1}}& & & +\phantom{0}15\underset{―}{\underset{―}{96}}\phantom{00}\\ & +& \overline{)l_4}& \overline{)l_3}& l_2& l_1& & & +\phantom{0}\underset{―}{\underset{―}{67}}20\phantom{00}\\ & +& m_4& m_3& m_2& m_1& & & +\phantom{0}0450\phantom{00}\end{array}$$$$\begin{array}{rrrrrrrrr}{h}_4& h_3& \boxed{{\displaystyle h_2}}& \boxed{{\displaystyle h_1}}& \overline{)l_4}& \overline{)l_3}& l_2& l_1& 15\underset{―}{\underset{―}{9667}}20\\ & +& h_4& h_3& \boxed{{\displaystyle h_2}}& \boxed{{\displaystyle h_1}}& & & +\phantom{0}15\underset{―}{\underset{―}{96}}\phantom{00}\\ & +& \overline{)l_4}& \overline{)l_3}& l_2& l_1& & & +\phantom{0}\underset{―}{\underset{―}{67}}20\phantom{00}\\ & +& m_4& m_3& m_2& m_1& & & +\phantom{0}0450\phantom{00}\end{array}$$

It should be obvious by now: the standard Karatsuba formula has a hidden inefficiency: a duplicated addition. If $H$$H$ and $L$$L$ has $2n$$2n$ digit, the lowest $n$$n$ digits in H and highest $n$$n$ digit in $L$$L$ are always added together, twice.

We can solve the problem by precomputing the result. For maximum efficiency, $H^{\prime }$$H^{\prime }$ can be computed on-the-fly in the middle of the calculation of $H$$H$, with tight assembly code.

$$\begin{array}{rl}{H}^{\prime }& =(h_4,h_3,h_2,h_1)+(0,0,l_4,l_3)\\ & =1596+67=1663\end{array}$$$$\begin{array}{rl}{H}^{\prime }& =(h_4,h_3,h_2,h_1)+(0,0,l_4,l_3)\\ & =1596+67=1663\end{array}$$

Then the final summation simplifies to:

$$\begin{array}{rrrrrrrrr}{h}_4^{\prime }& h_3^{\prime }& h_2^{\prime }& h_1^{\prime }& l_2& l_1& l_2& l_1& 16632020\\ & +& h_4^{\prime }& h_3^{\prime }& h_2^{\prime }& h_1^{\prime }& & & +\phantom{0}1663\phantom{00}\\ & +& m_4& m_3& m_2& m_1& & & +\phantom{0}0450\phantom{00}\\ p_8& p_7& p_6& p_5& p_4& p_3& p_2& p_1& 16843320\end{array}$$$$\begin{array}{rrrrrrrrr}{h}_4^{\prime }& h_3^{\prime }& h_2^{\prime }& h_1^{\prime }& l_2& l_1& l_2& l_1& 16632020\\ & +& h_4^{\prime }& h_3^{\prime }& h_2^{\prime }& h_1^{\prime }& & & +\phantom{0}1663\phantom{00}\\ & +& m_4& m_3& m_2& m_1& & & +\phantom{0}0450\phantom{00}\\ p_8& p_7& p_6& p_5& p_4& p_3& p_2& p_1& 16843320\end{array}$$

This is the Refined Karatsuba Identity, it requires only 7 half-word (3.5 full-word) additions instead of 8. This micro-optimization was originally proposed by Daniel J. Bernstein.

Reduced Refined Karatsuba

In cryptography applications, arithmetic operations are modular (i.e. the numbers “wrap back” after reaching a maximum value) because they represent elements in a finite field. Once the value went off the scale, a modular reduction is needed to bring it back within the proper range. In elliptic curve cryptography, extremely efficiency special-purpose reduction algorithms can be used, because the field size of a curve is often carefully chosen.

For example, in base-10 arithmetic, if the modulus is $n={10}^k-1$$n={10}^k-1$, casting out 9 is such an efficient algorithm. We simply split the number into $k-1$$k-1$ parts and add them together - repeat if necessary. For example: $16843320\text{ mod }9999=$$16843320\text{ mod }9999=$ $1684+3320$$1684+3320$ $=5004$$=5004$.

Fast reduction algorithms in cryptography is outside the scope of the article, I only want to convince you that sometimes using an extra reduction step is reasonable, which brings us to the Reduced Refined Karatsuba algorithm. It reduces the number of additions from 3.5 to 3.