Loïc Grenié on Mon, 03 Apr 2017 08:29:45 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Reuse of data in rnfkummer/computing order of galois elements without it |
* Watson Ladd [2017-04-03 06:53]:
> Dear all,
> I have a program which computes many rnfkummer's over the same base
> field K. All the rnfkummers are quadratic extensions. This ends up
> taking a very, very long time, particularly as many of the extensions
> have galois groups which contain elements of orders which are two
> large and are thus thrown out, so the time spent computing the
> extensions is wasted.
>
> My questions are as follows:
>
> 1: Can anything be done to accelerate the repeated rnfkummers?
Not for quadratic extensions. (In general, to compute a Kummer extension
of exponent p we need to p-th roots of unity to the base field; this
could be re-used. Useless for p = 2...)
> 2: Is there a way to determine the maximal order of an element of the
> Galois group of the resulting field without computing the field via
> rnfkummer? I know about bnrgaloismat, but it doesn't seem as though
> the resulting representation of the galois group can be used to find
> the order of elements easily.
By "Galois group" I understand the Galois group of (class field) over K.
(If you meant Gal(class field/Q), modify the following with the maximal
order allowed in the quotient.)
I don't see a fast if-and-onlu-if algorithm. There's a quick early abort
though : pick prime ideals in the base field not dividing the conductor
and compute their order in the ray class group (see below); if this
order is too large, stop. Under GRH, a suitable effective Chebotarev
bound would turn this into a fast rigorous algorithm. In practice, if
the test does not find elements of large order, it means they (probably)
don't exist and you can go on with rnfkummer...