Opened 10 years ago
Closed 10 years ago
#10912 closed enhancement (fixed)
add order setters and Tate and ate pairings
Reported by: | mariah | Owned by: | cremona |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.1 |
Component: | elliptic curves | Keywords: | |
Cc: | Merged in: | sage-4.7.1.alpha2 | |
Authors: | Mariah Lenox, Aly Deines | Reviewers: | John Cremona, Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
add order setters and Tate and ate pairings
Apply:
Attachments (8)
Change History (28)
Changed 10 years ago by
comment:1 Changed 10 years ago by
comment:2 Changed 10 years ago by
Response to the two comments:
- 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.
- 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 10 years ago by
- 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 10 years ago by
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.
comment:5 Changed 10 years ago by
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 10 years ago by
It also now uses Hasse_bounds in the group set_order.
comment:7 Changed 10 years ago by
So is this ready for review then?
comment:8 Changed 10 years ago by
- Status changed from needs_work to needs_review
comment:9 Changed 10 years ago by
- Description modified (diff)
comment:10 Changed 10 years ago by
- 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 10 years ago by
- Milestone changed from sage-4.7 to sage-4.7.1
- Reviewers set to John Cremona
comment:12 Changed 10 years ago by
- 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 10 years ago by
comment:13 Changed 10 years ago by
- 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 10 years ago by
- Status changed from needs_review to needs_work
Something is wrong, the new patch is much smaller than the old patch.
Changed 10 years ago by
comment:15 Changed 10 years ago by
- 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.
Changed 10 years ago by
comment:16 Changed 10 years ago by
- 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 10 years ago by
- Work issues documentation formatting deleted
comment:18 Changed 10 years ago by
*bump*
Anyone wants to review my patch?
comment:19 Changed 10 years ago by
- Status changed from needs_review to positive_review
comment:20 Changed 10 years ago by
- Merged in set to sage-4.7.1.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
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: