More Web Proxy on the site http://driver.im/

research-article

Fast Computation of Hyperelliptic Curve Isogenies in Odd Characteristic

Author:

Elie EidAuthors Info & Claims

ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

Pages 131 - 138

https://doi.org/10.1145/3452143.3465523

Published: 18 July 2021 Publication History

Abstract

Let p be an odd prime number and g < 2 be an integer. We present an algorithm for computing explicit rational representations of isogenies between Jacobians of hyperelliptic curves of genus g over an extension K of the field of p-adic numbers 𝒬 _p. The algorithm has a quasi-linear complexity in the degree of the rational representation. It relies on an efficient resolution, with a logarithmic loss of p-adic precision, of a first order system of differential equations.

References

[1]

Sean Ballentine, Aurore Guillevic, Elisa Lorenzo García, Chloe Martindale, Maike Massierer, Benjamin Smith, and Jaap Top. 2017. Isogenies for point counting on genus two hyperelliptic curves with maximal real multiplication. In Algebraic geometry for coding theory and cryptography. Springer, 63--94.

[2]

Wieb Bosma, John Cannon, and Catherine Playoust. 1997. The Magma algebra system. I. The user language. J. Symbolic Comput., Vol. 24, 3-4 (1997), 235--265. https://doi.org/10.1006/jsco.1996.0125 Computational algebra and number theory (London, 1993).

Digital Library

[3]

Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy, and Éric Schost. 2017. Algorithmes Efficaces en Calcul Formel.

[4]

Xavier Caruso. 2017. Computations with p-adic numbers. Les cours du CIRM, Vol. 5, 1 (2017). https://doi.org/10.5802/ccirm.25

[5]

Xavier Caruso, Elie Eid, and Reynald Lercier. 2020. Fast computation of elliptic curve isogenies in characteristic two. (March 2020). https://hal.archives-ouvertes.fr/hal-02508825 working paper or preprint.

[6]

Xavier Caruso, David Roe, and Tristan Vaccon. 2014. Tracking p-adic precision. LMS J. Comput. Math., Vol. 17, suppl. A (2014), 274--294. https://doi.org/10.1112/S1461157014000357

[7]

Xavier Caruso, David Roe, and Tristan Vaccon. 2015. p-adic stability in linear algebra. In ISSAC'15--Proceedings of the 2015 ACM International Symposium on Symbolic and Algebraic Computation. ACM, New York, 101--108.

Digital Library

[8]

Romain Cosset and Damien Robert. 2015. Computing $(ell, ell)$-isogenies in polynomial time on Jacobians of genus 2 curves. Math. Comp., Vol. 84, 294 (2015), 1953--1975.

[9]

Craig Costello and Benjamin Smith. 2020. The supersingular isogeny problem in genus 2 and beyond. In International Conference on Post-Quantum Cryptography. Springer, 151--168.

[10]

Jean-Marc Couveignes and Tony Ezome. 2015. Computing functions on Jacobians and their quotients. LMS Journal of Computation and Mathematics, Vol. 18, 1 (2015), 555--577. https://doi.org/10.1112/S1461157015000169

[11]

E. V. Flynn and Yan Bo Ti. 2019. Genus Two Isogeny Cryptography. In Post-Quantum Cryptography, Jintai Ding and Rainer Steinwandt (Eds.). Springer International Publishing, Cham, 286--306.

[12]

Kiran S. Kedlaya and Christopher Umans. 2011. Fast polynomial factorization and modular composition. SIAM J. Comput., Vol. 40, 6 (2011), 1767--1802. https://doi.org/10.1137/08073408X

Digital Library

[13]

Jean Kieffer, Aurel Page, and Damien Robert. 2020. Computing isogenies from modular equations between Jacobians of genus 2 curves. (Jan. 2020). https://hal.archives-ouvertes.fr/hal-02436133 working paper or preprint.

[14]

Pierre Lairez and Tristan Vaccon. 2016. On p-adic differential equations with separation of variables. In Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation. ACM, New York, 319--323.

Digital Library

[15]

Reynald Lercier and Thomas Sirvent. 2008. On Elkies subgroups of l-torsion points in elliptic curves defined over a finite field. J. Théor. Nombres Bordeaux, Vol. 20, 3 (2008), 783--797. http://jtnb.cedram.org/item?id=JTNB_2008__20_3_783_0

[16]

Teruhisa Matsusaka. 1959. On a characterization of a Jacobian variety. Memoirs of the College of Science, University of Kyoto., Vol. 32, 1 (1959), 1--19.

[17]

Enea Milio. 2019. Computing isogenies between Jacobian of curves of genus 2 and 3. (Aug. 2019). https://hal.archives-ouvertes.fr/hal-01589683 preprint.

[18]

James S Milne. 1986. Abelian varieties. In Arithmetic geometry. Springer, 103--150.

[19]

Frans OORT and Tsutomu SEKIGUCHI. 1986. The canonical lifting of an ordinary Jacobian variety need not be a Jacobian variety. J. Math. Soc. Japan, Vol. 38, 3 (07 1986), 427--437. https://doi.org/10.2969/jmsj/03830427

[20]

Emmanuel Thomé. 2003. Algorithmes de calcul de logarithmes discrets dans les corps finis. Ph.D. Dissertation. École polytechnique.

[21]

Song Tian. 2020. Translating the discrete logarithm problem on Jacobians of genus 3 hyperelliptic curves with (ℓ,ℓ,ℓ)-isogenies. arxiv: 2007.03172 [math.AG]

[22]

Tristan Vaccon. 2015. Précision p-adique: applications en calcul formel, théorie des nombres et cryptographie. Ph.D. Dissertation. University of Rennes 1.

Cited By

Kieffer JPage ARobert D(2024)Computing isogenies from modular equations in genus twoJournal of Algebra10.1016/j.jalgebra.2024.11.029Online publication date: Dec-2024
https://doi.org/10.1016/j.jalgebra.2024.11.029
Eid E(2023)Efficient computation of Cantor's division polynomials of hyperelliptic curves over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2022.10.006117:C(68-100)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.10.006
Pagès R(2022)Factoring differential operators over algebraic curves in positive characteristicACM Communications in Computer Algebra10.1145/3572867.357287656:2(60-63)Online publication date: 23-Nov-2022
https://dl.acm.org/doi/10.1145/3572867.3572876

Index Terms

Fast Computation of Hyperelliptic Curve Isogenies in Odd Characteristic
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Number theory algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
      1. Ordinary differential equations

Recommendations

Genus 2 hyperelliptic curve families with explicit jacobian order evaluation and pairing-friendly constructions
Pairing'12: Proceedings of the 5th international conference on Pairing-Based Cryptography

The use of elliptic and hyperelliptic curves in cryptography relies on the ability to compute the Jacobian order of a given curve. Recently, Satoh proposed a probabilistic polynomial time algorithm to test whether the Jacobian --- over a finite field ${\...
Eta pairing computation on general divisors over hyperelliptic curves y²=x^p-x+d

Recent developments on the Tate or Eta pairing computation over hyperelliptic curves by Duursma-Lee and Barreto et al. have focused on degenerate divisors. We present efficient methods that work for general divisors to compute the Eta paring over ...
Correspondences on hyperelliptic curves and applications to the discrete logarithm
SIIS'11: Proceedings of the 2011 international conference on Security and Intelligent Information Systems

The discrete logarithm is an important crypto primitive for public key cryptography. The main source for suitable groups are divisor class groups of carefully chosen curves over finite fields. Because of index-calculus algorithms one has to avoid curves ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ISSAC '21: Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation

July 2021

379 pages

ISBN:9781450383820

DOI:10.1145/3452143

General Chair:
Frédéric Chyzak
Inria, France
,
Program Chair:
George Labahn
University of Waterloo, Canada

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 July 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '21

Sponsor:

SIGSAM

ISSAC '21: International Symposium on Symbolic and Algebraic Computation

July 18 - 23, 2021

Virtual Event, Russian Federation

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
56
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kieffer JPage ARobert D(2024)Computing isogenies from modular equations in genus twoJournal of Algebra10.1016/j.jalgebra.2024.11.029Online publication date: Dec-2024
https://doi.org/10.1016/j.jalgebra.2024.11.029
Eid E(2023)Efficient computation of Cantor's division polynomials of hyperelliptic curves over finite fieldsJournal of Symbolic Computation10.1016/j.jsc.2022.10.006117:C(68-100)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jsc.2022.10.006
Pagès R(2022)Factoring differential operators over algebraic curves in positive characteristicACM Communications in Computer Algebra10.1145/3572867.357287656:2(60-63)Online publication date: 23-Nov-2022
https://dl.acm.org/doi/10.1145/3572867.3572876

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents