Opened 11 years ago

Closed 11 years ago

# add order setters and Tate and ate pairings

Reported by: Owned by: mariah cremona major sage-4.7.1 elliptic curves sage-4.7.1.alpha2 Mariah Lenox, Aly Deines John Cremona, Jeroen Demeyer N/A

add order setters and Tate and ate pairings

Apply:

### comment:1 Changed 11 years ago by cremona

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.

1. You use the hasse_bounds function in the opint order-setting function, but why not also in the groupcorder setting function?
1. 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)!

### comment:2 Changed 11 years ago by mariah

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.
1. 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?

### comment:3 Changed 11 years ago by aly.deines

• Status changed from new to needs_work

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

```

### comment:4 Changed 11 years ago by aly.deines

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.

```

### Changed 11 years ago by aly.deines

This fixed the bug in tate_pairing.

### comment:5 Changed 11 years ago by aly.deines

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.

### comment:6 Changed 11 years ago by aly.deines

It also now uses Hasse_bounds in the group set_order.

### comment:7 Changed 11 years ago by robertwb

So is this ready for review then?

### comment:8 Changed 11 years ago by mariah

• Authors changed from Mariah Lenox to Mariah Lenox, Aly Deines
• Status changed from needs_work to needs_review

### comment:9 Changed 11 years ago by mariah

• Description modified (diff)

### Changed 11 years ago by cremona

Reviewer patch: applies to 4.7.alpha5

### comment:10 Changed 11 years ago by cremona

• Description modified (diff)
• Status changed from needs_review to positive_review

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!

### comment:11 Changed 11 years ago by jdemeyer

• Milestone changed from sage-4.7 to sage-4.7.1
• Reviewers set to John Cremona

### comment:12 Changed 11 years ago by jdemeyer

• Status changed from positive_review to needs_work
• Work issues set to documentation formatting

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

### Changed 11 years ago by mariah

diff for review purposes only

### comment:13 Changed 11 years ago by mariah

• Description modified (diff)
• Status changed from needs_work to needs_review

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

### comment:14 Changed 11 years ago by jdemeyer

• Status changed from needs_review to needs_work

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

### Changed 11 years ago by mariah

diff for review purposes only

### comment:15 Changed 11 years ago by mariah

• Description modified (diff)
• Status changed from needs_work to needs_review

Oops! Forgot a file. Apologies.

Attachment trac_10912-ate.p3.diff is a diff of trac_10912-ate.patch and trac_10912-ate.p3.patch.

### comment:16 Changed 11 years ago by jdemeyer

• Description modified (diff)
• Reviewers changed from John Cremona to John Cremona, Jeroen Demeyer

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

### comment:17 Changed 11 years ago by jdemeyer

• Work issues documentation formatting deleted

### comment:18 Changed 11 years ago by jdemeyer

*bump*

Anyone wants to review my patch?

### comment:19 Changed 11 years ago by cremona

• Status changed from needs_review to positive_review

### comment:20 Changed 11 years ago by jdemeyer

• Merged in set to sage-4.7.1.alpha2
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.