# The group structure of elliptic curves over $\mathbb{Z}/N\mathbb{Z}$

Massimiliano Sala∗<EMAIL_ADDRESS>Daniele Taufer†
<EMAIL_ADDRESS>∗University of Trento; †CISPA Helmholtz Center
for Information Security

###### Abstract

We characterize the possible groups $E(\mathbb{Z}/N\mathbb{Z})$ arising from
elliptic curves over $\mathbb{Z}/N\mathbb{Z}$ in terms of the groups
$E(\mathbb{F}_{p})$, with $p$ varying among the prime divisors of $N$. This
classification is achieved by showing that the infinity part of any elliptic
curve over $\mathbb{Z}/p^{e}\mathbb{Z}$ is a
$\mathbb{Z}/p^{e}\mathbb{Z}$-torsor.

As a first consequence, when $E(\mathbb{Z}/N\mathbb{Z})$ is a $p$-group, we
provide an explicit and sharp bound on its rank. As a second consequence, when
$N=p^{e}$ is a prime power and the projected curve $E(\mathbb{F}_{p})$ has
trace one, we provide an isomorphism attack to the ECDLP, which works only by
means of finite rings arithmetic rather than involved methods.

###### keywords:

Group structure , Elliptic Curves , Rank , Anomalous curves , Discrete
Logarithm Problem , Isomorphism Attack

###### MSC:

11T71 , 13B25 , 14H52

††journal: Journal of Algebra

##  1 Introduction

Elliptic curves have been providing number theory with a fertile field of
intense research for the last century, from theoretic [17, 15, 29, 5],
algorithmic [21, 2] and applied [16, 9, 8, 23] sides. In their basic
definition, these objects consist of non-singular plane projective cubics,
defined as the zero-set of a Weierstrass polynomial over a given base field.
It is well-known that these curves are actually abelian varieties with the
chord-tangent sum [24, 7, 27]. The study of the group structure arisen from
this operation has attracted a huge attention and its grasp has proven to be
remarkably challenging. Beyond its indisputable algebraic interest, the
security of cryptographic protocols based on these curves relies in the nature
of their addition operation, hence the investigation of these groups has
received impetus in the last decades.

When the underlying field is finite, any group that may be realized as point
group of an elliptic curve is known [18, 26]. Nevertheless, both their
distribution [1] and their efficient explicit description [10] are lines of
open research. We refer to [19] for an overview of the known classification of
groups arising from curves with a Weierstrass model.

Elliptic curves may also be defined over rings, among which
$\mathbb{Z}/N\mathbb{Z}$ is a significant instance both from a theoretical
perspective [12] and for cryptographic applications [13]. In this paper, we
are mainly interested in their algebraic, especially groupal, properties: we
classify all the possible groups arising from elliptic curves over any residue
ring $\mathbb{Z}/N\mathbb{Z}$ in terms of their projected components modulo
the prime divisors of $N$. More precisely, if $p$ is a prime integer and
$\mathrm{v}_{p}(N)$ is the $p$-adic valuation of $N$, the Chinese Reminder
Theorem provides a group isomorphism

$E(\mathbb{Z}/N\mathbb{Z})\simeq\bigoplus_{p|N}E(\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z}),$

whose components are known [12, 27] to split as

$E(\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z})=H\oplus E(\mathbb{F}_{p}).$

The subgroup at infinity $H$, given by the kernel of the canonical projection,
is known to be a $p$-group, since $|H|=p^{\mathrm{v}_{p}(N)-1}$ [12]. However,
two problems remained open: determining the structure of this group, and
outlining its behavior in the anomalous case.

In this work we provide a complete solution to the above issues. The main
result of this paper is reaching a complete group classification, as follows.

$E(\mathbb{Z}/N\mathbb{Z})\simeq\bigoplus_{\begin{subarray}{c}p|N\\\
|E(\mathbb{F}_{p})|\neq
p\end{subarray}}E(\mathbb{F}_{p})\oplus\mathbb{Z}/p^{\mathrm{v}_{p}(N)-1}\mathbb{Z}\oplus\bigoplus_{\begin{subarray}{c}p|N\\\
|E(\mathbb{F}_{p})|=p\end{subarray}}G_{p},$

where every $G_{p}$ may be either $\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z}$
or $\mathbb{F}_{p}\oplus\mathbb{Z}/p^{\mathrm{v}_{p}(N)-1}\mathbb{Z}$. This
result is obtained by proving that the infinity part of
$E(\mathbb{Z}/p^{e}\mathbb{Z})$ is a $\mathbb{Z}/p^{e}\mathbb{Z}$-torsor,
which is far from being true over generic local rings, as we will explicitly
show.

From the above classification, we derive some consequences. First, we give an
explicit bound on the rank of $E(\mathbb{Z}/N\mathbb{Z})$ when the points of
such curve form a $p$-group. This bound is sharp and depends only on $p$,
determining as a corollary infinitely many groups that cannot arise from such
curves. The proof of this bound also provides a systematic way for generating
such $p$-curves of admissible ranks. Second, we exhibit a polynomial-time
isomorphism attack to the elliptic curve discrete logarithm problem (ECDLP)
over anomalous curves. Although similar attacks have already appeared [20,
25], we find this approach noteworthy as its correctness and execution may be
elaborated with finite rings arithmetic, which constitutes the ideal setting
for computational algebra applications.

This paper is organized as follows. In Section 2 we recall some known results
and definitions, including the group structure of elliptic curves over finite
fields and the definition of such curves over rings. In Section 3 the group
structure of elliptic curves over $\mathbb{Z}/N\mathbb{Z}$ is investigated and
we derive our main result (Theorem 17). Consequently, in Section 4 we present
a bound to the rank of $p$-groups that may arise from elliptic curves over
$\mathbb{Z}/N\mathbb{Z}$. An isomorphism attack to the ECDLP over anomalous
curves is described in Section 5. Finally, conclusions and further work are
discussed in Section 6.

##  2 Preliminaries

In this paper $R$ always denotes a commutative ring with unity and $R^{*}$ the
set of its invertible elements. We employ capital letters $X,Y,Z$ to denote
elements of $R$, while lowercase ones are variables in $R[x,y,z]$.

######  Definition 1 (Primitivity).

A finite collection $\\{X_{i}\\}_{i\in\\{0,\dots,n\\}}\subseteq R^{n+1}$ is
called _primitive_ if the ideal
$\langle\\{X_{i}\\}_{i\in\\{0,\dots,n\\}}\rangle_{R}$ is $R$ itself.

###  2.1 Elliptic curves over finite fields

The trace $t$ of any elliptic curve over a finite field $\mathbb{F}_{q}$ is
constrained by the Hasse bound [24, Theorem V.1.1], i.e.

$t=q+1-|E(\mathbb{F}_{q})|$

is bounded by

$-2\sqrt{q}\leq t\leq 2\sqrt{q}.$

Not every possible integer $t$ in the above interval occurs as the trace of an
elliptic curve over $\mathbb{F}_{q}$, as detailed in [28, Theorem 4.1]. In
particular, it shows that the Hasse interval over prime fields is full. From
this work, a complete characterization of the possible point groups for
elliptic curves over finite fields has seen the light, independently
discovered by two authors [18, 26].

By virtue of these works we know all the possible groups arising from elliptic
curves over finite fields, which we will use in Section 3 to characterize
those of curves over $\mathbb{Z}/N\mathbb{Z}$.

###  2.2 Strong rank

To deal with matrices over commutative rings, it is worth to introduce a
stronger notion of matrix rank.

######  Definition 2 (Minor ideal).

Let $n,m\in\mathbb{Z}_{\geq 1}$ and $A\in M_{n,m}(R)$. For every integer
$1\leq t\leq\min\\{n,m\\}$ we define the _$t$ -minor ideal_ $I_{t}(A)$ as the
ideal generated by the $t\times t$ minors of $A$. We also define by convention
$I_{0}(A)=R$ and for every $t>\min\\{n,m\\}$ we set $I_{t}(A)=(0)$.

######  Definition 3 (Strong rank).

Let $n,m\in\mathbb{Z}_{\geq 1}$ and $A\in M_{n,m}(R)$. We define the _strong
rank_ of $A$ as

$\textnormal{rk}(A)=\max\\{t\in\mathbb{Z}_{\geq 0}\ |\ I_{t}(A)\neq(0)\\}.$

This notion of rank is easily shown to be never lower than the usual notion of
rank over rings [6, Chapter 4]. The convenience of using this rank relies on
the following result.

######  Lemma 4.

Let $n,m\in\mathbb{Z}_{\geq 1}$ and $A\in M_{n,m}(R)$ be a matrix whose
entries are primitive, then the following are equivalent.

  1. 1.

$\textnormal{rk}(A)=1$.

  2. 2.

The $2\times 2$ minors of $A$ vanish.

  3. 3.

All the primitive vectors of $R^{n}$ that may be obtained from an $R$-linear
combination among the columns of $A$ are equal up to $R^{*}$-multiples.

###### Proof.

Let $A=(a_{i,k})_{\begin{subarray}{c}1\leq i\leq n\\\ 1\leq k\leq
m\end{subarray}}$.
$[\ref{rk:i}\Rightarrow\ref{rk:ii}]$ Since $\textnormal{rk}(A)=1$ then
$I_{2}(A)=(0)$, hence all the generators of $I_{2}(A)$ vanish.
$[\ref{rk:ii}\Rightarrow\ref{rk:iii}]$ Let $v_{1}=(v_{11},\dots,v_{1n})$ and
$v_{2}=(v_{21},\dots,v_{2n})$ be two primitive columns combinations. Since
$v_{1}$ is primitive there are $\alpha_{1},\dots,\alpha_{n}\in R$ with

$\sum_{i=1}^{n}\alpha_{i}v_{1i}=1\in R.$

Any $2\times 2$ minor of the ($n\times 2$)-matrix $(v_{1}|v_{2})$, whose
columns are $v_{1}$ and $v_{2}$, is an $R$-linear combination of the $2\times
2$ minors of $A$, hence it vanishes. Thus, for every $i,j\in\\{1,\dots,n\\}$
we have $v_{1i}v_{2j}=v_{1j}v_{2i}$, then

$v_{2}=1\cdot v_{2}=\left(\sum_{i=1}^{n}\alpha_{i}v_{1i}v_{2j}\right)_{1\leq
j\leq n}=\left(\sum_{i=1}^{n}\alpha_{i}v_{1j}v_{2i}\right)_{1\leq j\leq
n}=\left(\sum_{i=1}^{n}\alpha_{i}v_{2i}\right)v_{1}.$

This proves that $v_{2}$ is a multiple of $v_{1}$, and since also $v_{2}$ is
primitive then the scalar factor has to be a unit, i.e.
$\sum_{i=1}^{n}\alpha_{i}v_{2i}\in R^{*}$.
$[\ref{rk:iii}\Rightarrow\ref{rk:i}]$ For every pair of columns $c_{k}$ and
$c_{h}$ of $A$ there is $r_{kh}\in R^{*}$ such that $c_{h}=r_{kh}c_{k}$.
Therefore for every $1\leq i,j\leq n$ we have

$a_{ik}a_{jh}-a_{ih}a_{jk}=r_{kh}(a_{ik}a_{jk}-a_{ik}a_{jk})=0,$

which shows that $I_{2}(A)=(0)$. Moreover, since the entries of $A$ are
primitive we have $I_{1}(A)=R$, so that $\textnormal{rk}(A)=1$. ∎

###  2.3 Elliptic curves over rings

Let $n$ be a non-negative integer. The projective $n$-space over $R$ is
defined in order to respect projections on any non-zero quotient of $R$, as
follows.

######  Definition 5 (Projective $n$-space).

The _projective $n$-space_ over $R$ is the set of orbits of primitive tuples
in $R^{n+1}$ under the action of elements $u\in R^{*}$ given by

$u(X_{0},\dots,X_{n})=(uX_{0},\dots,uX_{n}).$

It is denoted by $\mathbb{P}^{n}(R)$, while
$(X_{0}:\dots:X_{n})\in\mathbb{P}^{n}(R)$ represents the orbit of
$(X_{0},\dots,X_{n})\in R^{n+1}$.

An elliptic curve over $R$ may be defined [12] to properly extend those over
$R/\mathfrak{m}$, where $\mathfrak{m}\subseteq R$ is any maximal ideal,
provided that $R$ satisfies the following condition.

######  Condition 6 ([12]).

For every pair $n,m\in\mathbb{Z}_{\geq 1}$ and every matrix

$A=(a_{ij})_{\begin{subarray}{c}1\leq i\leq n\\\ 1\leq j\leq
m\end{subarray}}\in M_{n,m}(R)$

with strong rank $\textnormal{rk}(A)=1$ and primitive entries, there exists an
$R$-linear combination of the columns of $A$ whose entries are primitive.

In this work we will only deal with elliptic curves that may be defined via
their short Weierstrass equation, which is not restrictive when $6\in R^{*}$.

######  Definition 7 (Elliptic curve over $R$).

Let $R$ be a commutative ring with unity satisfying Condition 6 and let
$A,B\in R$ such that

$\Delta_{A,B}=-(4A^{3}+27B^{2})\in R^{*}.$

The _elliptic curve_ $E_{A,B}(R)$ is defined as

$E_{A,B}(R)=\\{(X:Y:Z)\in\mathbb{P}^{2}(R)\ |\
Y^{2}Z=X^{3}+AXZ^{2}+BZ^{3}\\}.$

Given an elliptic curve $E=E_{A,B}(R)$, we denote by $\mathcal{O}=(0:1:0)\in
E$ its _zero element_ , with $E^{a}=E\cap\mathbb{P}_{\text{aff}}^{2}(R)$ its
_affine points_ and with $E^{\infty}$ the remaining points, which are called
_points at infinity_.

On these curves a sum operation may be explicitly defined on an open covering
of $E_{A,B}(R)\times E_{A,B}(R)$ by means of $(2,2)$-bidegree polynomials [11,
3]. This operation extends the usual point addition with respect to
projections, i.e. for every proper ideal $I\subsetneq R$ we have a well-
defined group homomorphism

$\pi:E_{A,B}(R)\twoheadrightarrow E_{A,B}(R/I).$

We recall for convenience the two addition laws we employ in this work: the
sum of $P_{1}=(X_{1}:Y_{1}:Z_{1})$ and $P_{2}=(X_{2}:Y_{2}:Z_{2})$ is given by
any primitive linear combination of $(S_{1}:S_{2}:S_{3})$ and
$(T_{1}:T_{2}:T_{3})$, where 111Addition laws corresponding to $(0:0:1)$ and
$(0:1:0)$ as in [[3], Theorem 2].

$\displaystyle S_{1}=\ $
$\displaystyle(X_{1}Y_{2}-X_{2}Y_{1})(Y_{1}Z_{2}+Y_{2}Z_{1})+(X_{1}Z_{2}-X_{2}Z_{1})Y_{1}Y_{2}$
$\displaystyle-A(X_{1}Z_{2}-X_{2}Z_{1})(X_{1}Z_{2}+X_{2}Z_{1})-3B(X_{1}Z_{2}-X_{2}Z_{1})Z_{1}Z_{2},$
$\displaystyle S_{2}=\ $
$\displaystyle-3X_{1}X_{2}(X_{1}Y_{2}-X_{2}Y_{1})-Y_{1}Y_{2}(Y_{1}Z_{2}-Y_{2}Z_{1})-A(X_{1}Y_{2}-X_{2}Y_{1})Z_{1}Z_{2}$
$\displaystyle+A(Y_{1}Z_{2}-Y_{2}Z_{1})(X_{1}Z_{2}+X_{2}Z_{1})+3B(Y_{1}Z_{2}-Y_{2}Z_{1})Z_{1}Z_{2},$
$\displaystyle S_{3}=\ $ $\displaystyle
3X_{1}X_{2}(X_{1}Z_{2}-X_{2}Z_{1})-(Y_{1}Z_{2}-Y_{2}Z_{1})(Y_{1}Z_{2}+Y_{2}Z_{1})$
$\displaystyle+A(X_{1}Z_{2}-X_{2}Z_{1})Z_{1}Z_{2},$

and

$\displaystyle T_{1}=\ $ $\displaystyle
Y_{1}Y_{2}(X_{1}Y_{2}+X_{2}Y_{1})-AX_{1}X_{2}(Y_{1}Z_{2}+Y_{2}Z_{1})$
$\displaystyle-A(X_{1}Y_{2}+X_{2}Y_{1})(X_{1}Z_{2}+X_{2}Z_{1})-3B(X_{1}Y_{2}+X_{2}Y_{1})Z_{1}Z_{2}\hskip
45.52458pt$
$\displaystyle-3B(X_{1}Z_{2}+X_{2}Z_{1})(Y_{1}Z_{2}+Y_{2}Z_{1})+A^{2}(Y_{1}Z_{2}+Y_{2}Z_{1})Z_{1}Z_{2},$
$\displaystyle T_{2}=\ $ $\displaystyle
Y_{1}^{2}Y_{2}^{2}+3AX_{1}^{2}X_{2}^{2}+9BX_{1}X_{2}(X_{1}Z_{2}+X_{2}Z_{1})$
$\displaystyle-A^{2}X_{1}Z_{2}(X_{1}Z_{2}+2X_{2}Z_{1})-A^{2}X_{2}Z_{1}(2X_{1}Z_{2}+X_{2}Z_{1})$
$\displaystyle-3ABZ_{1}Z_{2}(X_{1}Z_{2}+X_{2}Z_{1})-(A^{3}+9B^{2})Z_{1}^{2}Z_{2}^{2},$
$\displaystyle T_{3}=\ $ $\displaystyle
3X_{1}X_{2}(X_{1}Y_{2}+X_{2}Y_{1})+Y_{1}Y_{2}(Y_{1}Z_{2}+Y_{2}Z_{1})$
$\displaystyle+A(X_{1}Y_{2}+X_{2}Y_{1})Z_{1}Z_{2}+A(X_{1}Z_{2}+X_{2}Z_{1})(Y_{1}Z_{2}+Y_{2}Z_{1})$
$\displaystyle+3B(Y_{1}Z_{2}+Y_{2}Z_{1})Z_{1}Z_{2}.$

##  3 Elliptic curves over $\mathbb{Z}/N\mathbb{Z}$

Let $N\in\mathbb{Z}_{\geq 2}$ be an integer. Hereafter we consider elliptic
curves defined over the ring $R=\mathbb{Z}/N\mathbb{Z}$, which satisfies the
Condition 6. More generally, in [12] this condition has been proved to hold
for every finite ring. Here we show that $\mathbb{Z}/N\mathbb{Z}$ underlies an
even stronger condition.

######  Lemma 8.

Let $N\in\mathbb{Z}_{\geq 2}$ be an integer and $A$ be a matrix over
$\mathbb{Z}/N\mathbb{Z}$ whose entries are primitive, then there exists a
linear combination of the columns of $A$ that is primitive. In particular,
$R=\mathbb{Z}/N\mathbb{Z}$ satisfies Condition 6.

###### Proof.

Let $A=(c_{1}|c_{2}|\dots|c_{m})$ be the columns of the considered matrix.
Since $A$ is primitive, for every prime $p|N$ there are coefficients
$\alpha^{(p)}_{1},\dots,\alpha^{(p)}_{m}\in\mathbb{Z}/p\mathbb{Z}$ such that
the vector

$v^{(p)}=\sum_{i=1}^{m}\alpha^{(p)}_{i}c_{i}$

is primitive over $\mathbb{Z}/p\mathbb{Z}$. By the Chinese Reminder Theorem we
may find integers $\beta_{1},\dots,\beta_{m}\in\mathbb{Z}$ solving, for every
prime divisor $p$ of $N$, the congruence system

$\beta_{i}\equiv\alpha^{(p)}_{i}\bmod p.$

Therefore, $\sum_{i=1}^{m}\beta_{i}c_{i}$ is easily seen to be a primitive
combination of the columns of $A$. ∎

We now recall how the group of points of an elliptic curve over
$\mathbb{Z}/N\mathbb{Z}$ can be described by the curve projections over the
$p$-components of this ring, with $p$ ranging among the prime divisors of $N$.

######  Proposition 9 ([27], Corollary 2.32).

Let $N_{1},N_{2}$ be coprime integers and let $A,B\in\mathbb{Z}$ such that
$\Delta_{A,B}\in(\mathbb{Z}/N_{1}N_{2}\mathbb{Z})^{*}$. Then the canonical
projections induce a group isomorphism

$E_{A,B}(\mathbb{Z}/N_{1}N_{2}\mathbb{Z})\simeq
E_{A,B}(\mathbb{Z}/N_{1}\mathbb{Z})\oplus
E_{A,B}(\mathbb{Z}/N_{2}\mathbb{Z}).$

Thus, it is sufficient to study the structure of elliptic curves
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ for any prime $p$ and positive integer
$e$, which is the main goal of this section. We begin by noticing that the
points $P\in E=E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ of such curves have
prescribed representatives:

  * 1.

If $P\in E^{a}$, then there are $X,Y\in\mathbb{Z}/p^{e}\mathbb{Z}$ such that

$P=(X:Y:1).$

  * 2.

If $P\in E^{\infty}$, then there are $X,Z\in p(\mathbb{Z}/p^{e}\mathbb{Z})$
such that

$P=(X:1:Z).$

The size of these curves is known, as reported in the next lemma.

######  Lemma 10 ([12], Section 4).

Let $p$ be a prime, $e\in\mathbb{Z}_{\geq 1}$ and

$\pi:E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\to E_{A,B}(\mathbb{F}_{p})$

be the canonical projection. Then for every $P\in E_{A,B}(\mathbb{F}_{p})$ we
have

$|\pi^{-1}(P)|=p^{e-1}.$

In particular

  * 1.

the size of the curve is
$|E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})|=p^{e-1}|E_{A,B}(\mathbb{F}_{p})|$,

  * 2.

$\ker\pi$ is a subgroup of $E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$, whose size
is $p^{e-1}$.

The coordinates of points at infinity satisfy the following relation, which we
prove by adapting the idea of expansion around $\mathcal{O}$ [24, Chapter IV].

######  Proposition 11.

Let p be a prime, $e\in\mathbb{Z}_{\geq 1}$ and
$E=E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$. There is a polynomial
$\mathsf{f}\in\mathbb{Z}[x]$ of degree at most $e-1$ such that for every $P\in
E^{\infty}$ there is $X\in p(\mathbb{Z}/p^{e}\mathbb{Z})$ satisfying

$P=\big{(}X:1:\mathsf{f}(X)\big{)}.$

Moreover, we have

$\mathsf{f}(X)\equiv X^{3}+AX^{7}+BX^{9}\bmod{p^{10}}.$

###### Proof.

Since $P\in E^{\infty}$, it may be represented in the form $(X:1:Z)$, with
$X,Z\in p(\mathbb{Z}/p^{e}\mathbb{Z})$ that satisfy

$Z\equiv X^{3}+AXZ^{2}+BZ^{3}\bmod{p^{e}}.$

We recursively define the following sequence of polynomials in
$\mathbb{Z}[x,z]$:

$F_{0}(x,z)=x^{3}+Axz^{2}+Bz^{3},\qquad\forall\ i\in\mathbb{Z}_{\geq 1}:\
F_{i}(x,z)=F_{i-1}\big{(}x,F_{0}(x,z)\big{)}.$

It is easy to see by induction on $i\in\mathbb{Z}_{\geq 0}$ that this sequence
satisfies

$Z\equiv F_{i}(X,Z)\bmod{p^{e}}.$

Moreover, every $F_{i}$ for $i\in\mathbb{Z}_{\geq 1}$ is obtained from
$F_{i-1}$ by substituting all the occurrences of $z$ with $F_{0}(x,z)$, which
contains only terms of degree $3$, hence the total degree of terms involving
$z$ in $F_{i}$ is strictly increasing while increasing $i$. This means that
there exist $M\in\mathbb{Z}_{\geq 0}$ and $g\in\mathbb{Z}[x,z]$ such that

$F_{M}(x,z)=\mathsf{f}(x)+g(x,z),\qquad\text{ with }\begin{cases}\deg(g)\geq
e,\\\ \deg(\mathsf{f})<e.\end{cases}$

Since both $X$ and $Z$ are divisible by $p$, this implies

$Z\equiv F_{M}(X,Z)\equiv\mathsf{f}(X)\bmod{p^{e}},$

so that $\mathsf{f}\in\mathbb{Z}[x]$ is the required polynomial. A direct
computation shows that

$F_{3}=x^{3}+Ax^{7}+Bx^{9}+(\text{terms of degree}\geq 11),$

which proves the moreover part. ∎

######  Remark 12.

Although finite local rings are complete with respect to the topology induced
by their maximal ideal, they may not be domains (as it is the case for
$\mathbb{Z}/N\mathbb{Z}$). For this reason we found appropriate to explicitly
compute $\mathsf{f}$ instead of considering the truncation to the correct
exponent of the classical series [24, Chapter IV].

To simplify the exposition, for any $X\in\mathbb{Z}/p^{e}\mathbb{Z}$ and any
positive integer $t$ we write $p^{t}|X$ or $X\equiv 0\bmod p^{t}$ in place of
the more precise $X\in p^{t}(\mathbb{Z}/p^{e}\mathbb{Z})$. In the same spirit,
we assign a $p$-adic valuation to any $X\in\mathbb{Z}/p^{e}\mathbb{Z}$ by
writing

$\mathrm{v}_{p}(X)=\begin{cases}t&\text{if }X\in
p^{t}(\mathbb{Z}/p^{e}\mathbb{Z})\setminus
p^{t+1}(\mathbb{Z}/p^{e}\mathbb{Z}),\\\ e&\text{if }X=0.\end{cases}$

From Proposition 11 it is possible to easily derive a description of the
first-order approximation of the sum of two points at infinity.

######  Proposition 13.

Let $p$ be a prime, $e\in\mathbb{Z}_{\geq 1}$,
$E=E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ and $\mathsf{f}\in\mathbb{Z}[x]$ be
the polynomial arising from $E$ as in Proposition 11. Let also

$P_{1}=\big{(}X_{1}:1:\mathsf{f}(X_{1})\big{)},\
P_{2}=\big{(}X_{2}:1:\mathsf{f}(X_{2})\big{)}\in E^{\infty}$

with $e_{1}=\mathrm{v}_{p}(X_{1})$ and $e_{2}=\mathrm{v}_{p}(X_{2})$. Then

$P_{1}+P_{2}=\big{(}X_{3}:1:\mathsf{f}(X_{3})\big{)},\quad\text{where}\quad
X_{3}\equiv X_{1}+X_{2}\bmod{p^{5\min\\{e_{1},e_{2}\\}}}.$

###### Proof.

As $\pi$ is a group homomorphism, $P_{1}+P_{2}$ lies itself in $E^{\infty}$,
which implies [[3], Theorem 2] that these points are never exceptional for the
addition law $+_{(0:1:0)}$ corresponding to $(0:1:0)$. A straightforward
computation with $+_{(0:1:0)}$ shows that, modulo monomials in $X_{1}$ and
$X_{2}$ of total degree at least $5$ (i.e. modulo
$p^{5\min\\{e_{1},e_{2}\\}}$), we have

$P_{1}+P_{2}=\big{(}X_{1}+X_{2}:1+3AX_{1}^{2}X_{2}^{2}:(X_{1}+X_{2})^{3}\big{)},$

which is equal to $\big{(}X_{1}+X_{2}:1:(X_{1}+X_{2})^{3}\big{)}$ as we verify
by multiplying its entries by
$1-3AX_{1}^{2}X_{2}^{2}\in(\mathbb{Z}/p^{5\min\\{e_{1},e_{2}\\}}\mathbb{Z})^{*}$.
∎

We can now prove that the infinity group is cyclic, which provides a structure
theorem for elliptic curves over $\mathbb{Z}/N\mathbb{Z}$.

######  Theorem 14.

Let $p$ be a prime, $e\in\mathbb{Z}_{\geq 1}$ and $\mathsf{f}\in\mathbb{Z}[x]$
be the polynomial arising from $E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ as in
Proposition 11. Then

$0\to\big{\langle}\big{(}p:1:\mathsf{f}(p)\big{)}\big{\rangle}\stackrel{{\scriptstyle\iota}}{{\hookrightarrow}}E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\stackrel{{\scriptstyle\pi}}{{\to}}E_{A,B}(\mathbb{F}_{p})\to
0.$

is a short exact sequence of groups.

###### Proof.

We know that the canonical projection
$\pi:E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\twoheadrightarrow
E_{A,B}(\mathbb{F}_{p})$ is a surjective group homomorphism and that
$|\ker\pi|=p^{e-1}$ by Lemma 10. Thus, it is sufficient to prove that
$P=\big{(}p:1:\mathsf{f}(p)\big{)}\in\ker\pi$ has order $p^{e-1}$. Since $P$
lies over $\mathcal{O}\in E_{A,B}(\mathbb{F}_{p})$, then its order is a power
of $p$ ($\ker\pi$ is a $p$-group). We prove by induction on $0\leq\epsilon\leq
e-1$ that

$p^{\epsilon}P=\big{(}X:1:\mathsf{f}(X)\big{)}\quad\text{ and
}\quad\mathrm{v}_{p}(X)=\epsilon+1.$

In particular, the minimal $\epsilon$ such that $X\equiv 0\bmod p^{e}$ is
$\epsilon=e-1$.
$[\epsilon=0]$ It is trivially seen that

$p^{0}P=\big{(}p:1:\mathsf{f}(p)\big{)}\quad\text{ and
}\quad\mathrm{v}_{p}(p)=1.$

$[\epsilon\rightarrow\epsilon+1]$ By the inductive hypothesis we know that

$p^{\epsilon+1}P=p(p^{\epsilon}P)=p\big{(}X:1:\mathsf{f}(X)\big{)}\quad\text{
and }\quad\mathrm{v}_{p}(X)=\epsilon+1.$

By Proposition 13 and induction on $\alpha\in\\{1,\dots,p-1\\}$ we have

$\big{(}X:1:\mathsf{f}(X)\big{)}+\big{(}\alpha X:1:\mathsf{f}(\alpha
X)\big{)}=\big{(}X_{2}:1:\mathsf{f}(X_{2})\big{)},$

with

$X_{2}\equiv(\alpha+1)X\bmod p^{5(\epsilon+1)}.$

Thus, by specializing the above result for $\alpha=p-1$, the $p$-adic
valuation of the first component of $p\big{(}X:1:\mathsf{f}(X)\big{)}$ is
proved to be $\mathrm{v}_{p}(X)+1=\epsilon+2$. ∎

The above theorem shows that the infinity part of any elliptic curve over
$\mathbb{Z}/p^{e}\mathbb{Z}$ is a $\mathbb{Z}/p^{e}\mathbb{Z}$-torsor with
respect to the standard multiplication-action. This is sufficient to determine
the group structure of these curves when their projection is not anomalous.

######  Corollary 15.

Let $p$ be a prime, $e\in\mathbb{Z}_{\geq 1}$ and
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ be an elliptic curve such that
$|E_{A,B}(\mathbb{F}_{p})|\neq p$. Then

$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\simeq
E_{A,B}(\mathbb{F}_{p})\oplus\mathbb{Z}/p^{e-1}\mathbb{Z}.$

###### Proof.

It is sufficient to show that the short exact sequence provided by Theorem 14
is a split sequence, which by the Splitting Lemma amounts to proving that it
is left split. Since $q=|E_{A,B}(\mathbb{F}_{p})|\neq p$ is in the Hasse bound
of $p$, then $(p,q)=1$, which implies that there is $k\in\mathbb{Z}$
satisfying

$\begin{cases}k\equiv 1\bmod p^{e-1},\\\ k\equiv 0\bmod q.\end{cases}$

By Theorem 14 we have
$E_{A,B}^{\infty}(\mathbb{Z}/p^{e}\mathbb{Z})=\pi^{-1}(\mathcal{O})=\big{\langle}\big{(}p:1:\mathsf{f}(p)\big{)}\big{\rangle}$.
Thus, since $k\equiv 0\bmod q$, the map

$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\stackrel{{\scriptstyle\cdot
k}}{{\to}}\big{\langle}\big{(}p:1:\mathsf{f}(p)\big{)}\big{\rangle}$

is a well-defined group homomorphism. Moreover, since $k\equiv 1\bmod
p^{e-1}$, the cyclic group
$\big{\langle}\big{(}p:1:\mathsf{f}(p)\big{)}\big{\rangle}$ is fixed under
this map, hence the multiplication-by-$k$ is a left section for the considered
sequence. ∎

When the exponent $e$ is small, an explicit group isomorphism may also be
exhibited.

######  Proposition 16.

Let $p$ be a prime, $1\leq e\leq 5$ be an integer,
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ be an elliptic curve and
$q=|E_{A,B}(\mathbb{F}_{p})|$ be the size of its projected curve. Then

$\displaystyle\Phi:E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ $\displaystyle\to
E_{A,B}(\mathbb{F}_{p})\oplus\mathbb{Z}/p^{e-1}\mathbb{Z},$ $\displaystyle P$
$\displaystyle\mapsto\left(\pi(P),\frac{1}{p}\frac{(qP)_{x}}{(qP)_{y}}\right),$

is a well-defined group homomorphism.
Moreover, if $q\neq p$ then $\Phi$ is a group isomorphism.

###### Proof.

It is easy to see that $\Phi(P)$ does not depend on the projective
representative of $P$. Moreover, as $\pi$ is a group homomorphism we have

$\pi(qP)=q\pi(P)=\mathcal{O}\in E_{A,B}(\mathbb{F}_{p}).$

Hence, by Proposition 11 we have $qP=\big{(}X:1:\mathsf{f}(X)\big{)}$ with
$X\in p(\mathbb{Z}/p^{e}\mathbb{Z})$. Therefore, $\frac{(qP)_{x}}{(qP)_{y}}\in
p(\mathbb{Z}/p^{e}\mathbb{Z})$, which is canonically isomorphic to
$\mathbb{Z}/p^{e-1}\mathbb{Z}$. Thus, $\Phi$ is a well-defined map between
groups having, by Lemma 10, the same size. It also respects the sum, as for
every pair $P_{1},P_{2}\in E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ we compute

$\Phi(P_{1})+\Phi(P_{2})=\left(\pi(P_{1}+P_{2}),\frac{1}{p}\left(\frac{(qP_{1})_{x}}{(qP_{1})_{y}}+\frac{(qP_{2})_{x}}{(qP_{2})_{y}}\right)\right),$

and since $e\leq
5\min\\{\mathrm{v}_{p}\big{(}(qP_{1})_{x}\big{)},\mathrm{v}_{p}\big{(}(qP_{2})_{x}\big{)}\\}$,
then by Proposition 13 we have

$\frac{(qP_{1})_{x}}{(qP_{1})_{y}}+\frac{(qP_{2})_{x}}{(qP_{2})_{y}}=\frac{(qP_{1}+qP_{2})_{x}}{(qP_{1}+qP_{2})_{y}}=\frac{\big{(}q(P_{1}+P_{2})\big{)}_{x}}{\big{(}q(P_{1}+P_{2})\big{)}_{y}}.$

As for the moreover part, it is sufficient to prove that
$\ker\Phi=\\{\mathcal{O}\\}$ when $q\neq p$. Let $\Phi(P)=(\mathcal{O},0)$,
then there exists $X\in p(\mathbb{Z}/p^{e}\mathbb{Z})$ such that
$P=\big{(}X:1:\mathsf{f}(X)\big{)}$ and

$\frac{qX}{p}\equiv\frac{(qP)_{x}}{p}\equiv 0\bmod{p^{e-1}}.$

Since $q$ lies in the Hasse interval of $p$, then $q\neq p$ implies $(p,q)=1$
and we conclude that $X\equiv 0\bmod{p^{e}}$, hence the kernel of $\Phi$ is
trivial. ∎

When the restricted curve $E_{A,B}(\mathbb{F}_{p})$ is anomalous two different
scenarios may occur. By Theorem 14 the curve
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ is guaranteed to contain a cyclic
subgroup of order $p^{e-1}$, therefore it may be either cyclic

$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\simeq\mathbb{Z}/p^{e}\mathbb{Z},$
(Cyclic)

or split, i.e.

$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\simeq\mathbb{F}_{p}\oplus\mathbb{Z}/p^{e-1}\mathbb{Z}.$
(Split)

Even if the cyclic case occurs over $\mathbb{Z}/p^{e}\mathbb{Z}$ with an
overwhelming probability ($\frac{p-1}{p}$), both may take place. As an
instance, one may check that

$E_{7,3}(\mathbb{Z}/13^{2}\mathbb{Z})\simeq\langle(0:61:1)\rangle,\quad\text{while}\quad
E_{1,6}(\mathbb{Z}/13^{2}\mathbb{Z})\simeq\langle(2:4:1)\rangle\oplus\langle(13:1:0)\rangle.$

The above discussion leads to the classification theorem.

######  Theorem 17.

Let $N$ be a positive integer and let $A,B$ be integers such that
$\Delta_{A,B}$ is coprime to $N$. Then we have

$E_{A,B}(\mathbb{Z}/N\mathbb{Z})\simeq\bigoplus_{\begin{subarray}{c}p|N\\\
|E_{A,B}(\mathbb{F}_{p})|\neq
p\end{subarray}}E_{A,B}(\mathbb{F}_{p})\oplus\mathbb{Z}/p^{\mathrm{v}_{p}(N)-1}\mathbb{Z}\oplus\bigoplus_{\begin{subarray}{c}p|N\\\
|E_{A,B}(\mathbb{F}_{p})|=p\end{subarray}}G_{p},$

where every $G_{p}$ may be either $\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z}$
or $\mathbb{F}_{p}\oplus\mathbb{Z}/p^{\mathrm{v}_{p}(N)-1}\mathbb{Z}$.

###### Proof.

By Proposition 9 we know that

$E_{A,B}(\mathbb{Z}/N\mathbb{Z})\simeq\bigoplus_{p|N}E_{A,B}(\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z}).$

By Corollary 15, for every $p$ such that $E_{A,B}(\mathbb{F}_{p})$ is not
anomalous we have

$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})\simeq
E_{A,B}(\mathbb{F}_{p})\oplus\mathbb{Z}/p^{\mathrm{v}_{p}(N)-1}\mathbb{Z}.$

On the other side, we have seen that

$G_{p}=\mathbb{F}_{p}\oplus\mathbb{Z}/p^{\mathrm{v}_{p}(N)-1}\mathbb{Z}\qquad\text{or}\qquad
G_{p}=\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z}$

may both occur as group structure of
$E_{A,B}(\mathbb{Z}/p^{\mathrm{v}_{p}(N)}\mathbb{Z})$ when
$E_{A,B}(\mathbb{F}_{p})$ is anomalous, which completes the study cases. ∎

######  Remark 18.

Given a finite collection of elliptic curves
$\\{E_{A_{l},B_{l}}(R_{l})\\}_{1\leq l\leq k}$, we may define an elliptic
curve over their product ring $\prod_{l=1}^{k}R_{l}$ with the componentwise
operation and [12, Section 4] we have

$E_{(A_{1},\dots,A_{k}),(B_{1},\dots,B_{k})}\left(\prod_{l=1}^{k}R_{l}\right)\simeq\prod_{l=1}^{k}E_{A_{l},B_{l}}(R_{l}).$

Thus, Theorem 17 provides the group structures of every elliptic curve defined
over a ring isomorphic to a finite product of integer residue rings.

######  Remark 19.

We notice that Theorem 14 really depends on elliptic curves behavior over
$\mathbb{Z}/p^{e}\mathbb{Z}$. Let us consider another local ring
$R=\mathbb{F}_{5}[x]/(x^{4})$ and let $\epsilon$ be a generator of its maximal
ideal. It defines a canonical projection

$R\to\mathbb{F}_{5},\quad
X_{0}+X_{1}\epsilon+X_{2}\epsilon^{2}+X_{3}\epsilon^{3}\mapsto X_{0},$

so we have an elliptic curve $E_{1,2}(R)$ defined as in Section 2.3, together
with a canonical projection onto $E_{1,2}(\mathbb{F}_{5})$.

This curve may appear similar to $E_{1,2}(\mathbb{Z}/5^{4}\mathbb{Z})$ at a
first glance, but one can directly verify that $E_{1,2}(R)$ is given by

$\langle(2\epsilon^{3}+\epsilon:1:\epsilon^{3})\rangle\oplus\langle(3\epsilon^{3}+3\epsilon^{2}+2\epsilon:1:3\epsilon^{3})\rangle\oplus\langle(\epsilon^{3}+\epsilon+3:\epsilon^{3}+3\epsilon^{2}+4\epsilon+3:1)\rangle,$

so that
$E_{1,2}(R)\simeq\mathbb{Z}/5\mathbb{Z}\oplus\mathbb{Z}/5\mathbb{Z}\oplus\mathbb{Z}/35\mathbb{Z}$.
This is due to the different structure of the infinity parts, as
$E^{\infty}_{1,2}(R)\simeq(\mathbb{Z}/5\mathbb{Z})^{\oplus 3}$, while
$E^{\infty}_{1,2}(\mathbb{Z}/5^{4}\mathbb{Z})\simeq\mathbb{Z}/5^{3}\mathbb{Z}$
as prescribed by our previous results.

##  4 Rank of $p$-groups from elliptic curves

We know that groups arising from elliptic curves defined over finite fields
have prescribed constraints [18, 26], e.g. their rank cannot exceed $2$. This
restriction can be relaxed for curves defined over $\mathbb{Z}/N\mathbb{Z}$,
as their rank may be arbitrarily large, but it may still be bounded in terms
of the the number of primes inside an Hasse interval.

######  Definition 20 ($\mathcal{H}_{p}$).

Given an integer $p\in\mathbb{Z}$, we define

$\mathcal{H}_{p}=|\\{q\in\mathbb{Z}\ |\ q\text{ is prime and
}p+1-2\sqrt{p}\leq q\leq p+1+2\sqrt{p}\\}|.$

The following result provides a sharp bound on the rank that elliptic curves
over $\mathbb{Z}/N\mathbb{Z}$ may have if their point group are $p$-groups,
which in particular shows that there are infinitely many groups that cannot
arise as a point group for an elliptic curve over an integer residue ring.

######  Proposition 21.

Let $p\geq 5$ be a prime, $N\in\mathbb{Z}_{\geq 2}$ and
$E=E_{A,B}(\mathbb{Z}/N\mathbb{Z})$ be an elliptic curve that is a $p$-group.
Then, by defining

$\chi_{p}=\begin{cases}2&\text{if there is a prime $q$ such that
}E_{A,B}(\mathbb{F}_{q})\simeq\mathbb{F}_{p}\oplus\mathbb{F}_{p},\\\
0&\text{otherwise},\end{cases}$

we have

$\textnormal{rk}(E)\leq\mathcal{H}_{p}+\chi_{p}+1.$

###### Proof.

By Theorem 17 we have

$E\simeq\bigoplus_{\begin{subarray}{c}q|N\\\ |E_{A,B}(\mathbb{F}_{q})|\neq
q\end{subarray}}E_{A,B}(\mathbb{F}_{q})\oplus\mathbb{Z}/q^{\mathrm{v}_{q}(N)-1}\mathbb{Z}\oplus\bigoplus_{\begin{subarray}{c}q|N\\\
|E_{A,B}(\mathbb{F}_{q})|=q\end{subarray}}G_{q},$

where every $G_{q}$ may be either $\mathbb{Z}/q^{\mathrm{v}_{q}(N)}\mathbb{Z}$
or $\mathbb{F}_{q}\oplus\mathbb{Z}/q^{\mathrm{v}_{q}(N)-1}\mathbb{Z}$. It is
easy to see that $G_{q}$ is a $p$-group only if $q=p$, hence we have

$\textnormal{rk}\bigoplus_{\begin{subarray}{c}q|N\\\
|E_{A,B}(\mathbb{F}_{q})|=q\end{subarray}}G_{q}\leq 2.$

Similarly, we notice that $\mathbb{Z}/q^{\mathrm{v}_{q}(N)-1}\mathbb{Z}$ is a
$p$-group only if $q=p$, but $E_{A,B}(\mathbb{F}_{p})$ is a $p$-group if and
only if $|E_{A,B}(\mathbb{F}_{p})|=p$. Thus, we have

$\bigoplus_{\begin{subarray}{c}q|N\\\ |E_{A,B}(\mathbb{F}_{q})|\neq
q\end{subarray}}E_{A,B}(\mathbb{F}_{q})\oplus\mathbb{Z}/q^{\mathrm{v}_{q}(N)-1}\mathbb{Z}\simeq\bigoplus_{\begin{subarray}{c}q|N\\\
q\neq p\end{subarray}}E_{A,B}(\mathbb{F}_{q}).$

Moreover, since the rank of $E_{A,B}(\mathbb{F}_{q})$ is at most $2$ [27,
Theorem 4.1], then it is a $p$-group only if

$\text{either}\qquad
E_{A,B}(\mathbb{F}_{q})\simeq\mathbb{F}_{p}\qquad\text{or}\qquad
E_{A,B}(\mathbb{F}_{q})\simeq\mathbb{F}_{p}\oplus\mathbb{F}_{p}.$

Since the Hasse buond over a prime field is full, then
$E_{A,B}(\mathbb{F}_{q})$ may be isomorphic to $\mathbb{F}_{p}$ for every
prime $q$ inside the Hasse interval of $p$.

On the other side, by [27, Prop.4.16] we know that
$E_{A,B}(\mathbb{F}_{q})\simeq\mathbb{F}_{p}\oplus\mathbb{F}_{p}$ may occur
only if

$q\in\\{p^{2}+1,p^{2}\pm p+1,p^{2}\pm 2p+1\\}.$

However, both $p$ and $q$ are odd primes, hence only $q=p^{2}\pm p+1$ may
occur. Furthermore, since $p>3$, it is easy to see that either $3|p^{2}+p+1$
or $3|p^{2}-p+1$, therefore only one of them can be prime. We conclude that
there is at most one prime $q$ such that
$E_{A,B}(\mathbb{F}_{q})\simeq\mathbb{F}_{p}\oplus\mathbb{F}_{p}$, so that

$\textnormal{rk}\bigoplus_{\begin{subarray}{c}q|N\\\ q\neq
p\end{subarray}}E_{A,B}(\mathbb{F}_{q})\leq(\mathcal{H}_{p}-1)+\chi_{p}.$

Collecting the above rank bounds, the statement follows. ∎

######  Example 22.

Let $p=11$. None of $11^{2}\pm 11+1$ is prime, then we have $\chi_{11}=0$,
therefore by Proposition 21, regardless of $N\in\mathbb{Z}_{\geq 2}$, the rank
of any elliptic curve over $\mathbb{Z}/N\mathbb{Z}$ that is a $11$-group is
bounded by $\mathcal{H}_{11}+1=5$. We also notice that this bound is sharp, as

$E_{167707,21664}(\mathbb{Z}/187187\mathbb{Z})\simeq\mathbb{F}_{11}\oplus\mathbb{F}_{11}\oplus\mathbb{F}_{11}\oplus\mathbb{F}_{11}\oplus\mathbb{F}_{11}.$

######  Example 23.

Let $p=13$. We notice that $13^{2}-13+1=157$ is prime and

$E_{0,15}(\mathbb{F}_{157})\simeq\mathbb{F}_{13}\oplus\mathbb{F}_{13},$

therefore we have $\chi_{13}=2$. By means of Proposition 21 we know that any
elliptic curve over $\mathbb{Z}/N\mathbb{Z}$ that is a $13$-group has rank
bounded by $\mathcal{H}_{13}+3=8$. We notice again that this bound is sharp,
as

$E_{63707931,239467091}(\mathbb{Z}/659902243\mathbb{Z})\simeq(\mathbb{F}_{13})^{\oplus
8}.$

##  5 Another isomorphism attack to anomalous ECDLP

Given an additive group $G$ and a base element $g\in G$, the discrete
logarithm problem (DLP) on $G$ consists of computing for any given $h\in G$ an
integer $N$, if existent, such that $h=N\cdot g=g+g+\dots+g$. When $G$ is the
point group of an elliptic curve (ECDLP), this problem is known to be
computationally feasible only in special cases, such as the anomalous ones
[22, 20, 25].

From the knowledge of the group structure provided by Theorem 14, we have
another way for efficiently solving the ECDLP on anomalous curves by employing
any cyclic curve that projects onto it.

######  Proposition 24.

Let $p$ be a prime, $e\in\mathbb{Z}_{\geq 2}$ and
$E=E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ be an elliptic curve, whose point
group is cyclic of order $p^{e}$. Then the map

$\displaystyle\Theta:E$ $\displaystyle\to\mathbb{F}_{p},$ $\displaystyle P$
$\displaystyle\mapsto\frac{1}{p^{e-1}}\frac{(p^{e-1}P)_{x}}{(p^{e-1}P)_{y}},$

is a well-defined surjective group homomorphism, whose kernel is

$\ker\Theta=\big{\langle}\big{(}p:1:\mathsf{f}(p)\big{)}\big{\rangle}.$

###### Proof.

For every $P\in E$ the point $p^{e-1}P$ is a $p$-torsion point of $E$, hence

$p^{e-1}P=\big{(}X:1:\mathsf{f}(X)\big{)},\qquad\text{ with }\
\mathrm{v}_{p}(X)\geq e-1,$

therefore $\Theta(P)=\frac{X}{p^{e-1}}\in\mathbb{F}_{p}$ is well-defined. Let
$G\in E$ be a generator of the point group of $E$, then for every integer
$m\in\mathbb{Z}$ we have

$p^{e-1}mG=m\big{(}X:1:\mathsf{f}(X)\big{)}=\big{(}mX:1:\mathsf{f}(mX)\big{)},$

where the last equality follows from Proposition 13, as for every $e\geq 2$
the point $p^{e-1}G$ lies in $\langle(p^{e-1}:1:0)\rangle$. Thus,
$\Theta(mG)=m\Theta(G)$, so that $\Theta$ is a group homomorphism. Moreover,
from the above equation it follows that

$\ker\Theta=\\{mp\ G\ |\
m\in\mathbb{Z}\\}=\big{\langle}\big{(}p:1:\mathsf{f}(p)\big{)}\big{\rangle}.$

By comparing the size of these groups, the surjectivity follows. ∎

From the above proposition, the discrete logarithm over anomalous curves may
be immediately recovered.

######  Corollary 25.

Let $p$ be a prime, $e\in\mathbb{Z}_{\geq 2}$ and
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})$ be an elliptic curve, whose point group
is cyclic of order $p^{e}$. Then the map

$\Theta\circ\pi^{-1}:E_{A,B}(\mathbb{F}_{p})\to\mathbb{F}_{p}$

is a well-defined group isomorphism.

###### Proof.

By Theorem 14 the canonical projection induces a group isomorphism
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})/\langle(p:1:\mathsf{f}(p))\rangle\simeq
E(\mathbb{F}_{p})$, whereas the map $\Theta$ arisen from Proposition 24
induces a group isomorphism
$E_{A,B}(\mathbb{Z}/p^{e}\mathbb{Z})/\langle(p:1:\mathsf{f}(p))\rangle\simeq\mathbb{F}_{p}$.
By composing those isomorphisms, the result follows. ∎

Finding any lift of a given point is computationally costless, therefore the
complexity of the isomorphism attack given by Corollary 25 only depends on the
cost of computing $\Theta$, which is $O(\log p)$. This approach is not faster
than previously known attacks to the same family of curves, but it has the
advantage of involving only finite precision objects.

######  Example 26.

Let us consider an anomalous curve as constructed in [14]:

$\displaystyle p$
$\displaystyle=730750818665451459112596905638433048232067471723,$
$\displaystyle A$
$\displaystyle=425706413842211054102700238164133538302169176474,$
$\displaystyle B$
$\displaystyle=203362936548826936673264444982866339953265530166.$

We consider on $E_{A,B}(\mathbb{F}_{p})$ the points

$\displaystyle P$
$\displaystyle=(1:310536468939899693718962354338996655381367569020:1),$
$\displaystyle Q$
$\displaystyle=(3:38292783053156441019740319553956376819943854515:1).$

To find their discrete logarithm it is sufficient to compute any lifts, such
as

$P^{\uparrow}=(1:P_{y}+\alpha p:1),\ Q^{\uparrow}=(3:Q_{y}+\beta p:1)\in
E_{A,B}(\mathbb{Z}/p^{2}\mathbb{Z}),$

where

$\alpha=\frac{1+A+B-P_{y}^{2}}{2pP_{y}}\bmod p^{2},\
\beta=\frac{27+3A+B-Q_{y}^{2}}{2pQ_{y}}\bmod p^{2},$

and to apply them the group homomorphism $\Theta$ of Proposition 24:

$\displaystyle\Theta(P^{\uparrow})$
$\displaystyle=343088892565802863386490109374548044078624360215,$
$\displaystyle\Theta(Q^{\uparrow})$
$\displaystyle=470974712001084540433398653921983741661987449793.$

This way we get the discrete logarithm $N$ such that $Q=N\cdot P$ as

$N=\frac{\Theta(Q^{\uparrow})}{\Theta(P^{\uparrow})}\bmod
p=113690975836469390483838646646828917131453128585.$

We remark that such a discrete logarithm would be unfeasible to be computed
with generic logarithm techniques, as one can directly verify that the Log
routine of Magma [4] does not terminate in a reasonable time.

##  6 Conclusions and open problems

In this work we have completed the classification of groups arising from
elliptic curves over $\mathbb{Z}/N\mathbb{Z}$ and exploited it for obtaining a
bound for these curve’s rank and an attack to the ECDLP over anomalous
elliptic curves.

The key ingredient is Theorem 14, which might still hold for more general
classes of rings, even though the kernel generator may be less explicit. We
consider the attempt of relaxing its hypotheses interesting from a theoretical
point of view, and finite discrete valuation rings might be suitable
candidates.

From a cryptographic perspective, Theorem 14 shows that for achieving
difficult ECDLPs, the infinity part of the considered elliptic curves needs to
be unrelated with the base-curve (as it was already known), or it needs to own
non-cyclical elements, which may be exploited for constructing isomorphism
attacks.

Finally, it may be investigated which other abelian varieties admit such an
extension to $\mathbb{Z}/N\mathbb{Z}$ and, when it is the case, if analogous
group decompositions over these rings hold. The latter attempt is considered
as interesting as challenging.

## Acknowledgments

This article has been supported in part by the European Union’s H2020
Programme under grant agreement number ERC-669891.

## References

  * [1] W. D. Banks, F. Pappalardi, and I. E. Shparlinski, _On Group Structures Realized by Elliptic Curves over Arbitrary Finite Fields_ , Experiment. Math. 21, 2012, pp. 11–25.
  * [2] W. Bosma, _Primality testing using elliptic curves_ , Math. Instituut, Univ. Amsterdam, volume Tech. Rep. 85–12, 1985.
  * [3] W. Bosma and H. W. Lenstra, _Complete Systems of Two Addition Laws for Elliptic Curves_ , J. Number Theory 53, 1995, pp. 229–240.
  * [4] W. Bosma, J. Cannon, and Catherine Playoust, _The Magma algebra system. I. The user language_ , J. Symbolic Comput. 24, 1997, pp. 235–265.
  * [5] C. Breuil, B. Conrad, F. Diamond, and R. Taylor, _On the modularity of elliptic curves over Q: wild 3-adic exercises_ , J. Amer. Math. Soc. 14, 2001, pp. 843–939.
  * [6] W. C. Brown _Matrices over commutative rings_ , Marcel Dekker, 1986.
  * [7] D. Husemöller, Elliptic Curves, Grad. Texts in Math. 111. Springer-Verlag, 1987.
  * [8] D. Johnson, A. Menezes, and S. Vanstone, The Elliptic Curve Digital Signature Algorithm (ECDSA), Int. J. Inf. Secur. 1, 2001, pp. 36–63.
  * [9] N. Koblitz, _Elliptic curve cryptosystems_ , Math. Comp. 48, 1987, pp. 203–209.
  * [10] D. R. Kohel and I. E. Shparlinski, _On Exponential Sums and Group Generators for Elliptic Curves over Finite Fields_ , Lecture Notes in Comput. Sci. 21, 2000, pp. 395–404.
  * [11] H. Lange and W. Ruppert, Complete systems of addition laws on abelian varieties, Invent. Math. 79, 1985, pp. 603–610.
  * [12] H. W. Lenstra, _Elliptic curves and number-theoretic algorithms_ , Proc. of the International Congress of Mathematicians, 1986, pp. 99–120.
  * [13] H. W. Lenstra, _Factoring integers with elliptic curves_ , Ann. of Math. 126, 1987, pp. 649–673.
  * [14] F. Leprévost, J. Monnerat, S. Varrette, and S. Vaudenay, _Generating Anomalous Elliptic Curves_ , Inform. Process. Lett. 93, 2005, pp. 225–230.
  * [15] L. Merel, _Bornes pour la torsion des courbes elliptiques sur les corps de nombres_ , Invent. Math. 124, 1996, pp. 437–449.
  * [16] V. S. Miller. _Use of elliptic curves in cryptography_ , Adv. Cryptol. 218, 1985, pp. 417–426.
  * [17] L. J. Mordell, _On the rational solutions of the indeterminate equations of the third and fourth degrees_ , Proc. Camb. Phil. Soc. 21, 1922, pp. 179–192.
  * [18] H. G. Rück, _A Note on Elliptic Curves Over Finite Fields_ , Math. Comp. 49, 1987, pp. 301–304.
  * [19] M. Sala and D. Taufer, _A survey on the group of points arising from elliptic curves with a Weierstrass model over a ring_ , Accepted in Int. J. Group Theory, 2022. Available at https://ijgt.ui.ac.ir/article_26665.html.
  * [20] T. Satoh and K. Araki, _Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves_ , Comm. Math. Univ. Sancti Pauli 47, 1998, pp. 81–92.
  * [21] R. Schoof, _Elliptic Curves over Finite Fields and the Computation of Square Roots mod p_ , Math. Comp. 44, 1985, pp. 483–494.
  * [22] I. A. Semaev, _Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p_ , Math. Comp. 67, 1998, pp. 353–356.
  * [23] I. E. Shparlinski, _Pseudorandom number generators from elliptic curves_ , Contemp. Math. 477, 2009, pp. 121–142.
  * [24] J. H. Silverman, _The arithmetic of elliptic curves_ , Springer-Verlag, 1986.
  * [25] N. Smart, _The discrete logarithm on elliptic curves of trace one_ , J. Cryptology 12, 1999, pp. 193–196.
  * [26] J. F. Voloch, _A note on elliptic curves over finite fields_ , Bull. Soc. Math. France 116, 1988, pp. 455–458.
  * [27] L. C. Washington, _Elliptic curves, number theory and cryptography_ , Chapman & Hall / CRC, 2008.
  * [28] W. C. Waterhouse, _Abelian varieties over finite fields_ , Ann. Sci. École Norm. Sup 2., 1969, pp. 521–560.
  * [29] A. Wiles, _Modular elliptic curves and Fermat’s Last Theorem_ , Ann. Math. 142, 1995, pp. 443–551.