Opened 12 years ago

Closed 12 years ago

# Potential bug in elliptic curve pairing code

Reported by: Owned by: was cremona major sage-4.3 elliptic curves elliptic curve sage-4.3.alpha1 John Cremona Robert Bradshaw N/A

### Description

```I think there is a problem in the function

ell_point._line_

which is used in _miller_. I don't know if it will necessarily lead to
incorrect results, since it's a degenerate case...

The method has form

G._line_(R, Q)

and returns the evaluation of Q at the line through G and R.

The problem occurs when Q is the point at infinity. In this case, I'm
thing) that _line_ should return 0 if the line through G and R is
vertical, and otherwise it should be undefined. The method is
returning an answer that assumes that Q is affine.

While I don't have the most recent version (for reasons I won't bore
you with) I've checked the latest code on line, and it appears to not
have changed from what I have.

I've attached a sample session.

---

----------------------------------------------------------------------
| Sage Version 4.0.2, Release Date: 2009-06-18                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: E = EllipticCurve([GF(17)(-1),GF(17)(0)])
sage: G = E.random_point(); G
(7 : 8 : 1)
sage: minus_G = -G; minus_G
(7 : 9 : 1)
sage: G._line_(minus_G, E(0)) # should return 0
10
sage: two_G = 2*G; two_G
(1 : 0 : 1)
sage: G._line_(two_G, E(0)) # should be undefined/error
11
sage:
```

### comment:1 Changed 12 years ago by cremona

The function P._line(R,Q), as documented, returns the value at Q of a suitably normalized function on the curve representing the straight line through P and R, where P and/or R are allowed to be the point O at infinity but Q is not.

The code as written does not work when Q=O, but this is not documented. I suggest a fix whereby if Q==O then a ValueError? is raised -- this is stricter than the remedy suggested, but I think more consistent since in this and similar cases the functions which are being evaluated are all in the polynomial ring k(x,y) of the curve and so should not be evaluated at O where they have poles.

I'm also sure that in the places where this function is used, the condition Q==O does not arise.

I'll make a patch,

John

### Changed 12 years ago by cremona

Applies to 3.1.2.rc0

### comment:2 Changed 12 years ago by cremona

• Authors set to John Cremona
• Owner changed from davidloeffler to cremona
• Summary changed from Potential bug in elliptic curve pairing code. to [with patch, needs review] Potential bug in elliptic curve pairing code.

The patch tests for Q=0 in the functions `_line_` and `_miller_` and raise an error if so. Doctests added.

### comment:3 Changed 12 years ago by robertwb

• Status changed from needs_review to positive_review
• Summary changed from [with patch, needs review] Potential bug in elliptic curve pairing code. to Potential bug in elliptic curve pairing code.

I think that condition is fine, now that it's properly documented.

### comment:4 Changed 12 years ago by mhansen

• Merged in set to sage-4.3.alpha1
• Resolution set to fixed
• Reviewers set to Robert Bradshaw
• Status changed from positive_review to closed

### comment:5 Changed 12 years ago by mvngu

• Report Upstream set to N/A
• Summary changed from Potential bug in elliptic curve pairing code. to Potential bug in elliptic curve pairing code
Note: See TracTickets for help on using tickets.