doi: 10.3934/amc.2022038
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Loops, multi-edges and collisions in supersingular isogeny graphs

Mathematical Institute, University of Oxford, Andrew Wiles Building, OX2 6GG, United Kingdom

Received  September 2021 Revised  March 2022 Early access June 2022

Supersingular isogeny graphs are known to have very few loops and multi-edges. We formalize this idea by studying and finding bounds for the number of loops and multi-edges in such graphs. We also find conditions under which the supersingular isogeny graph $ \Lambda_p( \ell) $ is simple.

The methods presented in this paper can be used to study many kinds of collisions in supersingular isogeny graphs. As an application, we introduce the notion of bi-route number for two graphs $ \Lambda_p( \ell_1),\Lambda_p( \ell_2) $ and compute bounds for it. We also study the number of edges in common between the graphs $ \Lambda_p( \ell_1),\Lambda_p( \ell_2) $.

Citation: Wissam Ghantous. Loops, multi-edges and collisions in supersingular isogeny graphs. Advances in Mathematics of Communications, doi: 10.3934/amc.2022038
References:
[1]

D. X. CharlesK. E. Lauter and E. Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptology, 22 (2009), 93-113.  doi: 10.1007/s00145-007-9002-x.

[2]

L. De FeoD. Jao and J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol., 8 (2014), 209-247.  doi: 10.1515/jmc-2012-0015.

[3]

M. Deuring, Die typen der multiplikatorenringe elliptischer funktionenkörper, Abh. Math. Sem. Hansischen Univ., 14 (1941), 197-272.  doi: 10.1007/BF02940746.

[4]

J. Gierster, Ueber relationen zwischen klassenzahlen binärer quadratischer formen von negativer determinante, Math. Ann., 21 (1883), 1-50.  doi: 10.1007/BF01442611.

[5]

O. Goldreich, Randomized methods in computation, lecture 10, Spring, (2001), 3–4, http://www.wisdom.weizmann.ac.il/ oded/PS/RND/l10.ps.

[6]

B. H. Gross, Heights and the special values of $\text{L}$-series, Number theory, CMS Conf. Proc., Amer. Math. Soc., Providence, RI, 7 (1987), 115-187. 

[7]

A. Hurwitz, Ueber relationen zwischen classenanzahlen binärer quadratischer formen von negativer determinante, Mathematische Annalen, 25 (1885), 157-196.  doi: 10.1007/BF01446402.

[8]

L. Kronecker, Ueber die anzahl der verschiedenen classen quadratischer formen von negativer determinante, J. Reine Angew. Math., 57 (1860), 248-255. doi: 10.1515/crll.1860.57.248.

[9]

L. Lovász, Very large graphs, arXiv preprint, (2009), arXiv: 0902.0132.

[10]

A. K. Pizer, Ramanujan graphs and hecke operators, Bull. Amer. Math. Soc. (N.S.), 23 (1990), 127-137.  doi: 10.1090/S0273-0979-1990-15918-X.

[11]

J. H. Silverman, The Arithmetic of Elliptic Curves, Second edition, Graduate Texts in Mathematics, 106. Springer, Dordrecht, 2009. doi: 10.1007/978-0-387-09494-6.

[12]

J. Voight, Quaternion Algebras, Graduate Texts in Mathematics, 288. Springer, Cham, 2021. doi: 10.1007/978-3-030-56694-4.

show all references

References:
[1]

D. X. CharlesK. E. Lauter and E. Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptology, 22 (2009), 93-113.  doi: 10.1007/s00145-007-9002-x.

[2]

L. De FeoD. Jao and J. Plût, Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies, J. Math. Cryptol., 8 (2014), 209-247.  doi: 10.1515/jmc-2012-0015.

[3]

M. Deuring, Die typen der multiplikatorenringe elliptischer funktionenkörper, Abh. Math. Sem. Hansischen Univ., 14 (1941), 197-272.  doi: 10.1007/BF02940746.

[4]

J. Gierster, Ueber relationen zwischen klassenzahlen binärer quadratischer formen von negativer determinante, Math. Ann., 21 (1883), 1-50.  doi: 10.1007/BF01442611.

[5]

O. Goldreich, Randomized methods in computation, lecture 10, Spring, (2001), 3–4, http://www.wisdom.weizmann.ac.il/ oded/PS/RND/l10.ps.

[6]

B. H. Gross, Heights and the special values of $\text{L}$-series, Number theory, CMS Conf. Proc., Amer. Math. Soc., Providence, RI, 7 (1987), 115-187. 

[7]

A. Hurwitz, Ueber relationen zwischen classenanzahlen binärer quadratischer formen von negativer determinante, Mathematische Annalen, 25 (1885), 157-196.  doi: 10.1007/BF01446402.

[8]

L. Kronecker, Ueber die anzahl der verschiedenen classen quadratischer formen von negativer determinante, J. Reine Angew. Math., 57 (1860), 248-255. doi: 10.1515/crll.1860.57.248.

[9]

L. Lovász, Very large graphs, arXiv preprint, (2009), arXiv: 0902.0132.

[10]

A. K. Pizer, Ramanujan graphs and hecke operators, Bull. Amer. Math. Soc. (N.S.), 23 (1990), 127-137.  doi: 10.1090/S0273-0979-1990-15918-X.

[11]

J. H. Silverman, The Arithmetic of Elliptic Curves, Second edition, Graduate Texts in Mathematics, 106. Springer, Dordrecht, 2009. doi: 10.1007/978-0-387-09494-6.

[12]

J. Voight, Quaternion Algebras, Graduate Texts in Mathematics, 288. Springer, Cham, 2021. doi: 10.1007/978-3-030-56694-4.

Figure 1.  The graph $ \Lambda_{109}(2,3) $ where $ 2 $-isogenies are in blue and $ 3 $-isogenies are in green
Figure 2.  The undirected graph $ \Lambda_{73}(2) $
Figure 3.  The directed graph $ \Lambda_{71}(2) $
Figure 4.  The graph $ \Lambda_{193}(2) $
Figure 5.  The graph $ \Lambda_{113}(2) $
Figure 6.  The graph $ \Lambda_{97}(3) $
Figure 7.  The graph $ \Lambda_{1009}(2) $
Figure 8.  Multiple edges
[1]

Qingqing Li, Tianshou Zhou. Interlocked multi-node positive and negative feedback loops facilitate oscillations. Discrete and Continuous Dynamical Systems - B, 2019, 24 (7) : 3139-3155. doi: 10.3934/dcdsb.2018304

[2]

Liang Zhao. New developments in using stochastic recipe for multi-compartment model: Inter-compartment traveling route, residence time, and exponential convolution expansion. Mathematical Biosciences & Engineering, 2009, 6 (3) : 663-682. doi: 10.3934/mbe.2009.6.663

[3]

Yuta Ishii, Kazuhiro Kurata. Existence of multi-peak solutions to the Schnakenberg model with heterogeneity on metric graphs. Communications on Pure and Applied Analysis, 2021, 20 (4) : 1633-1679. doi: 10.3934/cpaa.2021035

[4]

David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97

[5]

Xia Zhao, Jianping Dou. Bi-objective integrated supply chain design with transportation choices: A multi-objective particle swarm optimization. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1263-1288. doi: 10.3934/jimo.2018095

[6]

Josep M. Miret, Jordi Pujolàs, Nicolas Thériault. Trisection for supersingular genus $2$ curves in characteristic $2$. Advances in Mathematics of Communications, 2014, 8 (4) : 375-387. doi: 10.3934/amc.2014.8.375

[7]

João Paulo da Silva, Julio López, Ricardo Dahab. Isogeny formulas for Jacobi intersection and twisted hessian curves. Advances in Mathematics of Communications, 2020, 14 (3) : 507-523. doi: 10.3934/amc.2020048

[8]

Jordi-Lluís Figueras, Àlex Haro. Triple collisions of invariant bundles. Discrete and Continuous Dynamical Systems - B, 2013, 18 (8) : 2069-2082. doi: 10.3934/dcdsb.2013.18.2069

[9]

Maria Conceição A. Leite, Yunjiao Wang. Multistability, oscillations and bifurcations in feedback loops. Mathematical Biosciences & Engineering, 2010, 7 (1) : 83-97. doi: 10.3934/mbe.2010.7.83

[10]

Xingbo Liu, Deming Zhu. On the stability of homoclinic loops with higher dimension. Discrete and Continuous Dynamical Systems - B, 2012, 17 (3) : 915-932. doi: 10.3934/dcdsb.2012.17.915

[11]

Ali Moussaoui, Pierre Auger, Christophe Lett. Optimal number of sites in multi-site fisheries with fish stock dependent migrations. Mathematical Biosciences & Engineering, 2011, 8 (3) : 769-783. doi: 10.3934/mbe.2011.8.769

[12]

Bennett Palmer. Stable closed equilibria for anisotropic surface energies: Surfaces with edges. Journal of Geometric Mechanics, 2012, 4 (1) : 89-97. doi: 10.3934/jgm.2012.4.89

[13]

Núria Fagella, Àngel Jorba, Marc Jorba-Cuscó, Joan Carles Tatjer. Classification of linear skew-products of the complex plane and an affine route to fractalization. Discrete and Continuous Dynamical Systems, 2019, 39 (7) : 3767-3787. doi: 10.3934/dcds.2019153

[14]

Rhoda P. Agdeppa, Nobuo Yamashita, Masao Fukushima. An implicit programming approach for the road pricing problem with nonadditive route costs. Journal of Industrial and Management Optimization, 2008, 4 (1) : 183-197. doi: 10.3934/jimo.2008.4.183

[15]

B. Fernandez, P. Guiraud. Route to chaotic synchronisation in coupled map lattices: Rigorous results. Discrete and Continuous Dynamical Systems - B, 2004, 4 (2) : 435-456. doi: 10.3934/dcdsb.2004.4.435

[16]

W. Josh Sonnier, C. I. Christov. Repelling soliton collisions in coupled Schrödinger equations with negative cross modulation. Conference Publications, 2009, 2009 (Special) : 708-718. doi: 10.3934/proc.2009.2009.708

[17]

Asaf Kislev. Compactly supported Hamiltonian loops with a non-zero Calabi invariant. Electronic Research Announcements, 2014, 21: 80-88. doi: 10.3934/era.2014.21.80

[18]

Azucena Álvarez, Francisco R. Romero, José M. Romero, Juan F. R. Archilla. Nonsymmetric moving breather collisions in the Peyrard-Bishop DNA model. Discrete and Continuous Dynamical Systems - S, 2011, 4 (5) : 995-1006. doi: 10.3934/dcdss.2011.4.995

[19]

Christopher Cox, Renato Feres. Differential geometry of rigid bodies collisions and non-standard billiards. Discrete and Continuous Dynamical Systems, 2016, 36 (11) : 6065-6099. doi: 10.3934/dcds.2016065

[20]

F. J. Lin. Hamiltonian dynamics of atom-diatomic molecule complexes and collisions. Conference Publications, 2007, 2007 (Special) : 655-666. doi: 10.3934/proc.2007.2007.655

2021 Impact Factor: 1.015

Metrics

  • PDF downloads (88)
  • HTML views (42)
  • Cited by (0)

Other articles
by authors

[Back to Top]