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

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.