Opened 20 months ago

Last modified 2 months ago

#29064 new enhancement

is_galois() / automorphisms() can be made faster

Reported by: rburing Owned by:
Priority: major Milestone: sage-9.5
Component: number fields Keywords: is_galois, automorphisms
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (4)

comment:1 Changed 18 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

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.

comment:2 Changed 13 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:3 Changed 7 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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

comment:4 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.