UM Math Graduate Student Seminar

Michael Weiss
University of Miami

will present

Fast Multiplication Algorithms

Friday, November 6, 2015, 5:00pm
Ungar Building Room 402


Abstract:

Fast algorithms for multiplication of integers and polynomials are of great importance for calculations in number theory and cryptography where precise results for arbitrarily large numbers is required. In this talk I will give an overview of some of these algorithms that improve upon naive “schoolbook” multiplication (O(n^2)). In particular, I will present Karatsuba’s algorithm and the more general Toom-Cook multiplication algorithms as a class of algorithms that use polynomial interpolation to compute integer and polynomial products. I’ll then describe how they can be constructed as a series of linear transformations and can transformed via the Transposition Principle to algorithms that compute an important, smaller product called the middle product. This talk will focus on understanding the philosophy and general ideas behind the algorithms, and will be lighter on technical considerations such as the specifics of implementation, so coding knowledge or prior familiarity with the subject won’t be required!

 


Back to the seminar's page