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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sat, May 17, 2014 at 10:51:00AM +0100, Richard Heylen wrote:
> 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.

Indeed. For imaginary quadratic number fields, you might prefer to use
binary quadratic forms (which do not depend on the choice of an integral
basis). For any other fields, there are non canonical representation
of ideals and ideal classes with induces lots of complications (there are no
simple algorithms to reduce an ideal to a canonical representant of the class
group).

> 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.

This is the function idealtwoelt() that does that.
thought in your case it is easy:
IQF.zk*[E,F;0,G] gives you [A_1,B_1] (mod IQF.pol)

> 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]

>From a pedantic view, this identity is fundamentally meaningless:
the ideal given by the matrix [2,0;0,1] depend on the choice of the integral
basis done by bnfinit. [2,0;0,1] might not even be an ideal.  It also depend on
the result of the reduction.  However, it is likely to be always true when it
makes sense, since the class number is 3.

(By the way, this computation can be done by hand easily.  You should try it if
you did not already)

So lets say your ideal is (2,(1-sqrt(-23))/2).
? B = bnfinit(x^2+23);
? id = idealhnf(B,2,(1-x)/2)
%27 = [2,0;0,1]
? id3 = idealpow(B,id,3)
%28 = [8,2;0,1]
You can check that this is the same as
? idealhnf(B,2^3,((1-x)/2)^3)
%30 = [8,2;0,1]
? [idr,gen] = idealred(B,[id3,1])
%36 = [[1,0;0,1],[2,1]~]
? K.zk*gen
%37 = 1/2*x+3/2
Thus, id3 is generated by  (1+3*sqrt(-23))/2
? norm(Mod(%37,B.pol))
%63 = 8

(so we solved a^2+a*b+6*b^2=8 and found a=1,b=1)

Cheers,
Bill.