Time anomaly in finding orders of points on an elliptic curve over a finite field

[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

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

I understand that knowing the order of E is necessary to find the order of points, but why should forcing the order of E to be computed first make it almost 60 times faster?

Victor

This was on sage 5.11 on my macbook

[John Cremona]

I should be able to answer this having written the underlying code (a few years ago though).  

Finding the group order will involve finding orders of random points.  If the group is cyclic (I did not check) then it will quickly obtain that information and then finding the orders of any other points will be easy.  In that case it is quite possible that when you find the order of a random point you will find that it lies in the Hasse interval and hence the group is cyclic, in which case the group order is cached even though it was not asked for, to speed up finding the order of subsequent points.

If not cyclic, then no random point will be a generator so finding the order of one point will not cause any info to be cached to help finding the orders of more points, while if you actually ask for the group order -- which will in this case be harder and involve some Weil pairings, etc -- then finding point orders after that will be faster.

I think what this means is that as soon as you find the order of a point on a curve whose group order has not yet been computed and cached, that information should be cached.

I hope this makes some sense!

John

--
You received this message because you are subscribed to the Google Groups "sage-support" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-support...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/groups/opt_out.

[Victor Miller]

John, Thanks.  No, actually the curves are supersingular over GF(p^2) so the group is always the product of two cyclic groups of the same order (as far from cyclic as you can be).  I guessed that once I calculated the group order, it was cached, and then it was attempted to be factored (which, in this case was easy), and then you're home free.

Victor

[Victor Miller]

I haven't looked at the code, but does "finding the order of random points" use baby step giant step, or some sort of version of Pollard rho or lambda?

Victor

On Thursday, August 15, 2013 10:20:49 AM UTC-7, John Cremona wrote:

[John Cremona]

I know what it is -- I had not looked at the specific curve when I first answered.  Your curve has j-invariant 0, and when j=0 or 1728 the cardinality of the group is computed using the formula (taking into account twists of course) so is instantaneous.  But the finding of orders of points will use BSGS (there is a Pollard rho method too, implemented by someone else).

So this is wirth at least one patch:  when computing the order of a point it does check to see if the group order is already known, and makes use of that if it is, otherwise uses BSGS taking into account the Hasse interval to find a multiple of the point order which lies in that interval, which it then factors.  (You can fill in further details for yourself, or look at the source code).   The easy patch would be that if the group order is not known yet but j=0 or 1728 then the group order should be computed right then, since it is easy.

A more general improvement would be to enlarge the set of j-invariants for which the group order was computed by formula, say to include the other class number 1 j-invariants.  A project for someone!

Victor, feel free to open a ticket with my first suggestion, which would be very easy to implement.

John

On 15 August 2013 02:24, Victor Miller <victor...@gmail.com> wrote:

[Victor Miller]

John, Now I understand.  I will open a ticket.  I'd suggest that we add a new private method which will look at the curve and return True if it's one that has a fast method for computing the order.   I haven't looked, but is there sage code to compute Hecke characters, which is what's necessary to deal with curves with CM with small discriminants?

Victor

[John Cremona]

On 19 August 2013 01:29, Victor Miller <victor...@gmail.com> wrote:

John, Now I understand.  I will open a ticket.  I'd suggest that we add a new private method which will look at the curve and return True if it's one that has a fast method for computing the order.   I haven't looked, but is there sage code to compute Hecke characters, which is what's necessary to deal with curves with CM with small discriminants?

I think not.   Let's keep the first ticket limited to the cases j=0, 1728 which will be very easy, and have a second ticket for the larger task of dealing with other small discriminants.

John

[John Cremona]

On 19 August 2013 08:59, John Cremona <john.c...@gmail.com> wrote:

On 19 August 2013 01:29, Victor Miller <victor...@gmail.com> wrote:

John, Now I understand.  I will open a ticket.  I'd suggest that we add a new private method which will look at the curve and return True if it's one that has a fast method for computing the order.   I haven't looked, but is there sage code to compute Hecke characters, which is what's necessary to deal with curves with CM with small discriminants?

I think not.   Let's keep the first ticket limited to the cases j=0, 1728 which will be very easy, and have a second ticket for the larger task of dealing with other small discriminants.

Victor, did you make a ticket?  I could not find it.

 

John

[John Cremona]

On 12 January 2014 16:18, John Cremona <john.c...@gmail.com> wrote:

On 19 August 2013 08:59, John Cremona <john.c...@gmail.com> wrote:

On 19 August 2013 01:29, Victor Miller <victor...@gmail.com> wrote:

John, Now I understand.  I will open a ticket.  I'd suggest that we add a new private method which will look at the curve and return True if it's one that has a fast method for computing the order.   I haven't looked, but is there sage code to compute Hecke characters, which is what's necessary to deal with curves with CM with small discriminants?

I think not.   Let's keep the first ticket limited to the cases j=0, 1728 which will be very easy, and have a second ticket for the larger task of dealing with other small discriminants.

Victor, did you make a ticket?  I could not find it.

 

It is now #15667, i.e.  http://trac.sagemath.org/ticket/15667 and I'll do it.

John