Contributors: DGA CELAR; Institut de Recherche Mathématique de Rennes (IRMAR); Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes); Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-Institut Agro Rennes Angers; Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro); Lithe and fast algorithmic number theory (LFANT); Institut de Mathématiques de Bordeaux (IMB); Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria); Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS); Analyse cryptographique et arithmétique (CANARI); Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS); ANR-19-CE48-0008,CIAO,Cryptographie, isogenies et variété abéliennes surpuissantes(2019); ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)
نبذة مختصرة : International audience ; 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.
Processing Request
No Comments.