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: |
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
- Milestone changed from sage-9.1 to sage-9.2
comment:2 Changed 13 months ago by
- Milestone changed from sage-9.2 to sage-9.3
comment:3 Changed 7 months ago by
- 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
- Milestone changed from sage-9.4 to sage-9.5
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.