Opened 14 years ago

Closed 14 years ago

#4901 closed defect (fixed)

[with patch, positive review] bug in elliptic logarithm

Reported by: cremona Owned by: was
Priority: major Milestone: sage-3.3
Component: number theory Keywords: elliptic logarithm
Cc: AlexGhitza Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

#4214 introduced something which causes this example to fail:

sage: EllipticCurve("4390c2").gens()[0].elliptic_logarithm()
---------------------------------------------------------------------------
MemoryError                               Traceback (most recent call last)

/home/john/sage-3.2.2.rc1/devel/sage-elllog/<ipython console> in <module>()

/home/john/sage-3.2.2.rc1/local/lib/python2.5/site-packages/sage/schemes/elliptic_curves/ell_point.py in elliptic_logarithm(self, embedding, precision, algorithm)
   1211             E_pari = ER.pari_curve(prec=precision)
   1212             pt_pari = [pari(emb(self[0])), pari(emb(self[1]))]
-> 1213             log_pari = E_pari.ellpointtoz(pt_pari, precision=precision)
   1214             while prec_words_to_bits(log_pari.precision()) < precision:
   1215                 working_prec = 2*precision

/home/john/sage-3.2.2.rc1/local/lib/python2.5/site-packages/sage/libs/pari/gen.so in sage.libs.pari.gen._pari_trap (sage/libs/pari/gen.c:38603)()

/home/john/sage-3.2.2.rc1/local/lib/python2.5/site-packages/sage/libs/pari/gen.so in sage.libs.pari.gen.PariInstance.allocatemem (sage/libs/pari/gen.c:34732)()

/home/john/sage-3.2.2.rc1/local/lib/python2.5/site-packages/sage/libs/pari/gen.so in sage.libs.pari.gen.init_stack (sage/libs/pari/gen.c:37647)()

MemoryError: Unable to allocate 4096000000 bytes memory for PARI.

caused by an infinite loop.

The problem has been diagnosed by me and Alex and I'll post a patch shortly.

Attachments (1)

elllog-2.patch (6.7 KB) - added by cremona 14 years ago.

Download all attachments as: .zip

Change History (4)

Changed 14 years ago by cremona

comment:1 Changed 14 years ago by cremona

  • Summary changed from bug in elliptic logarithm to [with patch, needs review] bug in elliptic logarithm

The infinite loop was fixed by Alex, who then said

We seem to have run into a different problem, though:

sage: E = EllipticCurve("4390c2")
sage: P = E.gens()[0]
sage: P.elliptic_logarithm(precision=64)
0.000256387258865202254
sage: P.elliptic_logarithm(precision=65)
0.0002563872588652022535 + 0.004614954316673684681*I
sage: P.elliptic_logarithm(precision=128)
0.00025638725886520225353198932528666427412 + 0.0046149543166736846806755335569568366865*I
sage: P.elliptic_logarithm(precision=129)
0.00025638725886520225353198932528666427412
sage: P.elliptic_logarithm(precision=256)
0.0002563872588652022535319893252866642741168388008346370015005142128009610936373
sage: P.elliptic_logarithm(precision=257)
0.00025638725886520225353198932528666427411683880083463700150051421280096109363730 + 0.0046149543166736846806755335569568366865361459796795879146958143680521472570409*I

This is quite upsetting.

to which John replied

The explanation is that  0.004614954316673684681*I is the imaginary
period.  the point P is on the identity component so its e-log should
be a real multiple of the real period, but is obviously only
determined up to addition of any period.  Clearly the pari code does
not bother about that.

Here's one fix:  if P.is_on_identity_component(emb) is True then we
know that the result should be real, so we can kill the imaginary
part, and also normalise by making sure that the real part divided by
the real period is in [0,1).  That's not hard.  And if P is not on the
id. component, do the same but set the imaginary part to equal exactly
half the imaginary period.

The attached patch does both. Based on 3.2.2, tested on 32-bit and 64-bit.

comment:2 Changed 14 years ago by AlexGhitza

  • Summary changed from [with patch, needs review] bug in elliptic logarithm to [with patch, positive review] bug in elliptic logarithm

Looks good.

comment:3 Changed 14 years ago by mabshoff

  • Milestone changed from sage-3.4.1 to sage-3.3
  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 3.3.alpha0

Note: See TracTickets for help on using tickets.