#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: |
Description (last modified by )
In sage/elliptic_curves/sll_points.py 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
comment:2 Changed 13 years ago by
- Resolution set to duplicate
- Status changed from new to closed
Duplicate of #2561
comment:3 Changed 13 years ago by
- Description modified (diff)
Note: See
TracTickets for help on using
tickets.
delete - duplicate