Sage: Ticket #7116: Potential bug in elliptic curve pairing code
https://trac.sagemath.org/ticket/7116
<pre class="wiki">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:
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/7116
Trac 1.1.6cremonaSun, 04 Oct 2009 20:10:19 GMT
https://trac.sagemath.org/ticket/7116#comment:1
https://trac.sagemath.org/ticket/7116#comment:1
<p>
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.
</p>
<p>
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 <a class="missing wiki">ValueError?</a> 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.
</p>
<p>
I'm also sure that in the places where this function is used, the condition Q==O does not arise.
</p>
<p>
I'll make a patch,
</p>
<p>
John
</p>
TicketcremonaSun, 04 Oct 2009 20:24:00 GMTattachment set
https://trac.sagemath.org/ticket/7116
https://trac.sagemath.org/ticket/7116
<ul>
<li><strong>attachment</strong>
set to <em>trac_7116-miller_functions.patch</em>
</li>
</ul>
<p>
Applies to 3.1.2.rc0
</p>
TicketcremonaSun, 04 Oct 2009 20:25:51 GMTowner, summary changed; keywords, author set
https://trac.sagemath.org/ticket/7116#comment:2
https://trac.sagemath.org/ticket/7116#comment:2
<ul>
<li><strong>owner</strong>
changed from <em>davidloeffler</em> to <em>cremona</em>
</li>
<li><strong>keywords</strong>
<em>elliptic</em> <em>curve</em> added
</li>
<li><strong>summary</strong>
changed from <em>Potential bug in elliptic curve pairing code.</em> to <em>[with patch, needs review] Potential bug in elliptic curve pairing code.</em>
</li>
<li><strong>author</strong>
set to <em>John Cremona</em>
</li>
</ul>
<p>
The patch tests for Q=0 in the functions <code>_line_</code> and <code>_miller_</code> and raise an error if so. Doctests added.
</p>
TicketrobertwbFri, 20 Nov 2009 05:34:37 GMTstatus, summary changed
https://trac.sagemath.org/ticket/7116#comment:3
https://trac.sagemath.org/ticket/7116#comment:3
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>summary</strong>
changed from <em>[with patch, needs review] Potential bug in elliptic curve pairing code.</em> to <em>Potential bug in elliptic curve pairing code.</em>
</li>
</ul>
<p>
I think that condition is fine, now that it's properly documented.
</p>
TicketmhansenSun, 22 Nov 2009 07:36:08 GMTstatus changed; reviewer, resolution, merged set
https://trac.sagemath.org/ticket/7116#comment:4
https://trac.sagemath.org/ticket/7116#comment:4
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>reviewer</strong>
set to <em>Robert Bradshaw</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-4.3.alpha1</em>
</li>
</ul>
TicketmvnguSat, 26 Dec 2009 17:58:34 GMTsummary changed; upstream set
https://trac.sagemath.org/ticket/7116#comment:5
https://trac.sagemath.org/ticket/7116#comment:5
<ul>
<li><strong>upstream</strong>
set to <em>N/A</em>
</li>
<li><strong>summary</strong>
changed from <em>Potential bug in elliptic curve pairing code.</em> to <em>Potential bug in elliptic curve pairing code</em>
</li>
</ul>
Ticket