Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
JohnCremona opened this issue Mar 16, 2008 · 4 comments
Closed

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

JohnCremona opened this issue Mar 16, 2008 · 4 comments
Assignees
@williamstein
Labels
c: algebraic geometry c: elliptic curves p: major / 3 t: bug
Milestone
sage-2.10.4

Comments

@JohnCremona
Copy link
Member

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 lsolution in the interval [lb..ub]. This changes the complexity from O(q^1/2) to O(q^1/4).

Component: algebraic geometry

Issue created by migration from https://trac.sagemath.org/ticket/2561
@JohnCremona JohnCremona added this to the sage-2.10.4 milestone Mar 16, 2008
@JohnCremona
Copy link
Member Author

comment:1

Attachment: 8866.patch.gz

@JohnCremona JohnCremona changed the title serious inefficiency in order of points on elliptic curvews over finite fields [with nano-patch, needs review] serious inefficiency in order of points on elliptic curvews over finite fields Mar 16, 2008
@ncalexan
Copy link
Mannequin

ncalexan mannequin commented Mar 16, 2008

comment:2

Looks fine to me, apply.

@ncalexan ncalexan mannequin changed the title [with nano-patch, needs review] serious inefficiency in order of points on elliptic curvews over finite fields serious inefficiency in order of points on elliptic curvews over finite fields Mar 16, 2008
@ncalexan ncalexan mannequin added the s: positive review label Mar 16, 2008
@sagetrac-mabshoff
Copy link
Mannequin

sagetrac-mabshoff mannequin commented Mar 16, 2008

comment:3

Doctests pass with "-long", so another positive review.

Cheers,

Michael

@sagetrac-mabshoff
Copy link
Mannequin

sagetrac-mabshoff mannequin commented Mar 16, 2008

comment:4

Merged in Sage 2.10.4.final

@sagetrac-mabshoff sagetrac-mabshoff mannequin closed this as completed Mar 16, 2008
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@williamstein williamstein

Labels
c: algebraic geometry c: elliptic curves p: major / 3 t: bug
Projects
None yet
Milestone
sage-2.10.4
Development

No branches or pull requests
2 participants
@williamstein @JohnCremona