Re: Reuse of data in rnfkummer/computing order of galois elements withou

Dear Watson,

I expect you are trying to mimic the computations I have done a few

years ago.

On 2017-04-03 at 8:06 GMT+02:00 Karim Belabas wrote:

* 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...)

You can compte rnfkummer(bnf,subgroup,-2) which gives a basis of the

2-extensions, i.e. an rnfkummer for a basis of the subgroup, seen as a

(Z/2Z)-vector space. You can then multiply the discriminants of the

relative polynomials to get all the remaining polynomials. (rnfkummer for

negative degree has been added precisely for the type of computations

you are trying to do !)

> 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...

The early abort strategy worked fine a few years ago...

Loïc