Integer Multiplication

Number-theoretic algorithms are widely used, especially in cryptography. These schemes depend on generating large prime numbers and on the difficulty of factoring large integers into primes.

Number-theoretic algorithms measure input size by the number of bits needed to represent a number. For an integer $n$, the bit length is $d=\lfloor \log n\rfloor +1$, so a linear number-theoretic algorithm is one that runs in $O(d)$ time.

Integer Multiplication

The standard (manual) method for multiplying large numbers uses long multiplication. To multiply two $d$-digit numbers, this method performs $O(d^2)$ single-digit multiplications.

  123
× 456
------
  738    ← 123 × 6
 6150    ← 123 × 50
49200    ← 123 × 400
------
56088

Can We Multiply Faster?

For centuries, $O(d^2)$ was the best we had. Key breakthroughs:

• 1963: Karatsuba’s algorithm — $O(d^{{\log }_{2}3})$ time
• 1971: Schönhage–Strassen algorithm — $O(d\times \log d\times \log \log d)$
• 2019: Harvey & Van der Hoeven — optimal $O(d\log d)$ time

Karatsuba’s Multiplication Algorithm

Any Two Numbers Can Be Split In Half

Let $u$ and $v$ be two $2d$-bit integers, split into high and low $d$-bit parts:

$u=2^d{U}_1+U_0,v=2^d{V}_1+V_0$

Therefore, their product $uv=(2^d{U}_1+U_0)(2^d{V}_1+V_0)$ can be expanded as:

This expansion reduces the number of multiplications from four to three ($U_1{V}_1$, $U_0{V}_0$, and $(U_1-U_0)(V_1-V_0)$) resulting in $O(d^{{\log }_{2}3})$ time.

Note that the $2^d$ is a linear shifting operation as multiplying a number of the form $2^x$ is simply shifting the number, and the additional and subtraction are linear.

EXAMPLE

Given $U=(67{)}_{10}=(1000011{)}_2$ and $V=(31{)}_{10}=(11111{)}_2$

Then to multiply these two numbers, first we want to have it as even number of bits, so pad 0 to $U$ resulting in $U=(01000011{)}_2$.

• $2d$ is always an even number

To make $U$ and $V$ equal size, pad $V$ so that it has the same number of bits as $U$, we then get

• $U=(01000011{)}_2$.
• $V=(00011111{)}_2$

Now they are both $2d$ bit numbers, where $2d=8->d=4$.

So starting with this $2d$ even number, we can break it into halves of size $d$

See how:

• $U_1=(0100{)}_2=(4{)}_{10}$
• $U_0=(0011{)}_2=3_{10}$
• $V_1=0001_2=1_{10}$
• $V_0=(1111{)}_2=15_{10}$

If we shift $U_1$ by $4$ places, then we get $U_1<<4=(01000000{)}_2=(64{)}_{10}$. This is the same as $U_1\times 2^4$ due to the way binary works.

Pad $0$ to make $U_0$ the same length and $U_1$, i.e. $U_0=00000011_2$

If we added $U_0$ to $U_1<<4$, we get: $(U_1<<4)+U_0=01000000_2+00000011_2=01000011_2=67_{10}$ which is $U$

Any number $U$ and $V$, ensuring that they are even (have $2d$ digits), you can break it into two halves of $d$ bits and the number $U$ is nothing but $2^d{U}_1+U_0$

Divide & Conquer Approach

The form above decomposes the multiplication uv (problem of multiplying two 2d-bit numbers) into: three d-bit multiplications: 1 U1V1 2 (U1 − U0)(V1 − V0) 3 U0V0 plus some simple left shifting* and some additions/subtractions. * multiplication by any 2 k requires shifting the bits leftwards by k positions –reason!

This can be repeated to continually divided, so a $2d$ bit multiplication can be divided into 3 $d$ bit operations + $O(d)$ operation, this can be repeated to get 9 $\frac{d}{2}$ operations until some base case. This base case doesn’t have to be $1$ due to hardware implemntation that can do multiplication up to a certain fixed size (128 bit register can do 2 64 bit multiplcations). So get it down to a level where you can multiply on the hardware and return

The time complexity of this divide-and-conquer approach can be expressed using the recurrence relationship: T(2d) = 3T(d) + cd, where c is some constant. Solving this recurrence yields the O(d log2(3)) -time algorithm

Example