is_galois() / automorphisms() can be made faster

[rburing]

Let K.<a> = NumberField(f). The method K.is_galois() does the following:

if self.degree() < 12:
    return self.galois_group(type='pari').order() == self.degree()
else:
    return len(self.automorphisms()) == self.degree()

The method K.automorphisms() defined here runs essentially the PARI code

nfgaloisconj(nfinit(f))

to compute the automorphisms, followed by some conversions. As just discussed on pari-users, it is faster to run instead

nfgaloisconj(f)

because nfinit computes the full factorization of the discriminant of the polynomial, which is not (always) needed.

The question is whether the nfinit(f) data is really needed for the conversions in K.automorphisms(). If it is not needed, then the optimization (that is, calling nfgaloisconj(f) instead) can be implemented there. If it is needed, then the optimization can be implemented in is_galois().

Either way, this would make is_galois() work faster for extensions of high degree.

The fact that it is currently slow was reported on Ask SageMath, which led me to investigate.

Component: number fields

Keywords: is_galois, automorphisms

Issue created by migration from https://trac.sagemath.org/ticket/29064

[mkoeppe]

comment:1

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[mkoeppe]

comment:3

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[S17A05]

I just checked this for K.embeddings(K) (which is nowadays called in K.automorphisms()) for K.<i> = NumberField(x^2 + 1000) and K.<j> = NumberField(x^50 + 1000) by simply modifying the line conj = self.pari_nf().nfgaloisconj() to conj = pari(f).nfgaloisconj() in the code (where f = self.pari_polynomial("y")). In both cases it takes about 100 ns per loop with the regular method, while it takes about 150 µs per loop for the first example and more than 4 ms per loop for the second example with the modification. Maybe I am doing something wrong, but it seems to me that the simplifications performed by nfinit greatly reduce the time needed for the later computations in the method.