Master’s Thesis Presentation • Scientific Computation — Fast Algorithms for Finding the Characteristic Polynomial of a Rank 2 Drinfeld Module

Friday, September 14, 2018 1:00 pm - 1:00 pm EDT (GMT -04:00)

Yossef Musleh, Master’s candidate
David R. Cheriton School of Computer Science

We introduce a Monte Carlo randomized algorithm for computing the characteristic polynomial of a rank 2 Drinfeld module than runs in $O(n^2 \log n \log \log n \log q)$ field operations. We also introduce a deterministic algorithm that runs in $O(n^{2.6258} \log n + n^2 \log n \log log n \log q)$ field operations. Both approaches are a significant improvement over the current literature.