Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#7116 closed defect (fixed)

Potential bug in elliptic curve pairing code

Reported by: was Owned by: cremona
Priority: major Milestone: sage-4.3
Component: elliptic curves Keywords: elliptic curve
Cc: Merged in: sage-4.3.alpha1
Authors: John Cremona Reviewers: Robert Bradshaw
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

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
pretty sure (it's been a while since I've thought about this kind of
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:

Attachments (1)

trac_7116-miller_functions.patch (2.4 KB) - added by cremona 12 years ago.
Applies to 3.1.2.rc0

Download all attachments as: .zip

Change History (6)

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
  • Keywords elliptic curve added
  • 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.