Richard Heylen on Sat, 17 May 2014 11:51:11 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Algorithm for multiplication and reduction of ideals in imaginary quadratic number fields |
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