Algorithm for multiplication and reduction of ideals in imaginary quadratic number fields

[Richard Heylen <richardheylen@gmail.com>]

I'm trying to implement the algorithm for multiplication and reduction
of ideals in imaginary quadratic number fields.

I've tried to read the pari source code for ideal multiplication and
reduction but I have not been able to make much headway. I suspect
that the code copes with all sorts of number fields and it looks more
complicated than I expect from reading Buchmann Dullmann and Williams
"On the complexity and efficiency of a new key exchange mechanism"
which gives relatively short algorithms.

I have tried to reconcile the results I see from gp/pari with plugging
some suitable numbers into the algorithms mentioned in the paper but
so far I have failed.

It seems to me that given IQF=bnfinit(x^2+D) then the result of
idealmul(IQF,[A,B;0,C],[E,F;0,G]) should be [H,I;0,J] where H,I and J
can be obtained from A,B,C,D,E,F.
If someone could take the trouble to outline the relevant algorithm
then that'd be great.

Alternatively, Algorithm 3.2 of the above paper talks about
multiplying two ideals (A_1,B_1),(A_2,B_2). Perhaps it would be
easiest to tell me how to convert from the representation of ideals in
pari [E,F:0,G] to the (A_1,B_1) representation in the paper.

My first goal is independently to reproduce the fact that
idealpow(bnfinit(x^2+23),[2,0;0,1],3,1)==[1,0;0,1]

Thanks,

Richard Heylen