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]; then charorder(C, bnrisprincipal(C, pr, 0)) is the order of cl(pr) in Cl_f(K) Cheers, K.B. -- 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] `