Hilbert Class Polynomial function in SAGE...
eduardo
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
John Cremona
. There are patches undergoing review now relevant to this (at
#4120). That function was made a lot more efficient in #3857 (now
merged) but that function returns a list of the representative forms,
while you only need the number. The patch at #4120 has a function to
give the number but unfortunately does not use the speedups
implemented (by be and then Nils Skoruppa) in #3857. For such a
critical function I am sure that it should be implemented in cython
anyway.
John
2008/11/3 eduardo <eoca...@gmail.com>:
Martin Albrecht
> * 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?
Hi there,
AFAIK there is no documentation as such but plenty of examples. Note, that
Sage integers are basically mpz_t.
See sage.rings.integer.pyx for details. In particular there are C functions to
get/set mpz_ts from/for Integers.
Cheers,
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: martinr...@jabber.ccc.de
Kiran Kedlaya
fast code for the CRT method, which he spoke about at ECC this year.
Kiran
John Cremona
>
> 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
Robert Bradshaw
No idea what your constants are like, but 2^63 nanoseconds is
something like 290 years, so on face value that seems prohibitively
expensive without some massive parallelization of some sort (which
would probably require a complete rewrite of your algorithm.)
However, if I remember correctly the runtime depended on the
factorization of D, not just the size of D itself.
What I would suggest is keeping the long-long version, as that is
probably the most useful useful case, and the speed improvements are
huge. One could also have the mpz version as well, only called when
needed.
> * Is it safe to use long long? Is it 64-bit on all platforms? Does
> Cython care about that?
long long always has at least 64 bits, and is required on all
platforms we target for Sage, so it is safe to use 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?
Here is how you would do it (the easy way):
from sage.rings.integer cimport Integer
def add_via_gmp(Integer a, Integer b):
cdef Integer z = PY_NEW(Integer)
mpz_add(z.value, a.value, b.value)
return z
There is also the issue of memory management (if one needs temporary
mpz_t values) and the code is much harder to read/debug. Of course,
99% of the savings would be accomplished by just moving the inner
loop or two to use the mpz_* functions directly, so writing the whole
function this way would be overkill. The speed of this implementation
would almost certainly be closer to the speed of the Python version
than to the speed of the long-long version, as mpz_t arithmetic is
many, many times slower than manipulating long-longs.
- Robert
Alex Ghitza
than Magma.
I've just posted a patch integrating Eduardo's and Andrey's code into
Sage quadratic fields, at
http://trac.sagemath.org/sage_trac/ticket/4990
Best,
Alex
--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/