On principal ideal testing in totally complex quartic fields and the determination of certain cyclotomic constants
Johannes A Buchmann, H. C. Williams · Mathematics of Computation · 1987
Let L \mathcal {L} be any totally complex quartic field. Two algorithms are described for determining whether or not any given ideal in L \mathcal {L} is principal. One of these algorithms is very efficient in practice, but its complexity is difficult to analyze; the other algorithm is computationally more elaborate but, in this case, a complexity analysis can be provided. These ideas are applied to the problem of determining the cyclotomic numbers of order 5 for a prime p ≡ 1 ( mod 5 ) p \equiv 1\;\pmod 5 . Given any quadratic (or quintic) nonresidue of p, it is shown that these cyclotomic numbers can be efficiently computed in O ( ( log p ) 3 ) O({(\log p)^3}) binary operations.