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:

Status badges

Description (last modified by jdemeyer)

add order setters and Tate and ate pairings

Apply:

Attachments (8)

10912.patch (32.2 KB) - added by mariah 10 years ago.
Trac10912.patch (32.5 KB) - added by aly.deines 10 years ago.
This fixed the bug in tate_pairing.
trac_10912-ate.patch (32.5 KB) - added by cremona 10 years ago.
Reviewer patch: applies to 4.7.alpha5
trac_10912-ate.p2.patch (6.5 KB) - added by mariah 10 years ago.
trac_10912-ate.p2.diff (842 bytes) - added by mariah 10 years ago.
diff for review purposes only
trac_10912-ate.p3.patch (32.4 KB) - added by mariah 10 years ago.
trac_10912-ate.p3.diff (2.9 KB) - added by mariah 10 years ago.
diff for review purposes only
10912_doc_reviewer.patch (6.3 KB) - added by jdemeyer 10 years ago.

Download all attachments as: .zip

Change History (28)

Changed 10 years ago by mariah

comment:1 Changed 10 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.

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?
  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 10 years ago by mariah

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.
  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 10 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 10 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 10 years ago by aly.deines

This fixed the bug in tate_pairing.

comment:5 Changed 10 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 10 years ago by aly.deines

It also now uses Hasse_bounds in the group set_order.

comment:7 Changed 10 years ago by robertwb

So is this ready for review then?

comment:8 Changed 10 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 10 years ago by mariah

  • Description modified (diff)

Changed 10 years ago by cremona

Reviewer patch: applies to 4.7.alpha5

comment:10 Changed 10 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 10 years ago by jdemeyer

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

comment:12 Changed 10 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 10 years ago by mariah

Changed 10 years ago by mariah

diff for review purposes only

comment:13 Changed 10 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 10 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 10 years ago by mariah

Changed 10 years ago by mariah

diff for review purposes only

comment:15 Changed 10 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.

Changed 10 years ago by jdemeyer

comment:16 Changed 10 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 10 years ago by jdemeyer

  • Work issues documentation formatting deleted

comment:18 Changed 10 years ago by jdemeyer

*bump*

Anyone wants to review my patch?

comment:19 Changed 10 years ago by cremona

  • Status changed from needs_review to positive_review

comment:20 Changed 10 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.