2008/11/3 Kiran Kedlaya <[EMAIL PROTECTED]>: > > For the record, Drew Sutherland (cc'd on this) has some screamingly > fast code for the CRT method, which he spoke about at ECC this year.
Written in what? C? John > > Kiran > > eduardo wrote: >> 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 -~----------~----~----~----~------~----~------~--~---
