The system will be going down for regular maintenance. Please save your work and logout.
Fast change of level and applications to isogenies
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
< Reduce
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]
Language
en
Communication dans un congrès
This item was published in
Research in Number Theory, Research in Number Theory, ANTS 2022 - Fifteenth Algorithmic Number Theory Symposium, 2022-08-08, Bristol. 2023, vol. 9, n° 1, p. article n°7
English 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 ...Read more >
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.Read less <
English Keywords
Isogenies
abelian varieties
computational algebraic geometry
ANR Project
Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008
Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020
Origin
Hal imported
