Karim Belabas on Tue, 02 Dec 2008 18:41:40 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: idealstar

* John Cremona [2008-12-02 18:27]:
> Dear pari,
> The function idealstar(k,I) for an ideal I in a number field k,
> returns an abstract representation of the group (Z_K/I) together with
> generators.  using this I can easily form the map from the abstract
> group to the concrete one, but what about the inverse?  In other
> words, given an element of Z_K coprime to I, how can I express it in
> terms of the abstract generators?  is there a function for this, or
> has someone else implemented it?
> I fully realise that one special case of this is the discrete log
> problem for Z/pZ, and am not asking for anything which is very fast,
> but I hope I will not have to kist all the lements and check them one
> by one.

(18:30) gp > ???"discrete log"
bnfisprincipal elllog         fflog          ideallist      ideallog
idealstar      znlog

I'd have a look at "ideallog" ... 

As you mentionned, the bottleneck is the computation of discrete logs in
(Z_K / P) for maximal ideals P dividing I. This will be slow if Norm P - 1
is not smooth ( basic Pohlig-Hellman + Shanks ).


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-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]