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: sage-8.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:

Status badges

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 m3vandyk

  • Branch set to u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function

comment:2 Changed 4 years ago by djao

  • Commit set to 0a674fd488dcd7cb779101d263c10a874a13cf77

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.

Version 1, edited 4 years ago by djao (previous) (next) (diff)

comment:3 Changed 4 years ago by git

  • Commit changed from 0a674fd488dcd7cb779101d263c10a874a13cf77 to b9ababe78120a3104d2ddb53e481bac66106ca40

Branch pushed to git repo; I updated commit sha1. New commits:

b9ababeupdate Isogeny function to address slow order calcuaiton

comment:4 Changed 4 years ago by klui

Can you add an example demonstrating the speedup?

comment:5 Changed 4 years ago by git

  • Commit changed from b9ababe78120a3104d2ddb53e481bac66106ca40 to b461d389b5df0c982ac94778f33686673951172d

Branch pushed to git repo; I updated commit sha1. New commits:

b461d38Add doctest for order-free isogeny computation

comment:6 Changed 4 years ago by m3vandyk

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 klui

  • 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 klui

  • 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 --warn-long 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:

250f15afixed documentation, removed an import that's not longer needed, removed a list function

comment:9 Changed 4 years ago by djao

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 m3vandyk

  • 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 m3vandyk

  • Commit changed from 250f15ab7d9f3c8759afe55f687ecc5e49d8fb32 to e6ec1d657fec57c311292fbef96832b8302833c4

We have updated our branch to include the faster doctest.


New commits:

e6ec1d6Smaller and faster doctest for order-free isogenies

comment:12 Changed 4 years ago by klui

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#run-long-doctests

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 djao

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 git

  • Commit changed from e6ec1d657fec57c311292fbef96832b8302833c4 to 185d13695b0180cd483c4e67e26b43dccc6e1d66

Branch pushed to git repo; I updated commit sha1. New commits:

185d136Faster doctest for order-free isogenies that is under one second

comment:15 Changed 4 years ago by m3vandyk

  • 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 klui

  • 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 klui

  • 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:

926ff9bfixed trailing whitespace

comment:18 Changed 4 years ago by klui

  • Status changed from needs_review to positive_review

comment:19 Changed 4 years ago by tscrim

  • Status changed from positive_review to needs_work

Reviewer name missing.

comment:20 Changed 4 years ago by klui

  • Reviewers set to Kevin Lui
  • Status changed from needs_work to positive_review

Opps. Sorry!

comment:21 Changed 4 years ago by vbraun

  • Branch changed from u/klui/avoid_order_computation_in_ellipticcurveisogeny_function to 926ff9b5a81a114433221c2ac9e9d4be6e70d0d9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.