#15667: Time anomaly in finding orders of points on an elliptic curve over a
finite
field
------------------------------+--------------------------------------------
Reporter: cremona | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.1
Component: elliptic | Keywords: point order finite field
curves | Authors:
Merged in: | Report Upstream: N/A
Reviewers: | Branch:
Work issues: | Dependencies:
Commit: |
Stopgaps: |
------------------------------+--------------------------------------------
See https://groups.google.com/forum/#!searchin/sage-
support/anomaly|sort:relevance|spell:true/sage-support/PzrQ6kUzSJg/m99x
--9TS-oJ
The upshot is that when computing the order of a point on an elliptic
curve whose cardinality has not yet been computed, there are cases where
that cardinality could be computed very quickly first, which would be much
faster than using BSGS methods for the order. Specifically, this is the
case for curves with j-invariants 0 and 1728 over any finite field.
From the mailing list contribution by Victor Miller:
Consider the following:
{{{
def NextProgression(n,a,q):
p = next_prime(n)
while (p%q) != a:
p = next_prime(p+1)
return p
}}}
{{{
def Test(n,compute=False):
p = NextProgression(n,2,3)
print "found prime=",p
F.<u> = GF(p^2)
print "Found field"
E = EllipticCurve(F,[0,1])
if compute:
NN = E.order()
print "Found Elliptic Curve of order ",NN
P = E.random_point()
Q = E.random_point()
print "Found points"
nP = P.order()
print "Found order of P"
nQ = Q.order()
print "Found order of Q"
N = lcm(nP,nQ)
return E,P,Q,N
}}}
{{{
time E,P,Q,n = Test(2^25)
found prime= 33554501
Found field
Found points
Found order of P
Found order of Q
Time: CPU 10.52 s, Wall: 10.77 s
}}}
compared with
{{{
time E,P,Q,n = Test(2^25,compute=True)
found prime= 33554501
Found field
Found Elliptic Curve of order 1125904604468004
Found points
Found order of P
Found order of Q
Time: CPU 0.17 s, Wall: 0.18 s
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/15667>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
