Slow Computations in Quotient Rings

[finotti]

A student of mine is trying to use Sage to prove the commutativity of the group law of elliptic curves.  Below is the code used when trying to show (P + Q) + R = P + (Q + R), when R = P + Q.  I let it run for almost 4 hours with no result.  The same code translated to Magma was instantaneous.  Am I doing something wrong with Sage?  Or is just that the implementation in Magma is more efficient?  (We can use Magma, but it made me curious.)

def add_EC(vE, P, Q):

    if P == 0:

        return Q

    if Q == 0:

        return P

    a = vE[0]

    b = vE[1]

    x1 = P[0]

    y1 = P[1]

    x2 = Q[0]

    y2 = Q[1]

    if P == Q:

        if y1 == 0:

            return 0

        else:

            m = (3*x1^2 + a)/(2*y1)

    else:

        if x1 == x2:

            return 0

        else:

            m = (y2 - y1)/(x2 - x1)

    c = y1 - m*x1

    x3 = m^2 - x1 - x2

    y3 = m*x3 + c

    return [x3, -y3]

R.<A, B, a, b, c, d> = PolynomialRing(QQ)

eq1 = b^2 - a^3 - A*a - B

eq2 = d^2 - c^3 - A*c - B

S = R.quo([eq1, eq2])

F = FractionField(S)

vE = [F(A), F(B)]

P = [F(a), F(b)]

Q = [F(c), F(d)]

R = add_EC(vE, P, Q)

LHS = add_EC(vE, add_EC(vE, P, Q), R)

RHS = add_EC(vE, P, add_EC(vE, Q, R))

LHS == RHS

[rana-aere]

I modified the code and tried to trace computation.

I think you stepped over the weakness of Sagemath.

The modified code is quoted below.

The line with many minus signs is meant to separate the program in different cells of jupyter notebook.

My impression is that the program computes R, P + Q, LHS = (P + Q) + R and then Q + R for RHS.

After that the data for the outer call of P + (Q + R) becomes too big so that Sagemath cannot pass the parameters to add_EC.

I introduced local variable myA. This should represent A instead of the coordinate a of P.

Please verify the output.

```

def add_EC(vE, P, Q):

    print("add_EC is called with");

    print("P = ", P);

    print("Q = ", Q);

    if P == 0:

        print("P == 0, returning Q");

        return Q

    print("P != 0");

    if Q == 0:

        print("Q == 0, returning P");

        return P

    print("Q != 0");

    # avoid confusion of a of elliptic curve with a of P.

    myA = vE[0]

    # I gues we are not using b of the equation.

    # myB = vE[1]

    x1 = P[0]

    y1 = P[1]

    x2 = Q[0]

    y2 = Q[1]

    print("Copied actual parameters in local variables");

    if P == Q:

        print("P==Q");

        if y1 == 0:

            print("y1 == 0, returning 0");

            return 0

        else:

            print("y1 != 0, comuting m");

            m = (3*x1^2 + myA)/(2*y1)

        print("P==Q && y1 != 0");

    else:

        print("P != Q");

        if x1 == x2:

            print("x1 == x2, returning 0");

            return 0

        else:

            print("x1 != x2, computing m");

            m = (y2 - y1)/(x2 - x1)

        print("P!=Q && x1!=x2");

    print("Main case: intermediate variable m already computed");

    print("m = ", m);

    c = y1 - m*x1

    print("c = ", c);

    x3 = m^2 - x1 - x2

    print("x3 = ", x3);

    y3 = m*x3 + c

    print("y3= ", y3);

    return [x3, -y3]

#----------------------------------------------------------------------------------

R.<A, B, a, b, c, d> = PolynomialRing(QQ)

eq1 = b^2 - a^3 - A*a - B

eq2 = d^2 - c^3 - A*c - B

S = R.quo([eq1, eq2])

F = FractionField(S)

vE = [F(A), F(B)]

P  = [F(a), F(b)]

Q  = [F(c), F(d)]

#----------------------------------------------------------------------------------

R = add_EC(vE, P, Q)

#----------------------------------------------------------------------------------

R

#----------------------------------------------------------------------------------

LHS = add_EC(vE, add_EC(vE, P, Q), R)

#----------------------------------------------------------------------------------

LHS

#----------------------------------------------------------------------------------

# Sagemath cannot handle the next step.

# Make sure you are ready to terminate Sagemath,

# before uncommenting the next line.

# RHS = add_EC(vE, P, add_EC(vE, Q, R))

#----------------------------------------------------------------------------------

# RHS

#----------------------------------------------------------------------------------

# LHS==RHS

```

[finotti]

Thanks for the reply!

On Saturday, April 4, 2020 at 1:00:12 PM UTC-4, rana-aere wrote:

I modified the code and tried to trace computation.

I think you stepped over the weakness of Sagemath.

I was afraid that that would be the case...

 

The modified code is quoted below.

The line with many minus signs is meant to separate the program in different cells of jupyter notebook.

My impression is that the program computes R, P + Q, LHS = (P + Q) + R and then Q + R for RHS.

After that the data for the outer call of P + (Q + R) becomes too big so that Sagemath cannot pass the parameters to add_EC.

Thanks for taking the time to do that! I really appreciate.  I wonder if this is an issue that I should report or if it simply "how it is"...

I think we will just stick with Magma for now.  I try to use (and teach with) Sage whenever possible, but in this case I think I will have to stick with Magma.

Thanks again!

[rana-aere]

I think it is an issue to be reported.

So, I wait for someone to respond this question.

To developers of the SageMath module of rings:

Please verify the program in this question, with debugging messages I added.

we ran into a weakness of SageMath either

 in formula processing producing too complicated denominators

 or in SageMath module of quotient of rings, which fail to reduce the element of the ring.

I believe the code reported here is an important entry for new students to SageMath.

Please program what is going for this program.

2020年4月5日日曜日 5時56分25秒 UTC+9 finotti:

[Vincent Delecroix]

Dear rana-aere,

If you think this is an issue, then *you* should be working on it.
Every SageMath developers is a volunteer that does not take orders
and think by herself or himself what is relevant to do. Note that
helping others is indeed a concern for most of them.

As a start:

- you can check whether there is already an existing ticket
on https://trac.sagemath.org/ for this problem, and if not
open one which tracks down the problem to its essence (for
example it has nothing to do with elliptic curves).

- If you have a *concrete suggestion* in favor of an improvement
but does not know how to implement it, this could be discussed
on the sage-devel mailing list.

SageMath developers are mature enough to read the messages on this
list and figure out what is relevant to do without your call.

Best
Vincent

[rana-aere]

Dear Vincent ,

I am tempted to do so.

But, for now, I must focus on trouble of Sagemath start-up in MacOS.

I have fixed a trick of Sagemath (double click) hands over the ticket to the browser.

At the same time, I fixed some part of the trouble of error messages truncated.

I have an idea on some other problem with getcwd.

I have an idea on fixing problematic validation on MacOS HighSierra--Mojave--Catalina.

---- This turned out much more difficult than I expected.

I must also fix deprecation warnings, which makes us hard to consult new users installing Sagemath.

---- Most of this turns out upstream problem so I must find a way to reproduce warnings.

I accept to work on the ring but please allow me to be very slow.

In any event I take your welcome message.

Thank you. 

2020年4月7日火曜日 2時09分21秒 UTC+9 vdelecroix: