Using our M values from the previous slide, this equals

M1 + M2 + M3 + M4

The value we want is M2 + M3, so define M23

M23 = (XH + XL) * (YH + YL)

And our desired value is M23 – M1 – M4

Ok, all I see here is wackiness! How does this help?

Let's go back to the original equation now, and plug this back in

XY = 2NXHYH + 2N/2(XHYL + XLYH) + XLYL

= 2NM1 + 2N/2(M23 – M1 – M4) + M4

Only 3 distinct multiplications are now needed!

More Integer Multiplication

Looking back, we see that M23 involves multiplying at most (N/2)+1 bit integers, so asymptotically it is the same size as our other recursive multiplications

We have to do some extra additions and two subtractions, but these are all Theta(N) operations

Thus, we now have the following recurrence:

T(N) = 3T(N/2) + Theta(N)

This solves to Theta(Nlg3) Theta(N1.58)

Now we have an asymptotic improvement over the Gradeschool algorithm

Still a lot of overhead, but for large enough N it will run faster than Gradeschool

See karat.txt

Integer Multiplication

Can we do even better?

If we multiply the integers indirectly using the Fast Fourier Transform (FFT), we can achieve an even better run-time of Theta(NlgN)

Don't worry about the details of this algorithm

But if you are interested, read the text Ch. 41

For RSA, we will be ok using a GradeSchool / Karatsuba Hybrid

GradeSchool used for smaller sizes, switching to Karatsuba for larger sizes