LUBICZ, David; ROBERT, Damien

doi:10.1007/s40993-022-00407-9

Métadonnées

Afficher la notice complète

Licence d’utilisation du document

LUBICZ, David
DGA CELAR
Institut de Recherche Mathématique de Rennes [IRMAR]

ROBERT, Damien
Lithe and fast algorithmic number theory [LFANT]
Institut de Mathématiques de Bordeaux [IMB]
Analyse cryptographique et arithmétique [CANARI]

Langue

Communication dans un congrès

Ce document a été publié dans

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

Résumé en anglais

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.< Réduire

Mots clés en anglais

Isogenies

abelian varieties

computational algebraic geometry

URI

https://oskar-bordeaux.fr/handle/20.500.12278/191095

DOI

http://dx.doi.org/10.1007/s40993-022-00407-9

Project ANR

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

Origine

Importé de hal

Unités de recherche

Institut de Mathématiques de Bordeaux (IMB) - UMR 5251