Karim Belabas on Mon, 03 Apr 2017 08:06:48 +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...

N.B. If
  C = bnrinit( bnfinit(K), f );
  pr = idealprimedec(C, p)[1];
  charorder(C, bnrisprincipal(C, pr, 0))
is the order of cl(pr) in Cl_f(K)


Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]