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