Avoid order computation in EllipticCurveIsogeny function

[sagetrac-m3vandyk]

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.

Component: elliptic curves

Keywords: isogeny

Author: Madison Van Dyk; David Jao

Branch/Commit: 926ff9b

Reviewer: Kevin Lui

Issue created by migration from https://trac.sagemath.org/ticket/24640

[sagetrac-m3vandyk]

Branch: u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function

[davidjao]

comment:2

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 point 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.

[davidjao]

Commit: 0a674fd

[sagetrac-git]

Changed commit from 0a674fd to b9ababe

[sagetrac-git]

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

b9ababe

update Isogeny function to address slow order calcuaiton

[kevinywlui]

comment:4

Can you add an example demonstrating the speedup?

[sagetrac-git]

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

b461d38

Add doctest for order-free isogeny computation

[sagetrac-git]

Changed commit from b9ababe to b461d38

[sagetrac-m3vandyk]

comment:6

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.

[kevinywlui]

Changed branch from u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function to u/klui/avoid_order_computation_in_ellipticcurveisogeny_function

[kevinywlui]

Changed commit from b461d38 to 250f15a

[kevinywlui]

comment:8

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:

250f15a

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

[davidjao]

comment:9

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)

[sagetrac-m3vandyk]

Changed branch from u/klui/avoid_order_computation_in_ellipticcurveisogeny_function to u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function

[sagetrac-m3vandyk]

comment:11

We have updated our branch to include the faster doctest.

---

New commits:

e6ec1d6

Smaller and faster doctest for order-free isogenies

[sagetrac-m3vandyk]

Changed commit from 250f15a to e6ec1d6

[kevinywlui]

comment:12

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.

[davidjao]

comment:13

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)

[sagetrac-git]

Changed commit from e6ec1d6 to 185d136

[sagetrac-git]

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

185d136

Faster doctest for order-free isogenies that is under one second

[sagetrac-m3vandyk]

comment:15

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.

[kevinywlui]

Changed branch from u/m3vandyk/avoid_order_computation_in_ellipticcurveisogeny_function to u/klui/avoid_order_computation_in_ellipticcurveisogeny_function

[kevinywlui]

Changed commit from 185d136 to 926ff9b

[kevinywlui]

comment:17

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

[tscrim]

comment:19

Reviewer name missing.

[kevinywlui]

comment:20

Opps. Sorry!

[kevinywlui]

Reviewer: Kevin Lui

[vbraun]

Changed branch from u/klui/avoid_order_computation_in_ellipticcurveisogeny_function to 926ff9b