Paper Presentation at ANTS-XII

Jean-François Biasse
University of Kaiserslautern, Germany
Friday, September 2, 2016 - 11:00

Former ISPIA Post-Doctoral Fellow,  Jean-François Biasse, will be presenting a paper at the Twelfth Algorithmic Number Theory Symposium (ANTS-XII).

The paper being presented is Fast heuristic algorithms for computing relations in the class group of a quadratic order with applications to isogeny evaluation and is co-authored by Dr. Claus Fieker, professor at the University of Kaiserslautern, Germany, Faculty of Mathematics, and ISPIA Board Member, Dr. Michael John Jacobson, Jr.


In this paper, we present novels algorithms for finding small relations and ideal factorizations in the ideal class group of an order in an imaginary quadratic field, where both the norms of the prime ideals and the size of the coefficients involved are bounded. We show how our methods can be used to improve the computation of large-degree isogenies and endomorphism rings of elliptic curves defined over finite fields. We obtain improved heuristic complexity results in almost all cases for these problems, and significantly improved performance in practice, especially in situations where the ideal class group can be computed in advance.