Skip to Main content Skip to Navigation
Conference papers

Fast change of level and applications to isogenies

Abstract : Let (A, L , Θn) be a dimension g abelian variety together with a level n theta structure over a field k of odd characteristic, we denote by (θ Θ L i) (Z/nZ) g ∈ Γ(A, L) the associated standard basis. For ℓ a positive integer relatively prime to n and the characteristic of k, we study change of level algorithms which allow to compute level ℓn theta functions (θ Θ L ℓ i (x)) i∈(Z/ℓnZ) g from the knowledge of level n theta functions (θ Θ L i (x)) (Z/nZ) g or conversely. The classical duplication formulas is an example of change of level algorithm to go from level n to level 2n. The main result of this paper states that there exists an algorithm to go from level n to level ℓn in O(n g ℓ 2g log(ℓ)) operations in k. We deduce an algorithm to compute an isogeny f : A → B from the knowledge of (A, L , Θn) and K ⊂ A[ℓ] isotropic for the Weil pairing which computes f (x) for x ∈ A(k) in O((nℓ) g log(ℓ)) operations in k. We remark that this isogeny computation algorithm is of quasi-linear complexity in the size of K.
Complete list of metadata

https://hal.inria.fr/hal-03738315
Contributor : Damien Robert Connect in order to contact the contributor
Submitted on : Tuesday, July 26, 2022 - 12:04:44 AM
Last modification on : Wednesday, July 27, 2022 - 3:47:49 AM

File

article_short.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03738315, version 1

Citation

David Lubicz, Damien Robert. Fast change of level and applications to isogenies. Fifteenth Algorithmic Number Theory Symposium, ANTS-XV, Aug 2022, Bristol, United Kingdom. ⟨hal-03738315⟩

Share

Metrics

Record views

0

Files downloads

0