Opened 16 years ago

Closed 15 years ago

# optimize elliptic curve arithmetic: 2*P much slower than P+P

Reported by: Owned by: was somebody minor sage-2.8.3 basic arithmetic

### Description

William, my student noticed some slow performance with elliptic curves group law. I think there was a huge overhead in duplication: sage: E = EllipticCurve?([GF(101)(1),3]) sage: P = E([-1,1,1]) sage: timeit 2*P 100 loops, best of 3: 3.81 ms per loop sage: timeit P+P 1000 loops, best of 3: 1.81 ms per loop Basically n*P was passing through all sorts of high-level layers for group schemes, abelian groups, and the like. I've started teaching two courses here, and at the latest, will have to adapt to becoming a Dad next Tuesday (my wife Martine is overdue). But I may be able to add some code in the next three weeks.

### comment:1 Changed 16 years ago by was

This was from David Kohel. Here's a better formated version:

William, my student noticed some slow performance with elliptic curves group law. I think there was a huge overhead in duplication:

```sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
100 loops, best of 3: 3.81 ms per loop
sage: timeit P+P
1000 loops, best of 3: 1.81 ms per loop
```

Basically n*P was passing through all sorts of high-level layers for group schemes, abelian groups, and the like.

### comment:2 Changed 15 years ago by mabshoff

• Milestone set to sage-2.8.3

I guess this has been fixed. With Sage 2.8.2 I get:

```sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
1000 loops, best of 3: 317 µs per loop
sage: timeit P+P
10000 loops, best of 3: 92.7 µs per loop
```

Cheers,

Michael

### comment:3 Changed 15 years ago by was

• Resolution set to fixed
• Status changed from new to closed

### comment:4 Changed 15 years ago by mabshoff

• Resolution fixed deleted
• Status changed from closed to reopened
• Summary changed from optimize elliptic curve arithmetic to optimize elliptic curve arithmetic: 2*P much slower than P+P

Ok, reopened.

To quote David Kohel:

```I think the problem needs to be profiled.  The problem is likely NOT
in elliptic curves, but some
horrendous chain of calls to module operations before getting to the
(same) actual algorithms.
Note that P*2 is slightly faster since it calls directly the member
function of P rather than a
function on integers.

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
1000 loops, best of 3: 309 µs per loop
sage: timeit P+P
10000 loops, best of 3: 89.8 µs per loop
sage: timeit P*2
1000 loops, best of 3: 204 µs per loop

Yes, reopen it: these sorts of problems need to be looked at and
optimized.  The same problem
applies to points on Jacobians (compare 2*P, P*2, and P+P).

--David
```

### comment:5 Changed 15 years ago by was

• Resolution set to fixed
• Status changed from reopened to closed

As of SAGE-2.8.3 (probably due to Tom Boothby's work), this is now resolved:

```sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: import timeit
sage: t = timeit.Timer('2*P', 'from sage.all import EllipticCurve, GF; E = EllipticCurve([GF(101)(1),3]); P = E([-1,1,1])')
sage: t.timeit(10000)
1.0524919033050537
sage: s = timeit.Timer('P+P', 'from sage.all import EllipticCurve, GF; E = EllipticCurve([GF(101)(1),3]); P = E([-1,1,1])')
sage: s.timeit(10000)
1.067209005355835
```
Note: See TracTickets for help on using tickets.