Undergraduate Mathematical Sciences Seminar

Thursday, May 3, 12:30--1:50pm

MOR 230


Optimizing the Speed of Polynomial Evaluation

Tom Boothby
University of Washington

In many areas of mathematics, and other sciences, polynomials are evaluated thousands, even millions of times in a given computation. Especially in cryptography, these polynomials may have incredibly high degree. Thus, if polynomial evaluation is slow, entire classes of problems become intractable. In this talk we will discuss a few methods to evaluate polynomials and their respective tradeoffs, including an algorithm created by the speaker. There will be brief excursion into computation using Directed Acyclic Graphs, and some theory about addition chains and how they are used to optimize exponentiation.

No slides were used for this talk.