#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: |
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)
Change History (6)
comment:1 Changed 12 years ago by
comment:2 Changed 12 years ago by
- 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
- 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
- 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
- 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.
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