Opened 8 years ago

Closed 8 years ago

# Further isogeny improvement

Reported by: Owned by: Jeroen Demeyer major sage-6.8 elliptic curves John Cremona Jeroen Demeyer John Cremona N/A 7dfcc8e 7dfcc8e3a8d27b923afaae87a0b4764008146f5d #18589

### Description (last modified by Jeroen Demeyer)

To compute all `l`-isogenies, Sage uses a function `mult(f)` which computes

```gcd( numerator(f(m)), psi )
```

where `m` is a rational function giving the multiplication-by-`m` map (the denominator of `m` is coprime to `psi`)

Instead of the above computation, the inverse direction is actually easier to compute: given `g`, we want to find `f` such that

```gcd( numerator(f(m)), psi ) = g
```

Using some theory, this is equivalent to

```f(m) = 0 mod g
```

Since `f` must be irreducible of the same degree as `g`, this is just the characteristic (= minimal) polynomial of `m mod g`.

Example timing:

before

```sage: %time from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general; E = EllipticCurve(GF(3^3,'a'), [0,0,0,-1,0]); L = isogenies_prime_degree_general(E, 73)
CPU times: user 1min 52s, sys: 16 ms, total: 1min 52s
Wall time: 1min 52s
```

after

```sage: %time from sage.schemes.elliptic_curves.isogeny_small_degree import isogenies_prime_degree_general; E = EllipticCurve(GF(3^3,'a'), [0,0,0,-1,0]); L = isogenies_prime_degree_general(E, 73)
CPU times: user 33.1 s, sys: 107 ms, total: 33.2 s
Wall time: 33.2 s
```

### comment:1 Changed 8 years ago by Jeroen Demeyer

Dependencies: → #18589

### comment:2 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:3 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:4 Changed 8 years ago by Jeroen Demeyer

Branch: → u/jdemeyer/ticket/18611

### comment:5 Changed 8 years ago by Jeroen Demeyer

Commit: → f26e68173ae90f232ca4e3ca744d3285d108ded7 new → needs_review

New commits:

 ​47ccfd5 `#18589 isogeny improvement` ​ad56369 `#18589 simplified code + further improvements` ​2f83c20 `#18589: 2 simplifications following review` ​3d687e5 `#18589 further one-liner` ​f26e681 `Compute inverse of old mult() more efficiently`

### comment:6 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:7 Changed 8 years ago by git

Commit: f26e68173ae90f232ca4e3ca744d3285d108ded7 → 7dfcc8e3a8d27b923afaae87a0b4764008146f5d

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​7dfcc8e `Compute inverse of old mult() more efficiently`

### comment:8 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

### comment:9 Changed 8 years ago by John Cremona

Before I go to look at the code I will confirm the theory sketched in the ticket description. In the notation there, g is irreducible and if alpha is a root of it then the desired f is precisely the min poly of m(alpha).

### comment:10 Changed 8 years ago by John Cremona

Reviewers: → John Cremona needs_review → positive_review

Looks good and tests out well. For the record:

```sage: K.<a>=NumberField(x^2-x-22)                                                              sage: sage: E=EllipticCurve([0,0,1,-1590*a-8580,92750*a+359875])
sage: sage: time E.isogenies_prime_degree(89)
CPU times: user 25min 37s, sys: 2.4 s, total: 25min 39s
Wall time: 25min 37s
[Isogeny of degree 89 from Elliptic Curve defined by y^2 + y = x^3 + (-1590*a-8580)*x + (92750*a+359875) over Number Field in a with defining polynomial x^2 - x - 22 to Elliptic Curve defined by y^2 + y = x^3 + (12594390*a-80556570)*x + (-65385874750*a+319086769867) over Number Field in a with defining polynomial x^2 - x - 22]
```

though thanks to the code at #18589 this does not use mult() anyway so is not strictly relevant to this ticket.

### comment:11 Changed 8 years ago by Jeroen Demeyer

One more remark on the algorithm: the current `mult()` does not use the fact that the characteristic polynomial is one of finitely many given possibilities. We could probably optimize even more using this information. However, my impression is that it's not currently worth it, since the other parts of the isogeny computation take more time anyway. If you do come across an example where `mult()` dominates the computation, I'd like to know.

### comment:12 Changed 8 years ago by Volker Braun

Branch: u/jdemeyer/ticket/18611 → 7dfcc8e3a8d27b923afaae87a0b4764008146f5d → fixed positive_review → closed
Note: See TracTickets for help on using tickets.