Re: Computing generator of ideal I^n

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* Jeroen Demeyer [2013-08-07 17:05]:
> I have a number field K and an ideal I which has order n in the
> class group. Therefore, I^n is a principal ideal.
> 
> I want to compute a generator for I^n and I'm wondering if there is
> a faster way than first computing I^n and then calling
> bnfisprincipal(). Can the information that the ideal is given as
> n-th power be used to speed up this computation?

Sure! Unfortunately, it's awkward to do this in GP : the (libpari)
function isprincipalfact() is used internally for this, see Libpari's
manual, section "Computing in the class group"

  (21:19) gp > ??"Computing in the class group"@
  [...]

   GEN isprincipalfact(GEN bnf,  GEN C,  GEN L,  GEN f, long flag) is about the
same  as  bnfisprincipal0  applied  to  C prod L[i]^{f[i]},  where the L[i] are
ideals, the f[i] integers and C is either an ideal or NULL (omitted). Make sure
to include nf_GENMAT in flag!

  ? install(isprincipalfact, GDGGGL)
  ? K = bnfinit(y^2+23);
  ? isprincipalfact(K,, K.gen, K.cyc,  4/*nf_GENMAT*/)
  %2 = [[0]~, [[1, 1/2]~, 1; 2, 1]]

The result is [e, t] as in bnfisprincipal(), with the important difference that
't' is given in *factored* form (which is undocumented in GP, but supported by
most libpari number field functions).

> It suffices to do this for the ideals generating the class group,
> but that's already slow enough for the field that I'm using.

In fact, this is often already part of the bnfinit structure (dynamically
added as soon as a function requires it). It can be forced:

  ? install(check_and_build_cycgen, G)
  ? check_and_build_cycgen(K)
  %3 = [Mat([[2, 1]~, 1])]

(this is now part of K, all further calls will be instantaneous)

This is a vector of generators for the g_i^d_i, where the g_i are the class
group generators, and the d_i are their orders.

Cheers,

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