Re: all divisors of a cyclotomic integer

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

* John Cremona [2022-09-02 12:05]:
> I think that if a user thinks that some utility function would be useful,
> and it is easy to provide, then the software authors should consider adding
> it even if they themselves cannot think of an application.
> 
> In my code for computing bianchi modular forms (which does not use libpari
> as I am not clever enough to use it) I have a lot of ideal utilities, and
> listing all ideal divisors of an ideal is one of them.
> 
> So I vote to add such a function.

The possible variants are essentially described in ??divisors : here's
the loop version without using the (known!) factorization of each
divisor, just printing the result:

   idealdivisors(K, id) =
   { my(F = idealfactor(K, id), P = F[,1], E = F[,2], d);
     forvec(e = vectorv(#E,i,[0,E[i]]),
            d = idealfactorback(K,P,e); print(d))
   }

  ? K = nfinit(polcyclo(68));
  ? idealdivisors(K, 2*x^30 + 4*x^26 + 2*x^22)
  /* output omitted */

There are quite a few such variants, based on idealfactor and forvec.
With or without restricting to principal ideals for instance [as in
Bill's code]; or returning a list instead of looping through the
results, or maybe together with their factorizations, etc. I'd rather
give a few examples in the documentation and keep the interfaces simple.

If efficiency is a concern one could
- use a Gray code to perform a single multiplication for each new
  divisor, instead of idealfactorback from scratch.

- multiplications by prime ideals which are much cheaper than general
  multiplications; note that idealfactorback doesn't use this trick
  because it must cater to arbitrary "factorizations" involving arbitrary
  ideals not only primes [it could check its input first then take
  advantage of the trick if possible; but it currently doesn't]

- to output principal ideals only, one could precompute the images of the
  P[i] in the class group (matrix of discrete logs M) and restrict to
  exponent vectors such that M*v = 0 mod the class group elementary divisors.
  
Again each can be done in 5 to 10 lines of GP. I hardcoded a specific
variant in C for bnfisintnorm() because we had a specific application,
namely thue().

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251), Université de Bordeaux
Vice-président en charge du Numérique
T: (+33) 05 40 00 29 77; http://www.math.u-bordeaux.fr/~kbelabas/
`