Opened 4 years ago
Closed 4 years ago
#24640 closed enhancement (fixed)
Avoid order computation in EllipticCurveIsogeny function
Reported by:  m3vandyk  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  elliptic curves  Keywords:  elliptic curve, isogeny 
Cc:  Merged in:  
Authors:  Madison Van Dyk; David Jao  Reviewers:  Kevin Lui 
Report Upstream:  N/A  Work issues:  
Branch:  926ff9b (Commits, GitHub, GitLab)  Commit:  926ff9b5a81a114433221c2ac9e9d4be6e70d0d9 
Dependencies:  Stopgaps: 
Description
When computing the points in the kernel set of the isogeny, it is unnecessary and slow to perform the computation of P.order(): slow because computing the order requires factoring the order of E in many cases, and unnecessary because the preceding code block checks that P has finite order, and in the finite order case we can just compute all multiples of P until we get the identity since we need to compute all of these points anyway in order to list the kernel set. For curves of cryptographic size and kernels of small order, we have measured that eliminating the P.order() computation makes the EllipticCurveIsogeny? function run 200 times faster.
I (David) discussed this problem with William Stein and Kevin Lui at JMM 2017, and Kevin identified the source of the problem, but seems to have never checked in a fix.
Change History (21)
comment:1 Changed 4 years ago by
 Branch set to u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function
comment:2 Changed 4 years ago by
 Commit set to 0a674fd488dcd7cb779101d263c10a874a13cf77
comment:3 Changed 4 years ago by
 Commit changed from 0a674fd488dcd7cb779101d263c10a874a13cf77 to b9ababe78120a3104d2ddb53e481bac66106ca40
Branch pushed to git repo; I updated commit sha1. New commits:
b9ababe  update Isogeny function to address slow order calcuaiton

comment:4 Changed 4 years ago by
Can you add an example demonstrating the speedup?
comment:5 Changed 4 years ago by
 Commit changed from b9ababe78120a3104d2ddb53e481bac66106ca40 to b461d389b5df0c982ac94778f33686673951172d
Branch pushed to git repo; I updated commit sha1. New commits:
b461d38  Add doctest for orderfree isogeny computation

comment:6 Changed 4 years ago by
We added a doctest demonstrating the speedup. The test takes around a minute; we can try to think of ways to make it faster. Without our changes, the same test takes practically forever.
comment:7 Changed 4 years ago by
 Branch changed from u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function to u/klui/avoid_order_computation_in_ellipticcurveisogeny_function
comment:8 Changed 4 years ago by
 Commit changed from b461d389b5df0c982ac94778f33686673951172d to 250f15ab7d9f3c8759afe55f687ecc5e49d8fb32
I changed a few small things:
1) Fixed a line in doctest so that it works with sphnix.
2) Removed the multiples import and removed list.
Is there a smaller example? The current one take me about 75s
sage t warnlong ell_curve_isogeny.py ********************************************************************** File "ell_curve_isogeny.py", line 726, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny Warning, slow doctest: phi_v = EllipticCurveIsogeny(EK, P_list); phi_v Test ran for 1.72 s ********************************************************************** File "ell_curve_isogeny.py", line 838, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny Warning, slow doctest: iso2 = EL.isogenies_prime_degree(2); len(iso2) Test ran for 7.27 s ********************************************************************** File "ell_curve_isogeny.py", line 840, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny Warning, slow doctest: iso3 = EL.isogenies_prime_degree(3); len(iso3) Test ran for 9.97 s ********************************************************************** File "ell_curve_isogeny.py", line 852, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny Warning, slow doctest: duals = [phi.dual() for phi in isogs] Test ran for 1.46 s ********************************************************************** File "ell_curve_isogeny.py", line 1860, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny.__init_from_kernel_list Warning, slow doctest: p=12*next_prime(2**516)*next_prime(2**543)1 Test ran for 1.31 s ********************************************************************** File "ell_curve_isogeny.py", line 1861, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny.__init_from_kernel_list Warning, slow doctest: E=EllipticCurve([GF(p)(1),GF(p)(0)]) Test ran for 11.81 s ********************************************************************** File "ell_curve_isogeny.py", line 1862, in sage.schemes.elliptic_curves.ell_curve_isogeny.EllipticCurveIsogeny.__init_from_kernel_list Warning, slow doctest: P=E(0).division_points(3)[1] Test ran for 15.41 s [986 tests, 60.69 s]  All tests passed!  Total time for all tests: 60.9 seconds cpu time: 54.9 seconds cumulative wall time: 60.7 seconds
New commits:
250f15a  fixed documentation, removed an import that's not longer needed, removed a list function

comment:9 Changed 4 years ago by
Thanks Kevin! Here's a smaller example that takes under 2 seconds with the patch, and still takes a very long time without the patch. (Hopefully integer factorization algorithms in the future will not improve to the point where the second part of the previous sentence becomes false.) I also added a speed optimization in the field creation step to help things along.
p = 12 * next_prime(2^246) * next_prime(2^247)  1 F = FiniteField(p, proof=False) E = EllipticCurve([F(1), F(0)]) P = E(0).division_points(3)[1] EllipticCurveIsogeny(E, P)
comment:10 Changed 4 years ago by
 Branch changed from u/klui/avoid_order_computation_in_ellipticcurveisogeny_function to u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function
comment:11 Changed 4 years ago by
 Commit changed from 250f15ab7d9f3c8759afe55f687ecc5e49d8fb32 to e6ec1d657fec57c311292fbef96832b8302833c4
We have updated our branch to include the faster doctest.
New commits:
e6ec1d6  Smaller and faster doctest for orderfree isogenies

comment:12 Changed 4 years ago by
Sorry to bug you again. But is there a even smaller example? I think the doctests are suppose to take under a second. Alternatively, you can flag it as a long test.
http://doc.sagemath.org/html/en/developer/doctesting.html#runlongdoctests
As a side question, how are you able to come up with these primes?
After this, it should be go to go. Can you set the ticket as 'need review'? and I can give it a positive review.
comment:13 Changed 4 years ago by
You just pick random exponents until the resulting p is a prime. What you want is:
 p is not too large (so that the test runs fast)
 factoring p+1 takes a long time (so that the test demonstrates the need for avoiding factoring p+1)
However, I'm worried that if p is too small then improvements in future factoring technology will render the second point false while still not invalidating the main conclusion that factoring is too slow and should be avoided in general. I think the lowest we should go is (180, 194). This runs in under 1 second on my machine.
The full test is then:
p = 12 * next_prime(2^180) * next_prime(2^194)  1 F = FiniteField(p, proof=False) E = EllipticCurve([F(1), F(0)]) P = E(0).division_points(3)[1] EllipticCurveIsogeny(E, P)
comment:14 Changed 4 years ago by
 Commit changed from e6ec1d657fec57c311292fbef96832b8302833c4 to 185d13695b0180cd483c4e67e26b43dccc6e1d66
Branch pushed to git repo; I updated commit sha1. New commits:
185d136  Faster doctest for orderfree isogenies that is under one second

comment:15 Changed 4 years ago by
 Status changed from new to needs_review
I have changed the status to 'needs review' and the branch has been updated to include the faster doctest. The doctest runs in under 1 second on my machine as well.
comment:16 Changed 4 years ago by
 Branch changed from u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function to u/klui/avoid_order_computation_in_ellipticcurveisogeny_function
comment:17 Changed 4 years ago by
 Commit changed from 185d13695b0180cd483c4e67e26b43dccc6e1d66 to 926ff9b5a81a114433221c2ac9e9d4be6e70d0d9
I made a small aesthetic change which was to fix some trailing spaces.
I only made trivial code changes to this ticket so I hope it's okay that I'm the reviewer and am giving it a positive review.
New commits:
926ff9b  fixed trailing whitespace

comment:18 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:19 Changed 4 years ago by
 Status changed from positive_review to needs_work
Reviewer name missing.
comment:20 Changed 4 years ago by
 Reviewers set to Kevin Lui
 Status changed from needs_work to positive_review
Opps. Sorry!
comment:21 Changed 4 years ago by
 Branch changed from u/klui/avoid_order_computation_in_ellipticcurveisogeny_function to 926ff9b5a81a114433221c2ac9e9d4be6e70d0d9
 Resolution set to fixed
 Status changed from positive_review to closed
This is related to ticket #22161, although our proposed fix is different from Kevin's. (I wasn't sure how to deal with tickets that already have a branch.)
Basically, I am convinced that you never want to compute the group order or even the point order separately, ever. You should just always list all the multiples of P until you repeat back to where you started. In any other context, this would be a slow way to compute the group order, but in this context, it's a free computation, since you need the entire list of points anyway in order to apply Velu's formulas.