Fast change of level and applications to isogenies
| hal.structure.identifier | DGA CELAR | |
| hal.structure.identifier | Institut de Recherche Mathématique de Rennes [IRMAR] | |
| dc.contributor.author | LUBICZ, David | |
| hal.structure.identifier | Lithe and fast algorithmic number theory [LFANT] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Analyse cryptographique et arithmétique [CANARI] | |
| dc.contributor.author | ROBERT, Damien | |
| dc.date.accessioned | 2024-04-04T02:40:50Z | |
| dc.date.available | 2024-04-04T02:40:50Z | |
| dc.date.issued | 2023 | |
| dc.date.conference | 2022-08-08 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191095 | |
| dc.description.abstractEn | 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. | |
| dc.description.sponsorship | Cryptographie, isogenies et variété abéliennes surpuissantes - ANR-19-CE48-0008 | |
| dc.description.sponsorship | Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation - ANR-11-LABX-0020 | |
| dc.language.iso | en | |
| dc.rights.uri | http://creativecommons.org/licenses/by/ | |
| dc.source.title | Research in Number Theory | |
| dc.subject.en | Isogenies | |
| dc.subject.en | abelian varieties | |
| dc.subject.en | computational algebraic geometry | |
| dc.title.en | Fast change of level and applications to isogenies | |
| dc.type | Communication dans un congrès | |
| dc.identifier.doi | 10.1007/s40993-022-00407-9 | |
| dc.subject.hal | Informatique [cs]/Calcul formel [cs.SC] | |
| dc.subject.hal | Mathématiques [math]/Théorie des nombres [math.NT] | |
| bordeaux.page | article n°7 | |
| bordeaux.volume | 9 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 1 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | ANTS 2022 - Fifteenth Algorithmic Number Theory Symposium | |
| bordeaux.country | GB | |
| bordeaux.title.proceeding | Research in Number Theory | |
| bordeaux.conference.city | Bristol | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-03738315 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.conference.end | 2022-08-12 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-03738315v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.btitle=Research%20in%20Number%20Theory&rft.date=2023&rft.volume=9&rft.issue=1&rft.spage=article%20n%C2%B07&rft.epage=article%20n%C2%B07&rft.au=LUBICZ,%20David&ROBERT,%20Damien&rft.genre=unknown |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||