Compute the $j$-invariant corresponding to a given maximal order in $B_{p,\infty}$

elliptic-curvesisogenyquaternionssagemath

Let $B_{p,\infty}$ is the rational quaternion algebra ramified at $p$ and $\infty$.

By Deuring's correspondence, there is a one to one correspondence between maximal orders in $B_{p, \infty}$ up to isomorphism and supersingular $j$-invariants in $\mathbb{F}_{p^2}$ up to Galois conjugacy.

There are algorithms computing the $j$-invariant corresponding to a given maximal order (with its $\mathbb{Z}$-basis) such as Algorithm 12, EHL+18 of running-time polynomial in $\log p$.

Are there any implementations of these algorithms on Sagemath, Magma, etc?

I know there are some implementation of variations of the KLPT algorithm on Sagemath that compute an ideal with powersmooth norm in a left ideal class (of a maximal order), which is needed in the second step of Algorithm 12, EHL+18. But I suppose this step is for improving running-time only. It's not necessary to have an efficient algorithm like the Algorithm 12, as I only need to compute $j$-invariants when $p$ is small.

Best Answer

The "Deuring for the people" paper provides (among other things) a general and reasonably fast SageMath implementation of the KLPT-based approach. See here for the code.

Related Solutions

Proof of Deuring’s Correspondence

Apologies if this was too brief. We are given a maximal order $\mathcal{O}' \subset B$. Since $\mathcal{O}$ is also a maximal ideal, we may apply Lemma 17.4.7 (in the most recent version, v.0.9.23) to get $I' := \mathcal{O}\mathcal{O}'$ a connecting fractional ideal (indeed, there is a unique genus of maximal orders, 17.4.10), and in particular $\mathcal{O}_{\mathsf{R}}(I') = \mathcal{O}'$. Clearing denominators (section 9.3), there exists $a \in \mathbb{Z}$ such that $a\mathcal{O}' \subseteq \mathcal{O}$, so letting $I := a I' \subseteq \mathcal{O}$ we still have $\mathcal{O}_{\mathsf{R}}(I) = \mathcal{O'}$. Now apply Lemma 42.2.9.

Algebraic Geometry – Implementation of a Constructive Algorithm for Deuring’s Correspondence

All you need to do is define $\operatorname{GF}(17^2)$ explicitly using a concrete irreducible polynomial.

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.4, Release Date: 2021-08-22                     │
│ Using Python 3.9.5. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘
sage: F.<z> = GF(17^2, modulus=x^2+3) 
....: E = EllipticCurve(F, [0,1]) 
....: ker = E(0,1) 
....: phi = E.isogeny(ker) 
....: phi.set_post_isomorphism(phi.codomain().isomorphism_to(E))       
....: (X1, Y1) = phi.rational_maps() 
....: (X2, Y2) = phi.rational_maps() 
....: X3 = X2.subs(x=X1, y=Y1) 
....: Y3 = Y2.subs(x=X1, y=Y1) 
....: (X3, Y3) == E.multiplication_by_m(-3) 
....:                                                                           
True

Best Answer

Related Solutions

Proof of Deuring’s Correspondence

Algebraic Geometry – Implementation of a Constructive Algorithm for Deuring’s Correspondence

Related Question