A fast algorithm for finding a short generator of a principal ideal of $\mathbb{Q}({\zeta }_{p^s})$

Jean-Francois Biasse

We present a heuristic algorithm to compute the ideal class group, and a generator of a principal ideal in $\mathbb{Q}({\zeta }_{p^s})$ in time $2^{O(n^{1/2+\epsilon })}$ for $n:= deg(K…