add order setters and Tate and ate pairings

[sagetrac-mariah]

add order setters and Tate and ate pairings

Apply:

• attachment: trac_10912-ate.p3.patch
• attachment: 10912_doc_reviewer.patch

Component: elliptic curves

Author: Mariah Lenox, Aly Deines

Reviewer: John Cremona, Jeroen Demeyer

Merged: sage-4.7.1.alpha2

Issue created by migration from https://trac.sagemath.org/ticket/10912

[sagetrac-mariah]

Attachment: 10912.patch.gz

[JohnCremona]

comment:1

Excellent work. I'll need some time to go through the Tate and Ate pairing code; if no-one gets to it first this is something to do at SD29 in 10 days' time.

Until then, just two comments:

1. You use the hasse_bounds function in the opint order-setting function, but why not also in the groupcorder setting function?

2. Amusing fact: for fields of size at least 32 there cannot be two integers in the Hasse interval with one dividing the other (since the ratio of the upper and lower bounds is < 2)!

[sagetrac-mariah]

comment:2

Response to the two comments:

1. Yes, by all means I should have used the hasse_bounds function in the group order setter, I discovered it in the course of writing the point order setter, and then forgot to go back and change it.

2. A fine fact indeed! One could use it to make the group order setter more robust. It may well be worth having the both order setters defer to the builtin order calculation in small cases, perhaps with an override message?

[adeines]

comment:3

When I tried timing the first example in the tate_pairing, I got the following error:

p = 103; A = 1; B = 18; E = EllipticCurve(GF(p), [A, B])
P = E(33, 91); n = P.order()
k = GF(n)(p).multiplicative_order()
timeit('P.tate_pairing(P, n, k)')

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_3.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cCA9IDEwMzsgQSA9IDE7IEIgPSAxODsgRSA9IEVsbGlwdGljQ3VydmUoR0YocCksIFtBLCBCXSkKUCA9IEUoMzMsIDkxKTsgbiA9IFAub3JkZXIoKQprID0gR0YobikocCkubXVsdGlwbGljYXRpdmVfb3JkZXIoKQp0aW1laXQoJ1AudGF0ZV9wYWlyaW5nKFAsIG4sIGspJyk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/l5/l55HHC6uExG+F0kEqsPAgU+++TM/-Tmp-/tmp45b1A1/___code___.py", line 6, in <module>
    exec compile(u"timeit('P.tate_pairing(P, n, k)')" + '\n', '', 'single')
  File "", line 1, in <module>
    
  File "sage_timeit_class.pyx", line 82, in sage.misc.sage_timeit_class.SageTimeit.__call__ (sage/misc/sage_timeit_class.c:744)
  File "sage_timeit_class.pyx", line 59, in sage.misc.sage_timeit_class.SageTimeit.eval (sage/misc/sage_timeit_class.c:605)
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/misc/sage_timeit.py", line 181, in sage_timeit
    if timer.timeit(number) >= 0.2:
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python/timeit.py", line 193, in timeit
    timing = self.inner(it, self.timer)
  File "<magic-timeit>", line 6, in inner
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1751, in tate_pairing
    ret = self.tate_pairing(Q + R, n, k)/self.tate_pairing(R, n, k)
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1746, in tate_pairing
    ret = self._miller_(Q, n)
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1446, in _miller_
    raise ValueError, "Q must be nonzero."
ValueError: Q must be nonzero.

Whereas without the timing everthing is fine:

p = 103; A = 1; B = 18; E = EllipticCurve(GF(p), [A, B])
P = E(33, 91); n = P.order()
k = GF(n)(p).multiplicative_order()
P.tate_pairing(P, n, k)
1

[adeines]

comment:4

Ok, I can be more specific in what the error is. In tate_pairing (P.tate_pairing(Q,n,k)), if P.miller(Q, n) raises a
ZeroDivisionError: Inverse does not exist., then it creates a random point R and then calles P.tate_pairing(Q+R,n,k).
If Q+R is zero, then P.miller(Q+R,n,k) raises an error. This is not checked for and it seems that given certain
random seeds this does occur.

p = 103; A = 1; B = 18; E = EllipticCurve(GF(p), [A, B])
P = E(33, 91); n = P.order()
k = GF(n)(p).multiplicative_order()
set_random_seed(15)
P.tate_pairing(P,n,k)

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_10.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("cCA9IDEwMzsgQSA9IDE7IEIgPSAxODsgRSA9IEVsbGlwdGljQ3VydmUoR0YocCksIFtBLCBCXSkKUCA9IEUoMzMsIDkxKTsgbiA9IFAub3JkZXIoKQprID0gR0YobikocCkubXVsdGlwbGljYXRpdmVfb3JkZXIoKQpzZXRfcmFuZG9tX3NlZWQoMTUpClAudGF0ZV9wYWlyaW5nKFAsbixrKQ=="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/private/var/folders/l5/l55HHC6uExG+F0kEqsPAgU+++TM/-Tmp-/tmpjVE30I/___code___.py", line 7, in <module>
    exec compile(u'P.tate_pairing(P,n,k)
  File "", line 1, in <module>
    
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1751, in tate_pairing
    ret = self.tate_pairing(Q + R, n, k)/self.tate_pairing(R, n, k)
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1746, in tate_pairing
    ret = self._miller_(Q, n)
  File "/Users/aly/Desktop/sage-4.7.alpha2/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py", line 1446, in _miller_
    raise ValueError, "Q must be nonzero."
ValueError: Q must be nonzero.

[adeines]

Attachment: Trac10912.patch.gz

This fixed the bug in tate_pairing.

[adeines]

comment:5

I posted a patch which replaces the original. It fixes the bug found in tate_pairing. So far it doesn't do anything to make the group order setting more robust.

[adeines]

comment:6

It also now uses Hasse_bounds in the group set_order.

[robertwb]

comment:7

So is this ready for review then?

[sagetrac-mariah]

Changed author from Mariah Lenox to Mariah Lenox, Aly Deines

[JohnCremona]

Attachment: trac_10912-ate.patch.gz

Reviewer patch: applies to 4.7.alpha5

[JohnCremona]

comment:10

Looks fine to me, and all tests in elliptic)curves pass. Very nice job with excellent tests and examples.

My patch replaces the previous ones; it just corrected a couple of minor typos in the docstrings.

Positive review!

[jdemeyer]

Reviewer: John Cremona

[jdemeyer]

Work Issues: documentation formatting

[jdemeyer]

comment:12

There are some issues with the formatting of the documentation:

dochtml.log:/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.1.alpha1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py:docstring of sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.ate_pairing:169: (WARNING/2) Explicit markup ends without a blank line; unexpected unindent.
dochtml.log:/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.1.alpha1/local/lib/python2.6/site-packages/sage/schemes/elliptic_curves/ell_point.py:docstring of sage.schemes.elliptic_curves.ell_point.EllipticCurvePoint_field.tate_pairing:27: (WARNING/2) Literal block expected; none found.

The INPUT and OUTPUT blocks should not be indented, see http://sagemath.org/doc/developer/conventions.html#docstring-markup-with-rest-and-sphinx

[sagetrac-mariah]

Attachment: trac_10912-ate.p2.patch.gz

diff for review purposes only

[sagetrac-mariah]

comment:13

Attachment: trac_10912-ate.p2.diff.gz

Attachment attachment: trac_10912-ate.p2.patch makes the INPUT and OUTPUT blocks not be indented. Nothing else was changed from attachment [attachment: trac_10912-ate.patch].

[jdemeyer]

comment:14

Something is wrong, the new patch is much smaller than the old patch.

[sagetrac-mariah]

Attachment: trac_10912-ate.p3.patch.gz

[sagetrac-mariah]

diff for review purposes only

[sagetrac-mariah]

comment:15

Attachment: trac_10912-ate.p3.diff.gz

Oops! Forgot a file. Apologies.

Attachment [attachment: trac_10912-ate.p3.diff] is a diff of
[attachment: trac_10912-ate.patch] and [attachment: trac_10912-ate.p3.patch].

[jdemeyer]

comment:16

Attachment: 10912_doc_reviewer.patch.gz

Positive review to the documentation changes. Somebody still needs to review my reviewer patch.

[jdemeyer]

Changed reviewer from John Cremona to John Cremona, Jeroen Demeyer

[jdemeyer]

Changed work issues from documentation formatting to none

[jdemeyer]

comment:18

bump

Anyone wants to review my patch?

[jdemeyer]

Merged: sage-4.7.1.alpha2