Radical Isogenies on Montgomery Curves

Abstract

We work on some open problems in radical isogenies. Radical isogenies are formulas to compute chains of N-isogenies for small N and proposed by Castryck, Decru, and Vercauteren in Asiacrypt 2020. These formulas do not need to generate a point of order N generating the kernel and accelerate some isogeny-based cryptosystems like CSIDH. On the other hand, since these formulas use Tate normal forms, these need to transform Tate normal forms to curves with efficient arithmetic, e.g., Montgomery curves. In this paper, we propose radical-isogeny formulas of degrees 3 and 4 on Montgomery curves. Our formulas compute some values determining Montgomery curves, from which one can efficiently recover Montgomery coefficients. And our formulas are more efficient for some cryptosystems than the original radical isogenies. In addition, we prove a conjecture left open by Castryck et al. that relates to radical isogenies of degree 4.

1 Introduction

Recent developments in quantum computers raise the importance of research on post-quantum cryptography (PQC), which is resistant to attacks using quantum computers. Isogeny-based cryptography is one of the promising candidates for PQC. Indeed, an isogeny-based cryptosystem SIKE is one of the 3rd-round alternate candidates in the NIST PQC competition [1]. An advantage of isogeny-based cryptography is that it has smaller public and private keys and ciphertext than other candidates for PQC. On the other hand, the computational costs of encryption and decryption in isogeny-based cryptography are relatively high.

The first isogeny-based cryptosystem was proposed by Couveignes [11] and by Rostovtsev and Stolbunov [20, 22] independently. Their cryptosystem uses an action of the ideal class group of an order of an imaginary quadratic field on a set of ordinary elliptic curves. The action is calculated by isogenies between these elliptic curves. Isogenies between supersingular elliptic curves were brought to cryptography by Charles, Lauter, and Goren [9]. They proposed a cryptographic hash function based on supersingular isogenies. The security of their hash function is based on the hardness of path-finding in supersingular isogeny graphs. Subsequently, Jao and De Feo [16] constructed a key-exchange protocol based on the hardness of a similar problem. Their protocol, SIDH (Supersingular Isogeny Diffie-Hellman), underlies SIKE. Castryck, Lange, Martindale, Panny, and Renes [7] proposed another key-exchange protocol using supersingular isogenies, CSIDH (commutative SIDH). As the scheme of Couveignes and Rostovtsev-Stolbunov, CSIDH uses an action of the ideal class group of an order of an imaginary quadratic field. On the other hand, CSIDH uses a set of $\mathbb {F}_p$-isomorphism classes of supersingular elliptic curves, and the action is calculated by isogenies defined over $\mathbb {F}_p$, where p is a large prime number. There are many protocols based on CSIDH, e.g., signature schemes, SeaSign [12] and CSI-FiSh [2]. In addition, public-key encryption schemes, SiGamal [19] and InSIDH [15], use the group action in CSIDH.

It is known that an isogeny can be computed from points in its kernel by using Vélu’s formulas [24]. For accelerating the computation of isogeny-based cryptosystems, many variants of Vélu’s formulas are considered. There are the formulas on Montgomery curves [10, 13], Edwards curves [8, 17], and Hessian curves [4]. In addition, Bernstein, De Feo, Leroux, and Smith [4] proposed a new algorithm that reduces the cost to compute an isogeny of degree $\ell$ from $O(\ell )$ to $\tilde{O}(\sqrt{\ell })$.

Castryck, Decru, and Vercauteren [6] proposed new formulas, radical isogenies, that compute a chain of isogenies of the same degree. They showed that radical isogenies are more efficient for small degrees than other isogeny formulas. In particular, they showed that radical isogenies accelerate a variant of CSIDH.

In CSIDH, we need to compute isogenies of small degrees over $\mathbb {F}_p$ repeatedly. These isogenies correspond to the actions of ideal classes. To compute an isogeny by Vélu’s formula, we need a generator of the kernel of the isogeny. We obtain the generator from a random point on the domain of the isogeny by scalar multiplication. Let E be an elliptic curve such that (0, 0) on E has order $\ell$ and $\varphi$ an isogeny with kernel generated by (0, 0). Then a radical-isogeny formula gives the codomain $E'$ of $\varphi$ such that an isogeny with kernel generated by (0, 0) on $E'$ is not the dual isogeny $\hat{\varphi }$. The coefficients of $E'$ are in the smallest field containing the coefficients of E and an $\ell$-th root of a rational expression in the coefficients of E. In CSIDH, if $\ell$ is odd, then there is only one $\ell$-th root in $\mathbb {F}_p$. Therefore, we can determine the codomain uniquely and apply radical isogenies iteratively.

On the other hand, if $\ell$ is even, then there are two choices of an $\ell$-th root in $\mathbb {F}_p$, i.e., x and $-x$ have the same $\ell$-th power. Castryck, Decru, and Vercauteren [6] conjectured a radical-isogeny formula of degree 4 that corresponds to the action of an ideal of norm 4 and left it as an open problem.

Another crucial open problem is to reduce the costs of transformations between elliptic curves in radical isogenies. Radical isogenies need to transform an elliptic curve to another curve on which the point (0, 0) has order $\ell$. In particular, the calculation of radical isogenies are as follows:

• 1. Take a starting curve E as a Montgomery curve.

• 2. Find a point $P \in E$ of order $\ell$.

• 3. Transform E to a curve F such that the image of P in F is (0, 0).

• 4. Apply radical isogenies of degree $\ell$ to F iteratively.

• 5. Transform the last codomain of the radical isogenies to a Montgomery curve.

• 6. Calculate isogenies of another degree.

The reason to use Montgomery curves is that Montgomery curves have efficient point addition formulas. Furthermore, if the degree $\ell$ is large, then the formulas on Montgomery curves is more efficient than radical isogenies. The computational costs of the transformations between Montgomery curves and curves used in radical isogenies are relatively high. Therefore, it is important to reduce these costs.

Contribution

We work on some open problems in radical isogenies. In particular, we propose radical-isogeny formulas of degrees 3 and 4 on Montgomery curves and prove the conjecture on radical isogenies of degree 4. Since our formulas have an efficient method to calculate Montgomery coefficients, our formulas reduce the costs of the transformations. Table 1 summarizes the computational costs of our formulas and the formulas in [6] in CSIDH and CSURF, a variant of CSIDH by [5].

Table 1. The costs of radical isogenies in CSIDH and CSURF. The formulas of degree 4 are only applied to CSURF. The letters E, M, A, and I denote exponentiation, multiplication, addition, and inversion on $\mathbb {F}_p$, respectively. The latter $\alpha$ in the table represents $2\mathbf{E} + 2\mathbf{M} + 6\mathbf{A} + \mathbf{I}$ if the exponent of the ideal of norm two is negative, and zero otherwise.

Let E be a Montgomery curve, P a point on E of order 3 with x-coordinate t, and $E'$ a Montgomery curve that is the codomain of an isogeny with kernel generated by P. Our formula of degree 3 gives the x-coordinate of a point of order 3 on $E'$ by a rational expression in a cube root of t. Though the computational cost of our formula is higher than that of the original radical isogeny of degree 3, there is a simple formula to compute the Montgomery coefficient of E from t. Therefore, our formula could improve the computational cost in some cases.

For degree 4, we give a radical-isogeny formula between Montgomery coefficients. In addition, our formula can be simplified by using a modified Montgomery coefficient, which is defined by $4(A + 2)$ or $4(-A + 2)$, where A is a Montgomery coefficient. The computational cost of our formula is slightly less than that of the original radical isogeny of degree 4. In CSURF, we need a transformation between Montgomery curves if the action of an ideal of norm two with a negative exponent. This transformation occurs in half of the keys in CSURF. Although the cost of this transformation is relatively high, it is less than the cost of transformation in the original radical isogenies of degree 4.

In addition, our formula of degree 4 proves the conjecture on radical isogenies of degree 4 by [6]. We obtain this result using the explicit formula to transform a Tate normal form to a Montgomery curve.

Organization

Section 2 introduces mathematical tools and previous works we refer to in this paper. Section 3 gives new formulas over arbitrary fields. In Sect. 4, we attempt to obtain a simpler form of radical isogenies. In particular, we consider a pair of a curve and its $\ell$-cyclic subgroup instead of a pair of a curve and an order-$\ell$ point on it. Section 5 applies the formulas in Sect. 3 to isogenies over $\mathbb {F}_p$. We compare the computational costs of our formulas and that of the original radical isogenies. In addition, we prove the conjecture on radical isogenies of degree 4. Finally, Sect. 6 concludes this paper.

2 Preliminaries

This section gives a summary of the mathematical background of this paper and introduces previous works. We refer the reader to Silverman [21] for Sect. 2.1 and Diamond and Shurman [14] for Sect. 2.2.

2.1 Elliptic Curves and Isogenies

Let K be a field. An elliptic curve over K is a smooth projective curve over K of genus one with a specified base point over K. For an elliptic curve E, we denote its specified base point by $O_E$. An elliptic curve E has an abelian group structure with identity $O_E$. For an extension field L over K, we denote the set of points on E defined over L by E(L). Then E(L) is a subgroup of E. For an integer n, we denote the multiplication-by-n map on an elliptic curve by [n]. The n-torsion subgroup of E is $\{P \in E \mid [n]P = O_E\}$ and denoted by E[n]. If the characteristic $\mathrm {char}(K)$ is coprime to n, we can define the Tate pairing, which is a bilinear map

$$\begin{aligned} t_n: E(K)[n] \times E(K)/nE(K) \rightarrow K^\times /(K^\times )^n, \end{aligned}$$

where E(K)[n] is the set of points defined over K in E[n].

Let E and $E'$ be elliptic curves over K. An isogeny $\varphi : E \rightarrow E'$ is a non-constant morphism such that $\varphi (O_E) = O_{E'}$. The isogeny $\varphi$ induces an injection $\varphi ^*: \overline{K}(E') \rightarrow \overline{K}(E)$ between the function fields of the curves. The degree of $\varphi$ is the degree of the field extension $\overline{K}(E)/\varphi ^*(\overline{K}(E'))$. We denote this by $\deg \varphi$. We say that $\varphi$ is separable (resp. inseparable) if the extension $\overline{K}(E)/\varphi ^*(\overline{K}(E'))$ is separable (resp. inseparable). The degree of $\varphi$ is finite, and the cardinality of $\ker \varphi$ is less than or equal to $\deg \varphi$. Furthermore, if $\varphi$ is separable, then we have $\#\ker \varphi = \deg \varphi$. Conversely, given a finite subgroup $\varPsi$ of E, there exists a separable isogeny with kernel $\varPsi$. In addition, the codomain of an isogeny with kernel $\varPsi$ is unique up to isomorphism. We denote the codomain by $E/\varPsi$. We call a separable isogeny whose kernel is an n-cyclic group an n-isogeny. For an isogeny $\varphi : E \rightarrow E'$, there exists the unique isogeny $\hat{\varphi }: E' \rightarrow E$ such that $\hat{\varphi }\circ \varphi$ is the multiplication-by-$\deg \varphi$ map on E. We call $\hat{\varphi }$ the dual isogeny of $\varphi$. We have $\deg \hat{\varphi } = \deg \varphi$ and that the dual isogeny of $\hat{\varphi }$ is $\varphi$.

2.2 Congruence Subgroups and Enhanced Elliptic Curves

Let N be a positive integer. The principal congruence subgroup of level N is

$$\begin{aligned} \varGamma (N) = \left\{ \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} \in \mathrm {SL}_2(\mathbb {Z})\mid \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} \equiv \begin{pmatrix} 1 &{} 0\\ 0 &{} 1 \end{pmatrix} \pmod {N} \right\} , \end{aligned}$$

where $\mathrm {SL}_2(\mathbb {Z})$ is the special linear group of degree 2 over $\mathbb {Z}$, i.e., the set of 2-by-2 matrices over $\mathbb {Z}$ having determinant 1. A congruence subgroup of level N is a subgroup of $\mathrm {SL}_2(\mathbb {Z})$ that includes $\varGamma (N)$. We define two congruence subgroups

$$\begin{aligned}&\varGamma _0(N) = \left\{ \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} \in \mathrm {SL}_2(\mathbb {Z})\mid \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} \equiv \begin{pmatrix} * &{} *\\ 0 &{} * \end{pmatrix} \pmod {N} \right\} ,\\&\varGamma _1(N) = \left\{ \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} \in \mathrm {SL}_2(\mathbb {Z})\mid \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} \equiv \begin{pmatrix} 1 &{} *\\ 0 &{} 1 \end{pmatrix} \pmod {N} \right\} , \end{aligned}$$

where $*$ means unspecified. We define an action of $\mathrm {SL}_2(\mathbb {Z})$ on the upper half plane $\mathcal {H}$ in $\mathbb {C}$ by

$$\begin{aligned} \begin{pmatrix} a &{} b\\ c &{} d \end{pmatrix} z = \frac{az + b}{cz + d}. \end{aligned}$$

Then we define sets $Y(N) = \varGamma (N)\backslash \mathcal {H}$, $Y_0(N) = \varGamma _0(N)\backslash \mathcal {H}$, and $Y_1(N) = \varGamma _1(N)\backslash \mathcal {H}$. Furthermore, we can extend the action of $\mathrm {SL}_2(\mathbb {Z})$ to $\mathcal {H}^{*} := \mathcal {H}\cup \mathbb {Q}\cup \{\infty \}$, and define $X(N) = \varGamma (N)\backslash \mathcal {H}^*$, $X_0(N) = \varGamma _0(N)\backslash \mathcal {H}^*$, and $X_1(N) = \varGamma _1(N)\backslash \mathcal {H}^*$. The sets $X(N),\ X_0(N)$, and $X_1(N)$ have structures of compact Riemann surfaces and are called Modular curves. The points in $Y(N),\ Y_0(N)$, and $Y_1(N)$ correspond to enhanced elliptic curves over $\mathbb {C}$. An enhanced elliptic curve for $\varGamma _0(N)$ is an ordered pair (E, C), where E is an elliptic curve over $\mathbb {C}$ and C is an N-cyclic subgroup of E. Two enhanced elliptic curves (E, C) and $(E', C')$ for $\varGamma _0(N)$ are equivalent if there exists an isomorphism $E \rightarrow E'$ that takes C to $C'$. We write this as $(E, C) \sim (E', C')$. The set of equivalence classes is denoted by

$$S_0(N) = \{\text{ enhanced } \text{ elliptic } \text{ curves } \text{ for } \varGamma _0(N)\} / \sim .$$

The equivalence class of an enhanced elliptic curve (E, C) is denoted by [E, C]. We define an enhanced elliptic curve for $\varGamma _1(N)$ as a pair of an elliptic curve over $\mathbb {C}$ and a point of order N on the curve, and an enhanced elliptic curve for $\varGamma (N)$ as a pair of an elliptic curve over $\mathbb {C}$ and an ordered pair of points that generates the N-torsion subgroup of the curve. Sets $S_1(N)$ and S(N) are defined similarly to $S_0(N)$. Then there are one-to-one correspondences

$$\begin{aligned} Y_0(N) \leftrightarrow S_0(N),\ Y_1(N) \leftrightarrow S_1(N),\ \text{ and } Y(N) \leftrightarrow S(N). \end{aligned}$$

In these correspondences, the natural projections in residues correspond to the natural projection in enhanced elliptic curves. For example, consider the natural projection $Y_0(p) \rightarrow Y(1)$ for a prime p. This projection corresponds to omitting the p-cyclic subgroup from an enhanced elliptic curve. Here, the index $[\varGamma (1):\varGamma _0(p)] = p + 1$ corresponds to the number of p-cyclic subgroups of an elliptic curve.

For an arbitrary algebraically closed field, we can define enhanced elliptic curves and the sets $S_0(N),\ S_1(N)$, and S(N) in the same way. We use the same notation for these as over $\mathbb {C}$.

2.3 Montgomery Curves

We give the definition and basic properties of Montgomery curves [18]. In this subsection, we let K be a field with $\mathrm {char}(K) \ne 2$.

A Montgomery curve over K is an elliptic curve E defined by $y^2 = x^3 + Ax^2 + x,$ where $A \in K$ such that $A^2 \ne 4$. We call A the Montgomery coefficient of E. We denote a point of x-coordinate $a \in K$ on a Montgomery curve by $(a, -)$. The j-invariant of E is

$$\begin{aligned} 256\frac{(A^2 - 3)^3}{A^2 - 4}. \end{aligned}$$

This formula means that there are exactly six isomorphic Montgomery curves over $\overline{K}$ (counted with multiplicity). The number six comes from the index $[\varGamma _0(1):\varGamma _0(4)]$. In other words, a Montgomery curve represents a class in $S_0(4)$. To explain this fact, we define a specified 4-cyclic subgroup of a Montgomery curve. By the arithmetic in Montgomery curves (see [18]), we obtain that the point (0, 0) on a Montgomery curve has order 2, and the x-coordinates of its halves are 1 and $-1$. For a Montgomery curve E, we denote the cyclic subgroup of E generated by $(1, -) \in E$ by $C_{E}^{(4)}$. Then we have the following.

Proposition 1

Let E and $E'$ be two Montgomery curves over K of Montgomery coefficients A and $A'$, respectively. Then $(E, C_{E}^{(4)}) \sim (E', C_{E'}^{(4)})$ if and only if $A = A'$. Furthermore, we have $(E, \langle {(0,0)}\rangle ) \sim (E', \langle {(0,0)}\rangle )$ if and only if $A^2 = A'^2$.

Proof

From Proposition III.3.1 in [21], every isomorphism between Montgomery curves is of the form $(x, y) \mapsto (u^2x + r, u^3y)$, where $r \in \overline{K}$ and $u \in \overline{K}^\times$.

Let $\iota : E \rightarrow E'$ be an isomorphism that preserves (0, 0). Then we have $\iota (x, y) = (u^2x, u^3y)$, where $u \in \overline{K}$ such that $u^4 = 1$, and $A' = u^2A$. Therefore, we conclude $A' = \pm A$, i.e., $A^2 = A'^2$. In addition, if $\iota$ takes $C_{E}^{(4)}$ to $C_{E'}^{(4)}$, then $\iota ((1, -)) = (1, -)$ thus $u^2 = 1$. This means $A = A'$.

Conversely, we assume $A' = -A$. Then there exists an isomorphism $\iota : E \rightarrow E',\ (x, y) \mapsto (-x, iy)$, where i is a square root of $-1$ in $\overline{K}$. Since $\iota ((0,0)) = (0,0)$, we have $(E, \langle {(0,0)}\rangle ) \sim (E', \langle {(0,0)}\rangle )$.    $\square$

It is easy to verify that for an enhanced elliptic curve (E, C) over $\overline{K}$ for $\varGamma _0(4)$, there exist a Montgomery curve $E'$ and an isomorphism $E \rightarrow E'$ that takes C to $C_{E'}^{(4)}$. Therefore, we can define a bijection $A : S_0(4) \rightarrow \overline{K}\backslash \{\pm 2\}$ by sending [E, C] to the Montgomery coefficient of a Montgomery curve in the class [E, C]. The following corollary summarizes our discussion.

Corollary 2

We have the following commutative diagram

where the top arrows are the natural projections, and the bottom arrows are defined by

$$A \mapsto A^2 \text{ and } a \mapsto 256\frac{(a - 3)^3}{a - 4}.$$

2.4 Vélu’s Formulas

Vélu [24] gave explicit formulas for isogenies between elliptic curves represented as Weierstrass forms. Vélu’s formulas take an elliptic curve E and a finite subgroup C of E as input and output an elliptic curve $E'$ and a separable isogeny $\varphi : E \rightarrow E'$ with kernel C. We display some of the variants of Vélu’s formulas that we need later.

Proposition 3

(Theorem 1 in [10]). Let K be a field with $\mathrm {char}(K) \ne 2$, E a Montgomery curve over K of coefficient A, and P a point on E of order $\ell = 2d + 1$. We write the x-coordinate of [i]P for $i = 1,\dots ,d$ as $x_i$. Then the Montgomery curve $y^2 = x^3 + A'x^2 + x$ with

$$\begin{aligned} A' = \left( 6\sum _{i=1}^d\left( \frac{1}{x_i} - x_i\right) + A\right) \left( \prod _{i=1}^dx_i\right) ^2 \end{aligned}$$

(1)

is the codomain of a separable isogeny $\varphi$ with kernel $\langle {P}\rangle$, which is defined by

$$\begin{aligned} \varphi : (x, y) \mapsto \left( f(x), yf'(x)\prod _{i=1}^dx_i\right) , \end{aligned}$$

(2)

where

$$\begin{aligned} f(x) = x\prod _{i=1}^d\left( \frac{xx_i-1}{x-x_i}\right) ^2, \end{aligned}$$

(3)

and $f'(x)$ is its derivative.

Note that $\varphi$ in Proposition 3 sends $(1, -)$ on E to $(1, -)$ on the codomain. As we showed in Sect. 2.3, the coefficient $A'$ is unique as we take an isogeny with this property.

For an isogeny whose kernel includes the point (0, 0), we need to choose a Montgomery coefficient of its codomain. Jao and De Feo [13] gave a formula for 2-isogenies that sends $(1, -)$ to (0, 0).

Proposition 4

([13]). Let K be a field with $\mathrm {char}(K) \ne 2$ and E a Montgomery curve over K of coefficient A. Then the Montgomery curve $y^2 = x^3 + A'x^2 + x$ with

$$\begin{aligned} A' = \frac{A + 6}{2\alpha }, \end{aligned}$$

(4)

where $\alpha$ is a square root of $A + 2$, is the codomain of a 2-isogeny $\varphi$ that sends $(1, -)$ to (0, 0), which is defined by

$$\begin{aligned} \varphi : (x, y) \mapsto \left( \frac{(x-1)^2}{2\alpha x}, \frac{1}{\beta ^3}y\left( 1-\frac{1}{x^2}\right) \right) , \end{aligned}$$

(5)

where $\beta$ is a square root of $2\alpha$.

Note that there are two choices of a Montgomery coefficient of the codomain, which corresponds to the sign of the square root $\alpha$. The sign of the square root $\beta$ is not essential since the change of the sign corresponds to the composition with the multiplication by $-1$.

2.5 Radical Isogenies

Let N be a positive integer, K a field with $\mathrm {char}(K) \not \mid N$, E an elliptic curve over K, and P a point in E(K) of order N. Then there exists an isogeny $\varphi : E \rightarrow E/\langle {P}\rangle$ with kernel $\langle {P}\rangle$. We can choose a model of $E/\langle {P}\rangle$ to be defined over K. Let $E'$ be such a model. Let $P'$ be a point on $E'$ such that $\hat{\varphi }(P') = P$. Castryck, Decru, and Vercauteren [6] showed that $P'$ is defined over $K(\root N \of {\rho })$, where $\rho$ is a representative of the Tate pairing $t_N(P, -P)$. The N choices of an N-th root of $\rho$ correspond to N-isogenies different from $\hat{\varphi }$. By taking models of E and $E/\langle {P}\rangle$ such that P and $P'$ are (0, 0), they gave explicit formulas to compute $E/\langle {P}\rangle$ from E, and called these radical isogenies. A radical isogeny can be seen as a map on $S_1(N)$; $(E, (0, 0)) \mapsto (E/\langle {(0,0)}\rangle , (0,0))$. For curve models, they used Tate normal forms [23] for $N \ge 4$. We write some of their formulas that we refer to later.

$\boldsymbol{N = 3}$. We use the model $E: y^2 + a_1xy + a_3y = x^3$ and $P = (0,0)$. Then a model of $E/\langle {P}\rangle$ such that $P' = (0,0)$ is $E': y^2 + a'_1xy + a'_3y = x^3$ with

$$\begin{aligned} a'_1 = -6\alpha + a_1 \text{ and } a'_3 = 3a_1\alpha ^2 - a_1^2\alpha + 9a_3, \end{aligned}$$

(6)

where $\alpha$ is a cube root of $-a_3$.

$\boldsymbol{N = 4}$. We use the Tate normal form $E: y^2 + xy - by = x^3 - bx^2$ and $P = (0,0)$. Then a Tate normal form of $E/\langle {P}\rangle$ such that $P' = (0,0)$ is $E': y^2 + xy - b'y = x^3 - b'x^2$ with

$$\begin{aligned} b' = -\frac{\alpha (4\alpha ^2 + 1)}{(2\alpha + 1)^4}, \end{aligned}$$

(7)

where $\alpha$ is a fourth root of $-b$.

$\boldsymbol{N = 5}$. We use the Tate normal form $E: y^2 + (1 - b)xy - by = x^3 - bx^2$ and $P = (0,0)$. Then a Tate normal form of $E/\langle {P}\rangle$ such that $P' = (0,0)$ is $E': y^2 + (1 - b')xy - b'y = x^3 - b'x^2$ with

$$\begin{aligned} b' = \alpha \frac{\alpha ^4 + 3\alpha ^3 + 4\alpha ^2 + 2\alpha + 1}{\alpha ^4 - 2\alpha ^3 + 4\alpha ^2 - 3\alpha + 1}, \end{aligned}$$

(8)

where $\alpha$ is a fifth root of b.

3 Radical-Isogeny Formulas on Montgomery Curves

In this section, we introduce radical-isogeny formulas of degrees 3 and 4 on Montgomery curves. In addition, we give some consideration for that of degree $\ge 5$.

3.1 Degree 3

Let K be a field with $\mathrm {char}(K) \ne 2, 3$.

As we showed in Sect. 2.2, a Montgomery coefficient represents a class in $S_0(4)$. A 3-cyclic subgroup of a Montgomery curve is represented by the x-coordinate of its generator. Therefore, a class in $S_0(12)$ can be represented by a pair of a Montgomery coefficient and the x-coordinate of a point of order 3. However, the genus of $X_0(12)$ is zero, so a class in $S_0(12)$ can be parametrized by one variable. Indeed, we show that the x-coordinate of a point of order 3 determines the Montgomery coefficient of the curve on which the point is.

From the arithmetic in Montgomery curves, we obtain the 3rd division polynomial of the Montgomery curve with coefficient $A \in K$:

$$\begin{aligned} x^4 + \frac{4}{3}Ax^3 + 2x^2 - \frac{1}{3}. \end{aligned}$$

Let t be the x-coordinate of a point of order 3 on the Montgomery curve with coefficient A. Then we have

$$\begin{aligned} A = \frac{-3t^4 -6t^2 + 1}{4t^3}. \end{aligned}$$

(9)

From the condition that $A \ne \pm 2, \infty$, we have $t \ne 0, \pm 1, \pm \frac{1}{3}$. For $t \in \overline{K}\backslash \{0, \pm 1, \pm \frac{1}{3}\}$, we denote the Montgomery curve with coefficient defined by (9) by $E_t$, and the 3-cyclic subgroup of $E_t$ generated by $(t, -)$ by $C_{t}^{(3)}$. The subgroup $C_{E_t}^{(4)} + C_{t}^{(3)} := \{P + Q \mid P \in C_{E_t}^{(4)}, Q \in C_{t}^{(3)}\}$ is cyclic of order 12. Then we have an analogue of Proposition 1.

Proposition 5

The map

$$T: \overline{K}\backslash \left\{ 0, \pm 1, \pm \frac{1}{3}\right\} \rightarrow S_0(12),\ t \mapsto [E_t, C_{E_t}^{(4)} + C_{t}^{(3)}]$$

is a well-defined bijection.

Proof

As we explained above, the map T is well-defined.

First, we show the surjectivity. Let (E, C) be an enhanced elliptic curve for $\varGamma _0(12)$ over $\overline{K}$. We decompose C to $C_3 + C_4$, where $C_3$ is cyclic of order 3 and $C_4$ is cyclic of order 4. From Proposition 1, there exists a Montgomery curve $E'$ such that $(E', C_{E'}^{(4)}) \sim (E, C_4)$. Let $\iota : E \rightarrow E'$ be an isomorphism taking $C_4$ to $C_{E'}^{(4)}$, and t the x-coordinate of a generator of $\iota (C_3)$. Then $t \ne 0, \pm 1, \pm \frac{1}{3}$ and $E' = E_t$. Therefore we have $(E, C) \sim (E_t, C_{E_t}^{(4)}+C_{t}^{(3)})$.

Next, we show the injectivity. Let t and $t'$ be elements in $\overline{K}\backslash \left\{ 0, \pm 1, \pm \frac{1}{3}\right\}$ such that there exists an isomorphism $\iota : E_t \rightarrow E_{t'}$ taking $C_{E_{t}}^{(4)} + C_{t}^{(3)}$ to $C_{E_{t'}}^{(4)} + C_{t'}^{(3)}$. From the proof of Proposition 1, we have $E_t = E_{t'}$ and $\iota ((x,y)) = (x, y)$ or $(x, -y)$. Therefore, we conclude $t = t'$.    $\square$

As in the case of Montgomery curves, we have the following corollary.

Corollary 6

We have the following commutative diagram

where the top arrow is the natural projection, the left vertical arrow is the inverse of the map in Proposition 5, and the bottom arrow is defined by

$$t \mapsto \frac{-3t^4 -6t^2 + 1}{4t^3}.$$

Using this parametrization of $S_0(12)$, we can derive a radical-isogeny formula of degree 3.

Theorem 7

Let $t \in \overline{K}\backslash \{0,\pm 1, \pm \frac{1}{3}\}$, E be a Montgomery curve over $\overline{K}$, and $\varphi : E_t \rightarrow E$ an isogeny taking $C_{E_t}^{(4)}$ to $C_{E}^{(4)}$ with kernel $C_{t}^{(3)}$. Then the x-coordinate of a generator of $\ker \hat{\varphi }$ is $-\frac{1}{3t}$, and the x-coordinates of other points of order 3 on E are

$$\begin{aligned} 3t\alpha ^2 + (3t^2-1)\alpha + 3t^3 - 2t, \end{aligned}$$

(10)

where $\alpha$ is a cube root of $t(t^2-1)$.

Proof

From Proposition 3, the Montgomery coefficient of E is

$$\begin{aligned} \frac{-27t^4 + 18t^2 + 1}{4t}. \end{aligned}$$

The 3rd division polynomial of E is decomposed as

$$\begin{aligned} \left( x + \frac{1}{3t}\right) (x^3 + (-9t^3 + 6t)x^2 + 3t^2x - t). \end{aligned}$$

(11)

It is easy to verify that $(-\frac{1}{3t}, -)$ on E generates the kernel of the dual isogeny $\hat{\varphi }$.

Let $P = (t, -)$ on $E_t$. An easy calculation shows that the y-coordinate of P is $\frac{t^2-1}{2\beta }$, where $\beta$ is a square root of t. By the theory of radical isogenies (see Sect. 3 in [6]), a root of the latter factor in (11) has a rational expression in $\beta$ and a cube root of the Tate pairing $t_3(P, -P)$. The isogeny $\varphi$ is unchanged by replacing P with $-P$, i.e., $\beta$ with $-\beta$. Therefore, the root should be in a radical extension of $\mathbb {Q}(t)$ of degree 3. Indeed, the Tate paring can be computed as

$$\begin{aligned} t_3(P, -P) = t(t^2 - 1) \bmod {\mathbb {Q}(\beta )^{\times 3}}. \end{aligned}$$

Let $\alpha$ be a cube root of $t(t^2-1)$. Then the latter factor in (11) decomposes into linear factors in $\mathbb {Q}(t, \alpha )$ and has a root of the form (10). This proves the theorem.    $\square$

The computational cost of this formula is worse than that of the original radical-isogeny formula (6). An advantage of this formula is that one can use the simple formula (9) to calculate the Montgomery coefficient from the representation t. In isogeny-based cryptosystems, Montgomery curves are used because of computational efficiency. Therefore, we need transformation between a Montgomery curve and a curve used in radical isogenies. In the case of (6), the transformation needs calculating radicals. On the other hand, our transformation formula (9) does not need any radicals. We discuss the detail of this point in Sect. 5.3.

3.2 Degree 4

Let K be a field with $\mathrm {char}(K) \ne 2$.

Since a Montgomery coefficient represents a class in $S_0(4) = S_1(4)$, it must be true that there exists a radical-isogeny formula of degree 4 between Montgomery coefficients. Indeed, we have the following.

Theorem 8

Let E be a Montgomery curve with coefficient $A \in K$, $E'$ a Montgomery curve, $\varphi : E \rightarrow E'$ an isogeny with kernel $C_{E}^{(4)}$, and $\psi$ an isogeny from $E'$ with kernel $\langle {(0,0)}\rangle$. If the kernel of the composition $\psi \circ \varphi$ is cyclic, then the Montgomery coefficient $A'$ of $E'$ is

$$\begin{aligned} \frac{(\beta +2)^4}{4\beta (\beta ^2+4)} - 2, \end{aligned}$$

(12)

where $\beta$ is a fourth root of $4(A+2)$.

Proof

We decompose $\varphi$ into the composition of two 2-isogenies $\varphi _2\circ \varphi _1$. We can assume that $\varphi _1$ takes $(1, -)$ to (0, 0). Let $A''$ be the Montgomery coefficient of $\varphi _1(E)$. From Proposition 4, we have

$$\begin{aligned} A'' + 2 = \frac{(\alpha + 2)^2}{2\alpha }, \end{aligned}$$

(13)

where $\alpha$ is a square root of $A + 2$. Again, from Proposition 4, The Montgomery coefficient of $E'$ is

$$\begin{aligned} \frac{((\alpha + 2)/\beta + 2)^2}{2(\alpha + 2)/\beta } - 2, \end{aligned}$$

(14)

where $\beta$ is a square root of $2\alpha$, i.e., a fourth root of $4(A + 2)$. We can obtain (12) by an easy calculation.    $\square$

By putting $a = 4(A + 2)$ and $a' = 4(A' + 2)$, we have a simpler formula

$$\begin{aligned} a' = \frac{(\beta +2)^4}{\beta (\beta ^2+4)}, \end{aligned}$$

(15)

where $\beta$ is a fourth root of a. The computational cost of this formula is slightly less than that of the original radical-isogeny formula (7). In addition, as in degree 3, it is easy to transform our new representation a into the Montgomery coefficient.

3.3 Degree $\ge 5$

We could not generalize our method to the case that $N \ge 5$. Since the genus of $X_0(4N)$ is greater than 0 for $N \ge 5$, we cannot represent an element in $S_0(4N)$ by one parameter. Furthermore, we have $S_0(N) \ne S_1(N)$ for $N \ge 5$, unlike in the case that $N = 3$ or 4. As we discuss in the next section, we cannot obtain radical-isogeny formulas of degree N for a model of $S_0(N)$ for $N \ge 5$. Therefore, we have to work on a model of $S_1(N)$. A natural parametrization for the case that $N \ge 5$ is a pair of a Montgomery coefficient and the x-coordinate of a point of order N. However, even for the case that $N = 5$, the calculation is too complicated, and we could not derive any formula.

4 Consideration to Formulas on $S_0(N)$

As we stated in Sect. 2.5, radical isogenies of degree N can be seen as a map on $S_1(N)$. For example, for $N = 3$, consider two curves $E: y^2 + a_1xy + a_3y = x^3$ and $E': y^2 + a'_1xy + a'_3y = x^3$. In these curves, the point (0, 0) has order 3. It is easy to verify that $(E, (0,0)) \sim (E', (0,0))$ if and only if $a_1^3/a_3 = {a'_1}^3/a'_3$. Note that $a_3, a'_3 \ne 0$ since the curves are smooth. By putting $T = a_1^3/a_3$ and $T' = {a'_1}^3/a'_3$, one can transform (6) to

$$\begin{aligned} T' = \frac{(\beta - 6)^3}{-\beta ^2 + 3\beta - 9}, \end{aligned}$$

where $\beta$ is a cube root of $-T$. (This formula is more costly than (6) because of the inversion and the cubic calculation.)

As we stated in the previous section, we have $S_0(N) = S_1(N)$ for $N \le 4$ since there is the isomorphism $[-1]$. For the case that $N \ge 5$, we could obtain a simpler isogeny formula on a parametrization of $S_0(N)$ than that of $S_1(N)$. However, in general, we cannot obtain radical formulas on a parametrization of $S_0(N)$. We explain this in the following.

Consider the case that $N = 5$. Let K be a field with $\mathrm {char}(K) \ne 5$, and consider two elliptic curves over K defined by

$$\begin{aligned}&E: y^2 + (1-b)xy - by = x^3 - bx,\\&E': y^2 + (1-b')xy - b'y = x^3 - b'x. \end{aligned}$$

These curves are in Tate normal form, and the points (0, 0) on these curves have order 5. The cyclic subgroup of E generated by (0, 0) is

$$\{O_E, (0,0), (b, b^2), (b, 0), (0, b)\}.$$

From this, it is easy to verify that $(E, (0,0)) \sim (E', (0,0))$ if and only if $b = b'$ and that $(E, \langle {(0,0)}\rangle ) \sim (E', \langle {(0,0)}\rangle )$ if and only if $b = b'$ or $b = -\frac{1}{b'}$, i.e., $\frac{b^2-1}{b} = \frac{{b'}^2-1}{b'}$. Therefore, $\frac{b^2-1}{b}$ is a parametrization of $S_0(5)$. Note that b and $-\frac{1}{b}$ are the roots of $x^2 -\frac{b^2-1}{b}x - 1$.

Let E and $E'$ be elliptic curves defined by the equations above. We define $\beta = \frac{b^2-1}{b}$ and $\beta ' = \frac{{b'}^2-1}{b'}$. From the radical-isogeny formula (8), we have $\mathbb {Q}(b') = \mathbb {Q}(\root 5 \of {b})$. In this setting, we show that $\beta ' := \frac{{b'}^2-1}{b'}$ does not have any rational expression in a fifth root of any element in $\mathbb {Q}(\beta )$.

Fig. 1.

The tower of field extensions

As we mentioned above, the field extension $\mathbb {Q}(b) / \mathbb {Q}(\beta )$ is of degree 2. Let $\zeta _5 \in \mathbb {C}$ be a primitive fifth root of unity. By adjoining $\zeta _5$ to the field extension $\mathbb {Q}(b') / \mathbb {Q}(\beta )$, we obtain the Galois extension $\mathbb {Q}(\zeta _5)(b') / \mathbb {Q}(\zeta _5)(\beta )$ of degree 10. The Galois group $\mathrm {Gal}(\mathbb {Q}(\zeta _5)(b') / \mathbb {Q}(\zeta _5)(\beta ))$ is generated by automorphisms $\sigma : b' \mapsto -\frac{1}{b'}$ and $\tau : b' \mapsto \zeta _5b'$. The fixed field of $\sigma$ is $\mathbb {Q}(\zeta _5)(\beta ')$, and that of $\tau$ is $\mathbb {Q}(\zeta _5)(b)$. It is easy to verify that $\tau ^{-1}\sigma \tau \ne \sigma$. Therefore, the group $\langle {\sigma }\rangle$ is not a normal subgroup of $\mathrm {Gal}(\mathbb {Q}(\zeta _5)(b') / \mathbb {Q}(\zeta _5)(\beta ))$, i.e., the extension $\mathbb {Q}(\zeta _5)(\beta ')/\mathbb {Q}(\zeta _5)(\beta )$ is not a Galois extension. This means that $\beta '$ cannot be expressed as any rational expression in any element in $\mathbb {Q}(\zeta _5)(\beta )$. The diagram in Fig. 1 summarizes the discussion.

To obtain a radical-isogeny formula for $S_0(N)$, we need to find a parametrization for $S_0(N)$ that makes the bottom extension in the diagram in Fig. 1 a Galois extension. We do not have any result for the existence of such parametrization. However, it seems to be complicated to find it. We leave this as an open problem.

5 Application to Cryptography

In this section, we consider the application of our formulas in Sect. 3 to CSIDH and its variants.

CSIDH uses the action of the ideal class group of an order of an imaginary quadratic field on supersingular elliptic curves. The action is calculated by isogenies defined over a finite prime field $\mathbb {F}_p$. Therefore, we consider formulas of such isogenies.

Let $\mathcal {O}$ be $\mathbb {Z}[\sqrt{-p}]$ or $\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}]$, and $\mathcal {E}\ell \ell _p(\mathcal {O})$ the set of $\mathbb {F}_p$-isomorphism classes of supersingular elliptic curves over $\mathbb {F}_p$ whose $\mathbb {F}_p$-endomorphism ring is isomorphic to $\mathcal {O}$. Note that the p-th power Frobenius endomorphism $\pi$ corresponds to $\sqrt{-p}$ or $-\sqrt{-p}$. We identify the $\mathbb {F}_p$-endomorphism ring of a curve with $\mathcal {O}$ under the former isomorphism. If $\mathcal {E}\ell \ell _p(\mathcal {O})$ is nonempty, then the ideal class group $\mathrm {cl}(\mathcal {O})$ acts freely and transitively on $\mathcal {E}\ell \ell _p(\mathcal {O})$ (Theorem 7 in [7]). The group action is defined as follows: Let $E \in \mathcal {E}\ell \ell _p(\mathcal {O})$, and $[\mathfrak {a}]$ be an ideal class in $\mathrm {cl}(\mathcal {O})$ represented by an integral ideal $\mathfrak {a}$. Then the action of $[\mathfrak {a}]$ on E is defined by $[\mathfrak {a}] * E = E/E[\mathfrak {a}]$, where $E[\mathfrak {a}]$ is the $\mathfrak {a}$-torsion subgroup of E, which is defined by $\{P \in E \mid \alpha (P) = O_E \text{ for } \text{ all } \alpha \in \mathfrak {a}\}$, and we take an isogeny with kernel $E[\mathfrak {a}]$ defined over $\mathbb {F}_p$. We denote the ideal in $\mathcal {O}$ generated by a, b by (a, b) and the ideal class of (a, b) by [a, b].

We restrict our attention to the case that $p \equiv 3 \pmod {4}$ since there is no supersingular Montgomery curve over $\mathbb {F}_p$ if $p \equiv 1 \pmod {4}$ [5]. We fix a square root of $-1$ in $\mathbb {F}_{p^2}$ and denote it by i. Note that $i \notin \mathbb {F}_p$ in our case.

5.1 Degree-3 Isogenies

Assume that $3 \mid p + 1$ so that a supersingular elliptic curve over $\mathbb {F}_p$ has an $\mathbb {F}_p$-rational point of order 3. Then the map $\mathbb {F}_p \rightarrow \mathbb {F}_p; a \mapsto a^3$ is bijective. Therefore, there is only one cube root of an element of $\mathbb {F}_p$. For $a \in \mathbb {F}_p$, the cube root of a in $\mathbb {F}_p$ is computed by the exponentiation $a^e$, where e is an integer such that $e \equiv 3^{-1} \pmod {p - 1}$.

Let E be a Montgomery curve in $\mathcal {E}\ell \ell _p(\mathcal {O})$. The role of 3-isogenies in CSIDH is to compute the actions of prime ideals $(3, \sqrt{-p} - 1)$ and $(3, \sqrt{-p} + 1)$. The torsion subgroup $E[3, \sqrt{-p} - 1]$ is generated by a point P of order 3 such that $\pi (P) = P$, and $E[3, \sqrt{-p} + 1]$ is generated by a point Q of order 3 such that $\pi (Q) = -Q$. Note that the x-coordinates of P and Q are in $\mathbb {F}_p$. We can use Theorem 7 to compute the actions of these ideals.

Corollary 9

Let E be a Montgomery curve in $\mathcal {E}\ell \ell _p(\mathcal {O})$, and t the x-coordinate of a generator of $E[3, \sqrt{-p} - 1]$ (resp. $E[3, \sqrt{-p} + 1]$). Then $[3, \sqrt{-p} - 1] * E$ (resp. $[3, \sqrt{-p} + 1]*E$) can be defined as a Montgomery curve $E'$ over $\mathbb {F}_p$ such that the x-coordinate of a generator of $E'[3, \sqrt{-p} - 1]$ (resp. $E'[3, \sqrt{-p} + 1]$) is

$$\begin{aligned} 3t\alpha ^2 + (3t^2-1)\alpha + 3t^3 - 2t, \end{aligned}$$

(16)

where $\alpha$ is the cube root of $t(t^2-1)$ in $\mathbb {F}_p$.

Proof

We prove the case for $E[3, \sqrt{-p} - 1]$. The other case can be proved in the same way.

Let $t'$ be an element in $\mathbb {F}_p$ defined by the equation (16), and $E'$ a Montgomery curve that has an order-3 point with x-coordinate $t'$. From Theorem 7, $E'$ is the codomain of the isogeny $\varphi$ in Proposition 3 with kernel generated by $(t, -)$. Because $t \in \mathbb {F}_p$, the isogeny $\varphi$ is defined over $\mathbb {F}_p$. Therefore, $E'$ is a representative of the $\mathbb {F}_p$-isomorphism class $[3, \sqrt{-p} - 1] * E$. Because $\alpha$ is only one cube root of $t(t^2-1)$ in $\mathbb {F}_p$, the element $t'$ is only one element such that the point $(t', -)$ on $E'$ has order 3 and generates the kernel of an isogeny different from $\hat{\varphi }$. This means that $t'$ is the x-coordinate of a generator of $E'[3, \sqrt{-p} - 1]$.    $\square$

A Formula for Montgomery$^\mathbf{-}$ Curves. A Montgomery$^{-}$ curve over a field K with $\mathrm {char}(K) \ne 2$ is an elliptic curve defined by $y^2 = x^3 + Ax^2 - x$, where $A \in K$ such that $A^2 \ne -4$.

Castryck and Decru [5] introduced Montgomery$^{-}$ curves for a model of a variant of CSIDH they proposed, CSURF. CSURF uses Montgomery$^{-}$ curves since there is a one-to-one correspondence between Montgomery$^-$ coefficients of supersingular elliptic curves and classes in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$.

The arithmetic and isogeny formulas on Montgomery$^-$ curves are given in [5]. Like Montgomery curves, the x-coordinate t of a point of order 3 on a Montgomery$^-$ curve determines the Montgomery$^-$ coefficient A. Indeed, we have

$$\begin{aligned} A = \frac{-3t^4 + 6t^2 + 1}{4t^3}. \end{aligned}$$

(17)

From the conditions $A^2 \ne -4$ and $A \ne \infty$, we have $t \ne 0, \pm i, \pm \frac{i}{3}$. For $t \in \mathbb {F}_p \backslash \{0\}$, we denote the Montgomery$^-$ curve with coefficient defined by (17) by $E^-_t$, and the 3-cyclic subgroup of $E^-_t$ generated by $(t, -)$ by $C_{t}^{(3-)}$.

The point (0, 0) on Montgomery$^-$ curve has order 2, and the x-coordinates of halves of (0, 0) are $\pm i$. Therefore, it is natural to use isogenies that send $(i, -)$ to $(i, -)$ between Montgomery$^-$ curves. However, if we use curves in $\mathcal {E}\ell \ell _p(\mathcal {O})$, such isogenies are not defined over $\mathbb {F}_p$ in general. A formula of isogenies over $\mathbb {F}_p$ between Montgomery$^-$ curves is given by Proposition 2 in [5]. By combining the formula in [5] and the proof of Theorem 7, we obtain the following formula for Montgomery$^-$ curves.

Theorem 10

Let $t \in \mathbb {F}_p \backslash \{0\}$, E be a Montgomery curve$^-$ over $\mathbb {F}_p$, and $\varphi : E^-_t \rightarrow E$ an isogeny with kernel $C_{t}^{(3-)}$ defined over $\mathbb {F}_p$ that sends (0, 0) to (0, 0). Then the x-coordinate of a generator of $\ker \hat{\varphi }$ is $-\frac{1}{3t}$, and the x-coordinates of other points of order 3 on E are expressed by

$$\begin{aligned} 3t\alpha ^2 + (3t^2+1)\alpha + 3t^3 + 2t, \end{aligned}$$

(18)

where $\alpha$ is a cube root of $t(t^2+1)$.

By choosing $\alpha$ in $\mathbb {F}_p$, we can obtain a similar result to Corollary 9.

5.2 Degree-4 Isogenies

We consider the case that $p \equiv 7 \pmod {8}$ and $\mathcal {O}= \mathbb {Z}[\frac{1 + \sqrt{-p}}{2}]$, which is the setting in CSURF. In this case, the prime 2 splits as the product of $\left( 2, \frac{1 - \sqrt{-p}}{2}\right)$ and $\left( 2, \frac{1 + \sqrt{-p}}{2}\right)$ in $\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}]$. As in [5], for $a \in (\mathbb {F}_p^\times )^2$, we denote the square root of a that is a square in $\mathbb {F}_p$ by $\sqrt{a}$ and define $\root 4 \of {a} := \sqrt{\sqrt{a}}$. Note that $\sqrt{a}$ can be computed as $a^{\frac{p + 1}{4}}$ and $\root 4 \of {a}$ as $a^{\frac{p+1}{8}}$.

Our purpose is to apply Theorem 8 to computing the actions of the squares of the prime ideals above 2. Unlike the case of degree 3, the squaring map in $\mathbb {F}_p$ is not bijective. Therefore, we need to determine a square root (or a fourth root) that corresponds to the action of an ideal class we want to compute.

As considered in [5], every class in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$ contains exactly two Montgomery curves over $\mathbb {F}_p$. In one of them, the point (0, 0) generates the $\left( 2, \frac{1 - \sqrt{-p}}{2}\right)$-torsion subgroup, and in the other curve, the point (0, 0) generates the $\left( 2, \frac{1 + \sqrt{-p}}{2}\right)$-torsion subgroup.

In the following, we let E be a Montgomery curve over $\mathbb {F}_p$ in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$, and A the Montgomery coefficient of E. First, we show how to determine which ideal the point (0, 0) generates.

Lemma 11

The point (0, 0) on E generates $E[2, \frac{1 - \sqrt{-p}}{2}]$ if and only if $A + 2 \in (\mathbb {F}_p^\times )^2$ and $E[2, \frac{1 + \sqrt{-p}}{2}]$ if and only if $-A + 2 \in (\mathbb {F}_p^\times )^2$

Proof

From Lemma 5 in [5], the point (0, 0) generates $E[2, \frac{1 - \sqrt{-p}}{2}]$ if and only if (0, 0) has half in $E(\mathbb {F}_p)$. Furthermore, if (0, 0) has half in $E(\mathbb {F}_p)$, then all halves of (0, 0) are in $E(\mathbb {F}_p)$ since $E \in \mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$ implies $E[2] \subset E(\mathbb {F}_p)$.

Let $P = (1, -)$ on E. Then P is half of (0, 0), and the y-coordinate of P is a square root of $A + 2$. Therefore, P has half in $E(\mathbb {F}_p)$ if and only if $A + 2 \in (\mathbb {F}_p^\times )^2$.

Because $E[2] \subset E(\mathbb {F}_p)$, the all roots of $x^3 + Ax^2 + x$ are in $\mathbb {F}_p$. This means that $A^2 - 4 \in (\mathbb {F}_p^\times )^2$. Therefore, if $A + 2 \notin (\mathbb {F}_p^\times )^2$, then $-A + 2 \in (\mathbb {F}_p^\times )^2$. This proves the latter of the lemma.    $\square$

We define the modified Montgomery coefficient a of E as $a = 4(A + 2)$ if $A + 2 \in (\mathbb {F}_p^\times )^2$ and $a = 4(-A + 2)$ if $-A + 2 \in (\mathbb {F}_p^\times )^2$. Note that a is always in $(\mathbb {F}_p^\times )^2$. To simplify notation, we let $\mathfrak {a}= \left( 2, \frac{1 - \sqrt{-p}}{2}\right)$ if $A + 2 \in (\mathbb {F}_p^\times )^2$ and $\mathfrak {a}= \left( 2, \frac{1 + \sqrt{-p}}{2}\right)$ if $-A + 2 \in (\mathbb {F}_p^\times )^2$. Then we can compute the action of $\mathfrak {a}$ as follows.

Lemma 12

Let $E'$ be a representative of the $\mathbb {F}_p$-isomorphism class $[\mathfrak {a}]* E$ that is expressed as the Montgomery curve over $\mathbb {F}_p$ such that (0, 0) on $E'$ generates $E'[\mathfrak {a}]$. Then the modified Montgomery coefficient of $E'$ is

$$\begin{aligned} \frac{(\sqrt{a} + 4)^2}{\sqrt{a}}. \end{aligned}$$

(19)

Proof

If $A + 2 \in (\mathbb {F}_p^\times )^2$, then the isogeny $\varphi$ in Proposition 4 is defined over $\mathbb {F}_p$ by taking $\alpha = \sqrt{A + 2}$. Let $E''$ be the codomain of $\varphi$ and $A''$ the Montgomery coefficient of $E''$. Then we have $A'' + 2 = \frac{(\sqrt{A + 2} + 2)^2}{2\sqrt{A + 2}} \in (\mathbb {F}_p^\times )^2$. Therefore, we conclude that $E' = E''$ as a Montgomery curve because $E'$ is the unique Montgomery curve satisfying the property by which it is defined. By multiplying $A'' + 2$ by 4, we obtain the formula in the lemma for the case that $A + 2 \in (\mathbb {F}_p^\times )^2$.

In the case that $-A + 2 \in (\mathbb {F}_p^\times )^2$, we use quadratic twists. Let $E^{(t)}$ be the quadratic twist of E, i.e., the Montgomery curve with coefficient $-A$. Then there exists an isomorphism $\tau : E \rightarrow E^{(t)}; (x, y) \mapsto (-x, iy)$. Let $\varphi$ be the isogeny in Proposition 4 from $E^{(t)}$ with $\alpha = \sqrt{-A + 2}$, and $E''$ the codomain of $\varphi$. Let ${E''}^{(t)}$ be the quadratic twist of $E''$ and $\tau ': E'' \rightarrow {E''}^{(t)}$ be the isomorphism defined by $(x,y) \mapsto (-x,iy)$. Then the composition

is defined over $\mathbb {F}_p$. An easy calculation shows that the modified Montgomery coefficient of ${E''}^{(t)}$ is equal to (19). This proves the lemma.    $\square$

Remark 1

If $A + 2 \in (\mathbb {F}_p^\times )^2$, then the isogeny in Lemma 12 sends $(1, -)$ to (0, 0). On the other hand, if $-A + 2 \in (\mathbb {F}_p^\times )^2$, then the isogeny sends $(-1, -)$ to (0, 0) because we use the composition with the twist maps in this case. This means that $E[\mathfrak {a}^2]$ is generated by $(1, -)$ if $A + 2 \in (\mathbb {F}_p^\times )^2$ and $(-1, -)$ if $-A + 2 \in (\mathbb {F}_p^\times )^2$. Note that $\mathfrak {a}$ is different in each case.

By using this lemma twice, we obtain a formula for the action of $\mathfrak {a}^2$. The obtained formula includes the square root of (19) in $(\mathbb {F}_p^\times )^2$. Therefore, we need to determine whether $\sqrt{a} + 4$ is a square in $\mathbb {F}_p$. The following lemma answers it.

Lemma 13

$\sqrt{a} + 4$ is a square in $\mathbb {F}_p$ if and only if $p \equiv 15 \pmod {16}$.

Proof

From Lemma 3 in [5], the subgroup $E(\mathbb {F}_p)[4]$ is isomorphic to $\mathbb {Z}/2\mathbb {Z}\oplus \mathbb {Z}/4\mathbb {Z}$. This subgroup has order 8, so $E(\mathbb {F}_p)$ contains a point of order 8 if and only if $p \equiv 15 \pmod {16}$.

Assume $A + 2 \in (\mathbb {F}_p^\times )^2$. Let $P = (1, -)$ on E. As we mentioned in Remark 1, P generates $E[\mathfrak {a}^2]$. Therefore, we have

$$\begin{aligned} \left( \frac{1 - \sqrt{-p}}{2}\right) ^2P = O_E. \end{aligned}$$

A straightforward calculation shows that

$$\begin{aligned} \frac{1 - \sqrt{-p}}{2}P = \frac{p + 1}{4}P. \end{aligned}$$

Because P has order 4, this equation implies that half of P is in $E(\mathbb {F}_p)$ if and only if $p \equiv 15 \pmod {16}$. From the arithmetic of Montgomery curves, the x-coordinate of half of P is a root of

$$\begin{aligned} x^4 - 4x^3 - (4A + 2)x^2 - 4x + 1. \end{aligned}$$

This is decomposed as

$$\begin{aligned} (x^2 + (\sqrt{a} - 2)x + 1) (x^2 + (-\sqrt{a} - 2)x + 1). \end{aligned}$$

(20)

The discriminant of the left factor is $\sqrt{a}(\sqrt{a}-4)$ and that of the right factor is $\sqrt{a}(\sqrt{a}+4)$. Since $(\sqrt{a} - 4)(\sqrt{a} + 4) = a - 16 \in (\mathbb {F}_p^\times )^2$, the polynomial (20) has a root in $\mathbb {F}_p$ if and only if $\sqrt{a} + 4 \in (\mathbb {F}_p^\times )^2$. Assume (20) has a root $x_0$ in $\mathbb {F}_p$, and let Q be $(x_0, -)$ on E. Then we have $2Q = P$. Because $x_0 \in \mathbb {F}_p$, the image $\pi (Q)$ of the Frobenius is Q or $-Q$. If $\pi (Q) = -Q$, we obtain $\pi (P) = -P$ by multiplying both sides by 2. This contradicts the fact that $P \in E(\mathbb {F}_p)$. Therefore, we have $\pi (Q) = Q$, i.e., $Q \in E(\mathbb {F}_p)$. This proves the lemma for the case that $A + 2 \in (\mathbb {F}_p^\times )^2$.

For the case that $-A + 2 \in (\mathbb {F}_p^\times )^2$, we can prove the lemma by applying the same discussion to the quadratic twist of E.    $\square$

Now we obtain the following radical-isogeny formula for the action of $\mathfrak {a}^2$.

Theorem 14

Let $E'$ be a representative of the $\mathbb {F}_p$-isomorphism class $[\mathfrak {a}^2] * E$ that is expressed as the Montgomery curve over $\mathbb {F}_p$ such that (0, 0) on $E'$ generates $E'[\mathfrak {a}]$. Then the modified Montgomery coefficient of $E'$ is

$$\begin{aligned} \frac{(\varepsilon \root 4 \of {a} + 2)^4}{\varepsilon \root 4 \of {a}(\sqrt{a} + 4)}, \end{aligned}$$

(21)

where $\varepsilon = -1$ if $p \equiv 7 \pmod {16}$ or $\varepsilon = 1$ if $p \equiv 15 \pmod {16}$.

Proof

From Lemma 13, we have

$$\begin{aligned} \sqrt{\frac{(\sqrt{a} + 4)^2}{\sqrt{a}}} = \frac{\varepsilon (\sqrt{a} + 4)}{\root 4 \of {a}}. \end{aligned}$$

By applying Lemma 12 twice, we obtain the formula in the theorem.    $\square$

As a corollary of Theorem 14, we prove a conjecture stated by [6]. In particular, we prove the following.

Corollary 15

(Conjecture 2 in [6]). Let E be an elliptic curve defined by a Tate normal form $y^2 + xy -by = x^3 -bx^2,\ b \in \mathbb {F}_p$, let $P = (0, 0) \in E$, and let $\mathfrak {a}= \left( 2, \frac{1 - \sqrt{-p}}{2}\right)$. Assume that $\mathrm {End}(E) \cong \mathbb {Z}[\frac{1 + \sqrt{-p}}{2}]$ and P generates $E[\mathfrak {a}^2]$. Then $-b$ is a square in $\mathbb {F}_p$. Moreover, the elliptic curve $E': y^2 + xy -b'y = x^3 -b'x^2$ with

$$\begin{aligned} b' = -\frac{\alpha (4\alpha ^2 + 1)}{(2\alpha + 1)^4}, \end{aligned}$$

(22)

where $\alpha = -\root 4 \of {-b}$ if $p \equiv 7 \pmod {16}$ or $\alpha = \root 4 \of {-b}$ if $p \equiv 15 \pmod {16}$, is a representative of the $\mathbb {F}_p$-isomorphism class $[\mathfrak {a}^2] * E$ such that (0, 0) on $E'$ generates $E'[\mathfrak {a}^2]$.

Proof

Note that $b \ne 0$ because E is smooth. We also note that P has order 4.

Let $E_+$ be the Montgomery curve with coefficient $2 + \frac{1}{4b}$ and $E_-$ the Montgomery curve with coefficient $-(2 + \frac{1}{4b})$. There are two isomorphisms $\iota _+: E \rightarrow E_+$ defined by

$$\begin{aligned} (x, y) \mapsto \left( \frac{1}{b}(x-b), \frac{1}{b\sqrt{b}}\left( y+\frac{x-b}{2}\right) \right) \end{aligned}$$

and $\iota _-: E \rightarrow E_-$ defined by

$$\begin{aligned} (x, y) \mapsto \left( -\frac{1}{b}(x-b), -\frac{1}{b\sqrt{-b}}\left( y+\frac{x-b}{2}\right) \right) . \end{aligned}$$

(Here, we extend the symbol to $\mathbb {F}_p$. A choice of a square root is not essential since it corresponds to the composition with $[-1]$.)

Assume that $-b$ is not a square in $\mathbb {F}_p$. Then b is a square in $\mathbb {F}_p$, so the isomorphism $\iota _+$ is defined over $\mathbb {F}_p$. Therefore we have $E_+ \in \mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$. From the assumption, the point $\iota _+(P)$ generates $E_+[\mathfrak {a}^2]$. However, the x-coordinate of $\iota _+(P)$ is $-1$. This contradicts Remark 1. Thus we conclude that $-b$ is a square in $\mathbb {F}_p$.

Because the isomorphism $\tau _-$ is defined over $\mathbb {F}_p$ and the x-coordinate of $\iota _-(P)$ is 1, the Montgomery curve $E_-$ is in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$, and the modified Montgomery coefficient of $E_-$ is $-\frac{1}{b}$. Let $E'_-$ be the Montgomery curve obtained by applying Theorem 14 to $E_-$. Then it is easy to verify that $E'$ is $\mathbb {F}_p$-isomorphic to $E'_-$ by an isomorphism defined as $\iota _-$, which sends (0, 0) on $E'$ to $(1, -)$ on $E_-'$. This completes the proof.    $\square$

5.3 Computational Efficiency

We discuss the computational efficiency of our formulas in application to CSIDH and its variants. As in [6], we evaluate the costs of formulas by the number of exponentiations, multiplications, additions, and inversions on $\mathbb {F}_p$ and denote these by E, M, A, and I, respectively. Note that the exponent of E is almost the same size as p and that its cost is about $1.5\log _2(p)\mathbf{M}$.

Degree 3. We compare the cost of our formula (16) with the original radical isogeny (6). The cost of our formula is $\mathbf{E} + 5\mathbf{M} + 12\mathbf{A}$, and that of the original is $\mathbf{E} + 3\mathbf{M} + 12\mathbf{A}$. Note that we count the multiplication by 2, 3, and 9 as $\mathbf{A}$, $2\mathbf{A}$, and $4\mathbf{A}$, respectively. Our cost is $2\mathbf{M }$ higher than the original. However, our parametrization t has the transformation formula (9) to recover a Montgomery coefficient, which is easy to compute. On the other hand, the original radical isogeny needs transformations between a Montgomery curve and a curve used in radical isogenies of degree 3. The costs of these transformations are relatively high since these include some exponentiations. From this, our formula could be more efficient than the original in some parameters of cryptosystems. We explain this in detail below.

Let $E \in \mathcal {E}\ell \ell _p(\mathcal {O})$, $\ell$ be an odd prime dividing $p + 1$, and $\mathfrak {l}$ be a prime ideal above $\ell$ in $\mathcal {O}$. The method to compute the action of $\mathfrak {l}^n$ on E by [6] is as follows:

• 1. Find a generator P of $E[\mathfrak {l}]$ on a Montgomery curve.

• 2. Transform the Montgomery curve to a curve with the image of P is (0, 0).

• 3. Compute an $\ell$-isogeny $n-1$ times by iterating the radical-isogeny formula.

• 4. Compute an $\ell$-isogeny with kernel $\langle {(0, 0)}\rangle$ by Vélu’s formula.

• 5. Transform the curve to a Montgomery form.

In the implementation¹ in [6] of CSURF, Step 2 contains E, and Step 5 contains 3E. On the other hand, by using our formula, we do not need Step 2 and obtain the objective Montgomery coefficient by (9) instead of Step 5. The cost of (9) is $3\mathbf{M} + 9\mathbf{A} + \mathbf{I}$.

Table 2 shows the costs of the 3-isogenies and the transformations. (Table 2 redisplays the left half of Table 1.) Because the cost of $\mathbf{I}$ is less than that of $\mathbf{E}$, our formula reduces the cost of the transformations at least $3\mathbf{E}$. In addition, if we use the projective coordinate on Montgomery curves, then the inversion in (9) vanishes. While the exceeding cost of our formula in Step 3 is $3(n-1)\mathbf{M}$. In Step 4, both methods use Vélu’s formulas. However, our method is slightly faster because Vélu’s formulas on Montgomery curves are efficient. Therefore, if the exponent n of the ideal is less than about $1.5\log _2(p)$, then our formula accelerates the action of an ideal of norm 3.

Table 2. The costs of 3-isogenies and transformations

Remark 2

The implementation in [6] uses 9-isogenies instead of 3-isogenies for CSURF-512, a parameter set of CSURF proposed by [5]. Since the characteristic p of the base field in CSURF-512 satisfies $9 \mid p + 1$, the elliptic curves in $\mathcal {E}\ell \ell _p(\mathcal {O})$ have a point of order 9 over $\mathbb {F}_p$. In this case, using 9-isogenies reduces the cost of the action of an ideal of norm 3 since the number of $\mathbf{E}$ in Step 3 is halved. Consequently, our formula does not improve the efficiency in this case. However, our formula could do in the case that $9 \not \mid p + 1$, for example, CSIDH-512 proposed in [7].

Degree 4. As in Sect. 5.2, we let $p \equiv 7 \pmod {8}$ for considering 4-isogenies corresponding to the ideal actions. We say curves in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$ are on the surface, and curves in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\sqrt{-p}])$ are on the floor.

First, we recall the computing method of CSURF in the previous works.

The original CSURF [5] uses Montgomery$^-$ curves since these curves are always on the surface, and there is a one-to-one correspondence between Montgomery$^-$ coefficients of supersingular elliptic curves and the classes in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$ if $p \equiv 7 \pmod {8}$. All the computation in the original CSURF, thus, is done on the surface.

On the other hand, the CSURF using radical isogenies [6] uses curves both on the surface and the floor. There are two reasons to use curves on the floor. First, their transformations from Tate normal forms to Montgomery curves for degrees greater than four use the properties that these curves have exactly one point of order 2 over $\mathbb {F}_p$. Second, the arithmetic on Montgomery curves is slightly faster than that on Montgomery$^-$ curves. The computation of ideal class actions is as follows:

• 1. Take a Montgomery$^-$ curve as an input.

• 2. Transform the curve to a Tate normal form and compute 4-radical isogenies.

• 3. Transform the resulting curve to a Montgomery curve on the floor.

• 4. Compute radical isogenies of degrees less than 17.

• 5. Compute the action of the remaining ideal as in the original CSIDH [7].

• 6. Transform the resulting Montgomery curve to Montgomery$^-$ curve.

Here, we propose a computing method of CSURF that does not use Montgomery$^-$ curves at all. Table 1 in [5] shows that there are exactly two $\mathbb {F}_p$-isomorphic Montgomery curves on the surface. On one of these, the point (0, 0) generates the ideal $\left( 2, \frac{1 - \sqrt{-p}}{2}\right)$ (we call a Montgomery curve with this property by positive type). On the other, the point (0, 0) generates the ideal $\left( 2, \frac{1 + \sqrt{-p}}{2}\right)$ (we call a Montgomery curve with this property by negative type). In short, there is a one-to-one correspondence between positive-type Montgomery curves and the classes in $\mathcal {E}\ell \ell _p(\mathbb {Z}[\frac{1 + \sqrt{-p}}{2}])$. Lemma 11 allows us to determine which type of curve is by computing a Legendre symbol. A Montgomery curve with coefficient A is on the surface if and only if $A^2 - 4 \in (\mathbb {F}_p^\times )^2$. Therefore, by adding two Legendre symbol computations to key validation in CSURF, we can use Montgomery coefficients of positive-type curves as public keys and shared secrets.

Unfortunately, we need to transform a Montgomery curve from positive type to negative type for computing the action of $\left( 2, \frac{1 + \sqrt{-p}}{2}\right)$, which is the inverse of $\left( 2, \frac{1 - \sqrt{-p}}{2}\right)$ as an ideal class, and the cost of the transformation needs two exponentiations. Let E be a positive-type Montgomery curve with coefficient A. Lemma 4 in [5] shows that the negative-type curve that is $\mathbb {F}_p$-isomorphic to E is obtained by an isomorphism between Montgomery curves sending $\left( \frac{-A - \sqrt{A^2 - 4}}{2}, 0\right)$ to (0, 0). Therefore, the coefficient of the negative-type curve is

$$\frac{-A - 3\sqrt{A^2-4}}{\sqrt{2\sqrt{A^2-4}(A + \sqrt{A^2-4})}}.$$

We use this transformation if the exponent of the ideal $\left( 2, \frac{1 - \sqrt{-p}}{2}\right)$ is negative. Furthermore, we have to move to the floor from the surface for using radical isogenies of degrees greater than four. This can be computed by a 2-isogeny.

Consequently, the computation of ideal class actions using our radical isogenies of degree 4 is as follows:

• 1. Take a positive-type Montgomery curve as an input.

• 2. Transform to negative type if the exponent of $\left( 2, \frac{1 - \sqrt{-p}}{2}\right)$ is negative.

• 3. Transform to the modified Montgomery coefficient.

• 4. Compute 4-radical isogenies by (21).

• 5. Transform to the Montgomery coefficient.

• 6. Transform to the floor.

• 7. Compute radical isogenies of other degrees.

• 8. Compute the action of the remaining ideal as in the original CSIDH [7].

• 9. Transform to the surface.

We can compute 9 by $A \mapsto \frac{A + 6}{2\sqrt{A + 2}}$. It is easy to check that the resulting curve is always positive type. The computational cost is slightly less than transforming a Montgomery curve on the floor to a Montgomery$^-$ curve.

Table 3 compares the costs related to 4-isogenies of our method with the original radical isogenies. This shows that our method is more efficient even if we need to transform to a negative-type curve.

We implemented CSURF using our formulas on Magma [3]. Our implementation is based on that by [6] and available at https://github.com/hiroshi-onuki/Montgomery-Radical-Isogenies.

Table 3. The costs of 4-isogenies and transformations. The costs of transformations in our formulas include the cost of transformations between Montgomery coefficients and modified Montgomery coefficients. In the second line, we need the cost $(2\mathbf{E} + 2\mathbf{M} + 6\mathbf{A} + \mathbf{I} )^*$ only in the case that the exponent of the ideal $[2, \frac{1 - \sqrt{-p}}{2}]$ is negative.

6 Conclusion

We proposed the radical-isogeny formulas of degrees 3 and 4 on Montgomery curves. We analyzed those computational efficiencies in application to CSIDH and its variants. Because our formulas reduce the cost of transformations between elliptic curves, these could improve the efficiency of CSIDH and its variants. In particular, we showed that our formulas of degree 3 could be efficient in some cases. Our formula of degree 4 is more efficient than the original radical isogenies. In addition, we proved the conjecture on radical isogenies of degree 4, which was left open in [6].