Opened 13 years ago

Closed 13 years ago

Last modified 13 years ago

#2560 closed defect (duplicate)

serious inefficiency in order of points on elliptic curvews over finite fields

Reported by: cremona Owned by: was
Priority: major Milestone: sage-2.10.4
Component: algebraic geometry Keywords: elliptic curves
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mabshoff)

In sage/elliptic_curves/ in the function EllipticCurvePoint_finite_field.order() a tiny blunder causes a huge inefficiency. The BSGS function is used to find a multiple of the order of the point (when the group order is not yet known), and the existing code

                M = self._bsgs(E(0),0,ub)

should be

                M = self._bsgs(E(0),lb,ub)

since there is a loution in the interval [lb..ub]. This changes the complexity from O(q^1/2) to O(q^1/4).

Change History (3)

comment:1 Changed 13 years ago by cremona

delete - duplicate

comment:2 Changed 13 years ago by mhansen

  • Resolution set to duplicate
  • Status changed from new to closed

Duplicate of #2561

comment:3 Changed 13 years ago by mabshoff

  • Description modified (diff)
Note: See TracTickets for help on using tickets.