Abstract
<p> Supersingular elliptic curve <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -isogeny graphs over finite fields offer a setting for a number of quantum-resistant cryptographic protocols. The security analysis of these schemes typically assumes that these graphs behave randomly. Motivated by this debatable assertion, we explore structural properties of these graphs. We detail the behavior, governed by congruence conditions on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="p"> <mml:semantics> <mml:mi>p</mml:mi> <mml:annotation encoding="application/x-tex">p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , of the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -isogeny graph over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript p"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbb {F}_p}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when passing to the spine, i.e. the subgraph induced by the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript p"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbb {F}_p}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -vertices in the full <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -isogeny graph. We describe the diameter of the spine and offer numerical data on the number of vertices, over both <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F Subscript p"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mi>p</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\mathbb {F}_p}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="double-struck upper F overbar Subscript p"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mover> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">F</mml:mi> </mml:mrow> <mml:mo accent="false"> ¯ </mml:mo> </mml:mover> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>p</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\overline {\mathbb {F}}_{p}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , in the center of the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -isogeny graph. Our plots of these counts exhibit a wave-shaped pattern which supports the assertion that centers of supersingular <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l"> <mml:semantics> <mml:mi> ℓ </mml:mi> <mml:annotation encoding="application/x-tex">\ell</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -isogeny graphs exhibit the same behavior as those of random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis script l plus 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi> ℓ </mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(\ell +1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -regular graphs. </p>