Hi there! I attended the SAGE DAYS 10 in Nancy (Thanks the people there for everything!). As other colleague and me are interested in crypto interesting Elliptic Curves, we noticed that the SAGE function that calculates the Hilbert class polynomial needs magma, so we proposed at the Coding Sprint the implementation of this function, for instance with CM Methods or/and the CRT Methods. After some time spending on it we got some issues that surely can be corrected with some help/discussion:
We implemented the CM-version of it in purely sage-python code. Comparing timings with Magma our implementation was almost (here)- times slower. So we can emphasize 3 bottlenecks apart from computation of a j-Invariant: the computation of the appropriate precision, generating of all different reduced primitive quadratic forms and the using of Python. 1. An idea of the computation of the appropriate precision we gathered from Andreas Enge's article [http://hal.inria.fr/inria-00001040]. He gives an upper bound for the size of the largest coefficient of the polynomial. 2. To generate all reduced primitive quadratic forms we used first the function called BinaryQF_reduced_representatives() from quadratic forms library. After that we implemented our version of this function and got about 50% speed up, and the present code doesn't generate primitive forms if the discriminant is non-fundamental. 3. But anyway our implementation was a snail comparing to magma's one. And then we tried to use Cython to implement the same function. As a result our implementation was a bit faster than magma's at least in experiments we ran. The only thing worried us was the using of type long long for discriminant of quadratic field. It means the input parameter is bounded by 2^63. It is O.K. for D around -2^63; even magma will break down since the complexity of the algorithm is O(|D|). Now I would like to ask some questions: * Shall we consider the bigger value of D then values fit in long long? * Is it safe to use long long? Is it 64-bit on all platforms? Does Cython care about that? * We can perhaps use mpz_t (from GMP) instead of long long. Then we need to know how can we input/ouput a variable of this type in Cython. Is there some documentation about that? thanks in Advance! cheers Ed --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
