id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
7116 Potential bug in elliptic curve pairing code was cremona "{{{
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:
}}}" defect closed major sage-4.3 elliptic curves fixed elliptic curve sage-4.3.alpha1 John Cremona Robert Bradshaw N/A