# Extending Lenstra’s Primality Test to CM Elliptic Curves and a new Quasi-
Quadratic Las Vegas Algorithm for Primality

Tejas Rao

(December 2022)

###### Abstract

For an elliptic curve with CM by $K$ defined over its Hilbert class field,
$E/H$, we extend Lenstra’s finite fields test to generators of norms of
certain ideals in $\mathcal{O}_{H}$, yielding a sufficient
$\widetilde{O}(\log^{3}N)$ primality test and partially answering an open
question of Lemmermeyer in the case of CM elliptic curves. Letting
$\iota,\gamma,b\in\mathcal{O}_{K}$, $(\iota)$ prime, and $b$ a primitive
$k$-th root of unity modulo $(\iota)^{n}$ we specialize this test to rational
integers of the form $N_{K/\mathbb{Q}}(\gamma\iota^{n}+b)$ with the norm of
$\gamma$ small, giving a Las Vegas test for primality with average runtime
$\widetilde{O}(\log^{2}N)$, that further certifies primality of such integers
in $\widetilde{O}(\log^{2}N)$ for nearly all choices of input parameters. The
integers tested were not previously amenable to quasi-quadratic heuristic
primality certification.

##  1 Preliminaries

Fast primality testing of a rational integer $N$ relies on a theme of Lucas,
wherein a finite group is constructed so (provably) large that $N$ must be
prime. Pomerance outlines the classical methods arising from this theme [26].
The binary modular exponentiation central to this Lucasian theme runs in
$\widetilde{O}(\log^{2}N)$, providing a hypothetical lower bound to all
primality testing barring a new theme. Pomerance proved that this hypothetical
minimum bound is met: there exist $\widetilde{O}(\log^{2}N)$ certifications of
primality for every rational prime [25, 26]. _Finding_ these certifications,
i.e. testing for primality, is another story. The fastest classical test
relies on a known factorization of $N^{k}-1$ for some fixed small
$k\in\mathbb{N}$, and runs in heuristic $\widetilde{O}(\log^{3}N)$ time:

######  Theorem 1.1 (Lenstra’s Finite Fields Test, [26, 20]).

Let $N,k$ positive integers, $N>1$ and $f\in(\mathbb{Z}/N\mathbb{Z})[x]$ monic
of degree $k$. Suppose that $F|N^{k}-1$, $F>\sqrt{N}$, and $F$ has a known
prime factorization. If $\exists g\in(\mathbb{Z}/N\mathbb{Z})[x]$ such that in
$(\mathbb{Z}/N\mathbb{Z})[x]/(f)$,

$\displaystyle\text{(1) }g^{F}=1,$ $\displaystyle\text{(2)
}\gcd(g^{\frac{F}{q}}-1,f)=1,\text{ for each prime }q|F,$
$\displaystyle\text{(3) }\text{each elementary symmetric polynomial in
}g^{N^{j}},0\leq j\leq{k-1}$ $\displaystyle\text{ has coefficients in
}\mathbb{Z}/N\mathbb{Z},$

and if none of the residues $N^{j}\mod F$, $0\leq j\leq k-1$, are proper
factors of $N$, then $N$ is prime.

Similar to Pocklington’s criterion, multiple bases $g$ may be chosen [20]. The
algorithm runs in heuristic $\widetilde{O}(k^{2}\log^{3}N)$, and tests based
on it are referred to as cyclotomic primality tests [7]. The runtime of this
algorithm is deterministically $\widetilde{O}(\log^{2}N)$ if $k$ is small and
fixed, the number of prime powers of $F$ is polynomial in $\log\log N$, and a
suitable $g$ (or multiple bases) is known; it remains heuristic
$\widetilde{O}(\log^{2}N)$ time even if the bases $g$ are not known
beforehand. This is the hypothetical minimum runtime of Lucasian tests, and an
algorithm having such (at least heuristic) runtime will henceforth be referred
to as an efficient primality test.

Beyond classical primality testing, the theory of Ellipitic Curve Primality
Proving (ECPP) has been developed by such figues as Goldwasser, Kilian, Atkin,
and Morain [11, 4]. In the seminal Elliptic Curve Primality Proving paper by
Atkin and Morain [4], the theory of complex multiplication (CM) is used to
determine the orders of the groups of points of certain elliptic curves and
test for primality of any positive integer $N$. An asymptotically-fast version
due to Shallit runs in heuristic $\widetilde{{O}}(\log^{4}N)$ time and stands
as our fastest general algorithm in practice [23, 18]. More recently,
Milhailescu proposed a variant general primality test running one round of
cyclotomic primality testing, followed by a round of ECPP, running in
heuristic $\widetilde{O}(\log^{3}N)$ time, which would stand as the fastest
general algorithm [21]. Importantly, it does not reduce to an _efficient
primality test_ when the number of prime power factors of $F$ is polynomial in
$\log\log N$. General testing is not yet $\widetilde{O}(\log^{2}N)$, and thus
there has been work done to determine heuristic $\widetilde{O}(\log^{2}N)$
testing utilizing elliptic curves, including the works of Gurevich and
Kunyavskiĭ, Tsumura, Gross, Denomme and Savin, and Chudnovsky and Chudnovsky
[15, 34, 14, 9, 5]. In addition, Abatzoglou, Sutherland, Wong, and Silverberg
use CM elliptic curves to provide a framework for deterministic efficient
primality testing for certain sequences of integers not amenable to classical
testing, utilizing elliptic curves with CM by the rings of integers of
$\mathbb{Q}[\sqrt{-7}],\mathbb{Q}[\sqrt{-15}]$ [2, 1]. A recent preprint in
the same vein proposes an extension of the results to class number $3$ [24].
These works expand the class of rational integers amenable to efficient
primality testing, including those of the form
$N_{K/\mathbb{Q}}(\gamma\iota^{k}+1)$ for $\iota,\gamma\in\mathcal{O}_{K}$,
$K$ an imaginary quadratic field, when there is an elliptic curve over the
Hilbert class field with CM by $\mathcal{O}_{K}$ and the norm of $\gamma$ is
small. Along with rational integers $N$ such that $N^{k}-1$ is highly factored
into a small number of distinct prime factors using Lenstra’s finite fields
test, these are the integers most amenable to efficient primality testing in
the literature. Some remarks on the state of efficient elliptic curve
primality testing are made by Silverberg in [30].

In the open problems section of his celebrated work Reciprocity Laws: From
Euler to Eisenstein [17, Appendix C], Lemmermeyer asks:

Can Lenstra’s Primality Test be generalized so as to include primality tests
based on elliptic curves?

In this paper, we answer this question in the affirmative for certain inputs
in the case of CM elliptic curves, producing an analogue heuristic
$\widetilde{O}(k^{2}\log^{3}N)$ primality test for a new class of rational
integers that reduces to heuristic $\widetilde{O}(\log^{2}N)$ time when $k$
and the number of certain prime power factors is small. To avoid precomputing
the complex isogenies of the CM elliptic curve, we introduce another efficient
primality test for a smaller new class of rational integers, this time which
provides a certificate of primality of a prime $p$ in one trial with
probability $1-1/p^{\alpha}$ for some reasonably-sized $\alpha$, and is a Las
Vegas primality algorithm with average runtime $\widetilde{O}(\log^{2}N)$. The
methodology to ensure certification of primality in one trial with high
probability is inspired by that of Grau, Marcén, and Sadornil [13, 12]. We
describe the implementation of the algorithm and give an example of rational
integers amenable to primality testing by it. In particular, this Las Vegas
primality algorithm can test rational integers in sequences of the form

$N_{K/\mathbb{Q}}(\gamma\iota^{k}+b)$

where $\gamma,\iota\in\mathcal{O}_{K}$ for some quadratic imaginary field $K$
and $N_{K/\mathbb{Q}}(\iota^{n})>N^{1/2+\alpha}$, with the following
precomputed information: an elliptic curve $E/H$ with CM by $\mathcal{O}_{K}$,
a rational prime $q=\iota\overline{\iota}$ splitting into two principal ideals
over $\mathcal{O}_{K}$, a primitive $k$-th root of unity $b$ modulo
$(\iota)^{n}$, some $k$-th power non-residue $a$ modulo
$\alpha_{n}=\gamma\iota^{n}+b$, and that $E/H$ has good reduction modulo an
ideal above $(\alpha_{n})$ in $H/K$ (it is sufficient to check
$\gcd(N_{K/\mathbb{Q}}(\alpha_{n}),N_{H/\mathbb{Q}}(\operatorname{disc}(E)))=(1)$).

##  2 Extending Lenstra’s Criterion

###  2.1 Notation and Assumptions

Throughout this paper, $p,q$ refer to rational primes. Further, $E/M$ refers
to an elliptic curve defined over some number field $M$ and $\mathcal{O}_{M}$
denotes the ring of integers of $M$. Let $h_{M}$ denote the class number. For
a Dedekind domain (e.g. the ring of integers of a number field) we adopt the
definition $\gcd(\mathfrak{j},\mathfrak{i})=\mathfrak{j}+\mathfrak{i}$ for two
ideals $\mathfrak{j},\mathfrak{i}$. We note that there is no proper ideal
containing both $\mathfrak{j},\mathfrak{i}$ precisely when
$\gcd(\mathfrak{j},\mathfrak{i})=(1)$. Further, let $N_{L/V}$ denote the field
norm for a field extension $L/V$.

The number fields of interest for most of this paper are imaginary quadratic
fields $K$ with Hilbert class field $H$. We let $E/H$ be an elliptic curve
defined over $H\supset K$ with complex multiplication by the ring of integers
$\mathcal{O}_{K}$ of $K$. _Further assume that $E$ has good reduction modulo
every relevant ideal unless otherwise stated_. That is, all prime ideals
modulo which we reduce $E$ are prime to $\operatorname{disc}(E)$. We further
let $\phi_{E,q}$ be the Frobenius endomorphism on the group
$E(\overline{\mathbb{F}}_{q})$ given by $\phi([x:y:z])=[x^{q}:y^{q}:z^{q}]$.
Further we will make the simplifying assumption that
$K\neq\mathbb{Q}[\sqrt{-1}],\mathbb{Q}[\sqrt{-3}]$ so that the unit group of
$\mathcal{O}_{K}$ is $\\{\pm 1\\}$, although it should be noted that much of
the theory can be extended without much trouble to these cases.

Let $\mathfrak{N}\subset\mathcal{O}_{H}$ be an ideal, $\pi\in\mathcal{O}_{K}$,
and $N\in\mathbb{N}$ such that

$\displaystyle N_{H/K}({\mathfrak{N}})$ $\displaystyle=\pi\mathcal{O}_{K}$
$\displaystyle N_{K/\mathbb{Q}}(\pi\mathcal{O}_{K})$ $\displaystyle=(N)$

We will reduce to the cases where the prime ideal factorization of a large
principal ideal factor of $(\pi^{k}-1)$ is known:

$\displaystyle(\pi^{k}-1)$ $\displaystyle=\Gamma\Lambda$
$\displaystyle\Lambda=(\lambda)$
$\displaystyle=\prod_{\mathfrak{q}|\Lambda}\mathfrak{q}^{e_{q}}\subset\mathcal{O}_{K}$

We also consider prime ideals of $\mathcal{O}_{H}$, $\mathfrak{p}$, with
$N_{H/K}({\mathfrak{N}})=\pi_{p}\mathcal{O}_{K}$ and
$N_{H/\mathbb{Q}}(\mathfrak{p})=p^{j}$ for a rational positive prime $p$. Also
let

$f_{k}=x^{k}-a\in(\mathcal{O}_{H}/\mathfrak{N})[x]$

with $a\in\mathcal{O}_{H}$ a primitive $k$-th power non-residue modulo
$\mathfrak{N}$. In particular, if $\mathfrak{N}$ is prime, then
$(\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k})$ is a degree $k$ finite extension
field of $\mathcal{O}_{H}/\mathfrak{N}$. In addition, reducing modulo
$\mathfrak{p}$ (for some prime $\mathfrak{p}|\mathfrak{N}$), we can consider
computations in $(\mathcal{O}_{H}/\mathfrak{p})[x]/(f_{k})$ as (potentially
not fully reduced) computations in some degree $h<k$ extension field of
$\mathcal{O}_{H}/\mathfrak{p}$. This is because $(f_{k})$ splits into the
product of irreducible polynomials $g_{i}$ modulo $\mathfrak{p}$, and thus
$(f_{k})\subset(g_{i})$ for some $g_{i}$.

Let $P=[x_{0}:y_{0}:z_{0}]\in E(\mathcal{O}_{H})$. We write
$P\mod\mathfrak{N}$ to denote the coordinate-wise reduction of $P$ modulo
$\mathfrak{N}$. Note that we have that $P\equiv
O_{E}\mod\mathfrak{N}\Leftrightarrow z_{0}\in\mathfrak{N}$. Following the
convention of [2, 1], we say $P$ is _strongly non-zero_ modulo $\mathfrak{N}$
if $\gcd(z_{0}\mathcal{O}_{H},\mathfrak{N})=(1)$. In particular this implies
$z_{0}\mathcal{O}_{H}$ and $\mathfrak{N}$ are relatively prime. In particular
this implies that for each prime $\mathfrak{p}|\mathfrak{N}$, $P\not\equiv
O_{E}\mod\mathfrak{p}$.

Now if $P=[x_{0}:y_{0}:z_{0}]=[x_{0}:y_{0}:\sum_{x=0}^{k-1}a_{i}x^{i}]\in
E(\mathcal{O}_{H}[x]/(f_{k}))$. Note we are implicitly reducing $z_{0}$ modulo
$f_{k}$ so that $z_{0}$ is given by an at most degree $k-1$ polynomial; we
will continue this practice throughout the paper. In particular this implies
that $P\equiv O_{E}\mod(\mathfrak{N},f_{k})\Leftrightarrow P\equiv
O_{E}\mod\mathfrak{N}$ since it is already reduced modulo $f_{k}$. We thus
note

$P\equiv O_{E}\mod(\mathfrak{N},f_{k})\Leftrightarrow P\equiv
O_{E}\mod\mathfrak{N}\Leftrightarrow z_{0}\in\mathfrak{N}\Leftrightarrow
a_{i}\in\mathfrak{N},0\leq i\leq k-1$

Thus we say $P$ is _strongly non-zero_ modulo $(\mathfrak{N},f_{k})$ if
$\gcd(a_{i}\mathcal{O}_{H},\mathfrak{N})=(1)$ for $0\leq i\leq k-1$. In
particular this implies that $a_{i}\not\in\mathfrak{p}$ for each prime
$\mathfrak{p}|\mathfrak{N}$ and thus that $P\not\equiv O_{E}\mod\mathfrak{p}$.

######  Remark 2.1.

If one wants to confirm $\gcd(a\mathcal{O}_{H},\mathfrak{N})=(1)$, simply show
that $\gcd(N_{H/\mathbb{Q}}(a\mathcal{O}_{H}),N)=1$. This is sufficient, and
if $N>\gcd(N_{H/\mathbb{Q}}(a\mathcal{O}_{H}),N)>1$, $N$ is composite and we
may terminate whatever primality testing algorithm we are running. If
$N=\gcd(N_{H/\mathbb{Q}}(a\mathcal{O}_{H}),N)$ and
$\gcd(a\mathcal{O}_{H},\mathfrak{N})=(1)$ then
$\sigma{\mathfrak{N}}|a\mathcal{O}_{H}$ for some $\sigma^{\prime}\in
Gal(H/K)$, $\sigma^{\prime}\neq id$. The latter condition may be checked
because
$\sigma^{\prime}{\mathfrak{N}}|a\mathcal{O}_{H}\Leftrightarrow(N)|\prod_{\sigma\in
Gal(H/K),\sigma\neq\sigma^{\prime}}\sigma(a\mathcal{O}_{H})\mathfrak{N}$. We
can try each guess for $\sigma^{\prime}\neq id$ to check this.

Note that if $E/H$, with CM by $\mathcal{O}_{K}$, has good reduction at a
prime $\mathfrak{p}$, then by Silverman’s _Advanced Topics in the Arithmetic
of Elliptic Curves_ ,

$\operatorname{End}(E)\rightarrow\operatorname{End}(\widetilde{E})$

is a homomorphism of $\mathcal{O}_{K}$-modules, where $\widetilde{E}$ denotes
the reduction [31, Chapter II,IV]. Thus it does not make a difference in
computations when we mod by $\mathfrak{p}$. If we do computations on $E/H$
modulo a possibly composite ideal $\mathfrak{N}$ with good reduction, then
since $\mathfrak{N}\subset\mathfrak{p}$, we can consider computations as
partial reductions and thus mod by $\mathfrak{N}$ universally in computation:

$[\alpha](Q\mod\mathfrak{N})\equiv[\alpha]Q\mod\mathfrak{N}$

###  2.2 Hecke Character Properties

Consider again $E/H$ with CM by $\mathcal{O}_{K}$ ($K\subset H$). Again recall
that throughout this paper $K\neq\mathbb{Q}[i],\mathbb{Q}[\sqrt{-3}]$. We
adopt and specialize the following definition-lemma from [28, Prop. 4.1].

######  Lemma 2.2.

Let $\psi:I(B)\rightarrow K^{\times}$ denote the _Hecke Character_ given as
the unique character from the group of fractional ideals with support outside
of primes $\beta\in\mathcal{O}_{H}$ where $E$ has bad reduction satisfying:

(1) $\psi(\mathfrak{p})\in\mathcal{O}_{K}$, and $\psi(\mathfrak{p})$ is a
generator of $N_{H/K}(\mathfrak{p})$ (2)
$|E(\mathcal{O}_{H}/\mathfrak{p})|=N_{H/\mathbb{Q}}(\mathfrak{p})+1-Tr_{K/\mathbb{Q}}(\psi(\mathfrak{p}))$

###### Proof.

We must check that Proposition $4.1$ specializes to this case when we take the
order in $K$, $\mathcal{O}=\operatorname{End}E$, to be $\mathcal{O}_{K}$, and
when we let $K\neq\mathbb{Q}[i],\mathbb{Q}[\sqrt{-3}]$. But this is precisely
the content of [28, Lemma 2.6, Remark 2.7, Corollary 4.2]. Notice that
conditions $(ii),(iii)$ of [28, Prop. 4.1] are trivially satisfied in this
special case because $\mathcal{O}=\mathcal{O}_{K}$. ∎

In particular, $\psi(\mathfrak{p})\in\mathcal{O}_{K}$ is the Frobenius
endomorphism of $E$ defined over ${\mathcal{O}_{H}/\mathfrak{p}}$,
$\psi(\mathfrak{p})[P]=P$ for all $P\in E(\mathcal{O}_{H}/\mathfrak{p})$ [10].
The above paper gives a method of calculating the Hecke character for certain
primes $\mathfrak{p}$ in a method that is negligible in computational
complexity compared to the runtime of the algorithm 3.3, as spelled out below
in Definition 2.3, Lemma 2.4, and [28, Prop. 6.2]. In particular, we have that

$\psi(\mathfrak{p})=u\pi_{p}$

for some unit $u\in\mathcal{O}_{K}^{\times}$. Since we have removed
$\mathbb{Q}[i],\mathbb{Q}[\sqrt{-d}]$, $u=\pm 1$. We define the analogs
$\left(\frac{a}{\mathfrak{N}}\right)$ of the Legendre symbol as in [28, Def.
2.3], except we allow $\mathfrak{N}$ to be composite in the definition. Let
$D$ be the discriminant of $K$. We make the following definition:

######  Definition 2.3.

Suppose $E:y^{2}=x^{3}+ax+b$. Let $\tau$ be as in [28, Prop. 5.3]. Recall
$\pi:=N_{H/K}(\mathfrak{N})$. Let $\epsilon_{\tau}$ be as in [28, Prop 6.2].
For an ideal $\mathfrak{N}\subset\mathcal{O}_{K}$ prime to
$\operatorname{disc}(E)$, define

$\psi(\mathfrak{N})=\begin{cases}\left(\frac{6b\gamma_{3}}{\mathfrak{N}}\right)_{2,H}\epsilon_{\tau}(\pi)\pi&\text{if
$D$ is odd}\\\
\left(\frac{-6bi\gamma_{3}}{\mathfrak{N}}\right)_{2,H}\epsilon_{\tau}(\pi)\pi&\text{if
$D\equiv 4,8\mod 16$}\\\
\left(\frac{6^{2}b^{2}(j-1728)}{\mathfrak{N}}\right)_{4,H}\epsilon_{\tau}(\pi)\pi&\text{if
$D\equiv 0,12\mod 16$}\end{cases}$

Note that by construction we have

######  Lemma 2.4.

If $\mathfrak{N}$ is prime, then $\psi(\mathfrak{N})$ from Definition 2.3 and
$\psi(\mathfrak{N})$ from Lemma 2.2 agree.

###### Proof.

This is Proposition $5.3$ of [28]. ∎

###  2.3 The $\mathcal{O}_{K}$-module generated by $P$

Let $P\in E((\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k}))$, with
$f_{k}\in\mathcal{O}_{H}[x]$ irreducible modulo each prime factor of
$\mathfrak{N}$. We now specify some of the details of the structure of the
$\mathcal{O}_{K}$-module $(P)$ generated by $P$. Let
$\operatorname{ord}_{\mathfrak{N}}(P)$ denote the unique ideal such that
$[\lambda]P\equiv O_{E}\mod\mathfrak{N}$ if and only if
$\lambda\in\operatorname{ord}_{\mathfrak{N}}(P)$. In other words,
$\operatorname{ord}_{\mathfrak{N}}(P)$ is the annihilator of $(P)$. We must
check this is well defined, and that we can say something about it
computationally.

######  Lemma 2.5.

If $\mathfrak{N}$ is prime, $\operatorname{ord}_{\mathfrak{N}}(P)$ exists.
Moreover, for some unit $u\in\mathcal{O}_{K}^{\times}$,

$\displaystyle\operatorname{ord}_{\mathfrak{N}}(P)\supset(u{N}_{H/K}(\mathfrak{N})^{k}-1)=(\psi(\mathfrak{N})^{k}-1).$

To do this we need the help of two lemmata.

######  Lemma 2.6.

For all $P\in E((\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k}))$,
$(\psi(\mathfrak{N})^{k}-1)P=O_{E}$ if $\mathfrak{N}$ is prime.

###### Proof.

By definition,
$\psi(\mathfrak{N}))[x_{0}:y_{0}:z_{0}]\equiv[x_{0}^{n}:y_{0}^{n}:z_{0}^{n}]\mod\mathfrak{N}$,
where $n=\\#\mathcal{O}_{H}/\mathfrak{N}$. We can write each projective
coordinate as some polynomial $\sum_{i=0}^{k-1}a_{i}x^{i}$ in
$(\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k})$, with
$a_{i}\in\mathcal{O}_{H}/\mathfrak{N}$. By the definition of $f_{k}$ and a
Galois extension,
$(\sum_{i=0}^{k-1}a_{i}x^{i})^{n}=\sum_{i=0}^{k-1}a_{i}\zeta_{k}^{i}x^{i}$ for
some $k$-th root of unity $\zeta_{k}\in\mathcal{O}_{H}$. Then lemma follows
when raising to the $n$-th power $k$ times, since
$[\psi(\mathfrak{N})^{k}]P\equiv P\mod\mathfrak{N}$. ∎

Now we introduce 2.7, using a similar methodology to [2] theorem 3.5 (a).

######  Lemma 2.7.

If $P\not\equiv O_{E}\mod\mathfrak{N}$ and $[\mathfrak{a}]P\equiv
O_{E}\mod\mathfrak{N}$ for some ideal $\mathfrak{a}$ (if $[\lambda]P\equiv
O_{E}\mod\mathfrak{N}$ for each $\lambda\in\mathfrak{a}$), and if there is an
element $\lambda\in\frac{\mathfrak{a}}{\mathfrak{h}}$ such that
$[\lambda]P\not\equiv O_{E}\mod\mathfrak{N}$, for each prime
$\mathfrak{h}|\mathfrak{a}$, then

$[\lambda]P\equiv O_{E}\mod\mathfrak{N}\Leftrightarrow\lambda\in\mathfrak{a}.$

###### Proof.

Assume that $[\lambda]P\equiv O_{E}\mod\mathfrak{N}$. Then further assuming
$\lambda\not\in\mathfrak{a}$, we have that $[\gcd(\mathfrak{a},\lambda
End(E))]P\equiv O_{E}\mod\mathfrak{N}$. If $\gcd(\mathfrak{a},\lambda
End(E))=(1)$ then we have a contradiction. So assume that
$\gcd(\mathfrak{a},\lambda End(E))$ is a proper ideal of $End(E)$. But then
since $\gcd(\mathfrak{a},\lambda End(E))|\mathfrak{a}$ and since
$\lambda\not\in\mathfrak{a}$ by assumption, we have that
$\gcd(\mathfrak{a},\lambda End(E))\supsetneq\mathfrak{a}$, a contradiction
because then for some prime $\mathfrak{h}|\mathfrak{a}$,
$\gcd(\mathfrak{a},\lambda End(E))\supset\frac{\mathfrak{a}}{\mathfrak{h}}$. ∎

###### Proof of Lemma 2.5.

If $\mathfrak{N}$ is prime then $[\lambda]P\equiv O_{E}\mod\mathfrak{N}$ for
every $\lambda\in(\psi(\mathfrak{N}))^{k}-1)$, by Lemma 2.6. If
$[1]P=O_{E}\mod\mathfrak{N}$, then $(1)=\operatorname{ord}_{\mathfrak{N}}(P)$,
and the condition that $[\lambda]P\not\equiv O_{E}\mod\mathfrak{N}$ for
$\lambda\not\in(1)$, as well as uniqueness, is trivial. Otherwise we have that
$[1]P\not\equiv O_{E}\mod\mathfrak{N}$. Then consider each prime
$\mathfrak{h}|(\psi(\mathfrak{N})^{k}-1)$, and the corresponding ideal
$\mathfrak{h}^{-1}(\psi(\mathfrak{N})^{k}-1)=\frac{(\psi(\mathfrak{N})^{k}-1)}{\mathfrak{h}}$.
If for each $\mathfrak{h}$ we have that $[\lambda]P\not\equiv
O_{E}\mod\mathfrak{N}$ for some
$\lambda\in\mathfrak{h}^{-1}(\psi(\mathfrak{N})^{k}-1)$, then we have
$\operatorname{ord}_{\mathfrak{N}}(P)=(\psi(\mathfrak{N})^{k}-1)$ by Lemma
2.7. Alternatively, let $i$ index through the distinct
$\mathfrak{h}_{i}|(\psi(\mathfrak{N})^{k}-1)$ such that
$[\mathfrak{h}_{i}^{-1}\psi(\mathfrak{N})^{k}-1)]P\equiv
O_{E}\mod\mathfrak{N}$. Then
$\operatorname{ord}_{\mathfrak{N}}(P)=\frac{(\psi(\mathfrak{N})^{k}-1)}{\prod_{i}\mathfrak{h}_{i}}$
by construction and Lemma 2.7. This divides $(\psi(\mathfrak{N})^{k}-1)$ and
is unique again by Lemma 2.7.

∎

Now let $\mathfrak{N}=\mathfrak{p}^{n}$ be a prime a power. By construction of
$f_{k}$, $f_{k}$ is irreducible modulo $\mathfrak{p}$. Letting
$R=(\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k})$, we see that
$R/\mathfrak{p}=(\mathcal{O}_{H}/\mathfrak{p})[x]/(f_{k})$ is a field. Thus
$\mathfrak{p}$ is a maximal ideal of $R$. From [19] we have

######  Lemma 2.8.

Let $R$ be a finite ring and $E/R$ an elliptic curve. The obvious projection
map of groups $\phi:E(R)\rightarrow E(R/\mathfrak{m})$ is a surjection with
$\\#\ker(\phi)=\\#\mathfrak{m}$.

It should be emphasized that $\phi$ is a map of _groups_. By the discussion
above we can take $R=(\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k})$. Now let $Q$
satisfy $\phi(Q)=O_{E}$. Then by the definition of a group hom, $\phi(Q\oplus
Q...\oplus Q)=O_{E}$. Since $\\#\mathfrak{p}=p^{n-1}$, and since the size of
$(Q)$ (the subgroup of $\ker(\phi)$ generated by $Q$) is the number of unique
sums, we have that Lagrange’s theorem implies $\\#(Q)|p^{n-1}$ and thus that
the number of unique sums divides $p^{n-1}$. Note that $\phi(Q)=O_{E}$ implies
by construction of $\phi$ that $Q\equiv 0\mod\mathfrak{p}$, and that the
number of unique sums is the first $s$ such that $Q\oplus..._{s}\oplus Q\equiv
O_{E}\mod\mathfrak{N}$. Further consider that for all $P$,
$(\psi(\mathfrak{p})^{k}-1)P=O_{E}$ in $R$ by Lemma 2.5. Putting this
together:

######  Lemma 2.9.

Let $\mathfrak{N}=\mathfrak{p}^{n}$ be a prime power. Then
$\operatorname{ord}_{\mathfrak{N}}(P)\supset
p^{n-1}(\psi(\mathfrak{N})^{k}-1)$ exists.

###### Proof.

Use the above discussion and the proof of Lemma 2.5, this time with
$p^{n-1}(\psi(\mathfrak{N})^{k}-1)$ in place of $(\psi(\mathfrak{N})^{k}-1)$.
∎

Now let $\mathfrak{N}$ be an arbitrary ideal. Iff $P\equiv
O_{E}\mod\mathfrak{p^{n}}$ for each prime power dividing $\mathfrak{N}$, then
$P\equiv O_{E}\mod\mathfrak{N}$. Thus

######  Lemma 2.10.

In general,

$\operatorname{ord}_{\mathfrak{N}}(P)\supset\operatorname{lcm}_{\mathfrak{p}^{n}|\mathfrak{N}}p^{n-1}(\psi(\mathfrak{N})^{k}-1)\supset\prod_{\mathfrak{p}^{n}|\mathfrak{N}}p^{n-1}(\psi(\mathfrak{N})^{k}-1)$

exists.

###### Proof.

Use the above discussion and the proof of Lemma 2.9, along with the proof of
Lemma 2.5, this time with
$\operatorname{lcm}_{\mathfrak{p}^{n}|\mathfrak{N}}p^{n-1}(\psi(\mathfrak{N})^{k}-1)$
in place of $(\psi(\mathfrak{N})^{k}-1)$. ∎

###  2.4 Main Theoretical Results

In this section assume that $E/H$ has good reduction modulo $\mathfrak{N}$. To
begin this section we should remark the following.

######  Remark 2.11.

For $\mathfrak{p}\subset\mathcal{O}_{H}$, we have that
$N_{H/\mathbb{Q}}(\mathfrak{p})=p^{j}$ is a prime power. Thus if we first
check that the integers $N$ we test are not perfect powers, we can test the
primality of $N=N_{H/\mathbb{Q}}(\mathfrak{N})$ by testing the primality of
$\mathfrak{N}$.

######  Remark 2.12.

The trial division steps in this section will be proven in the proceeding one.
Additionally, an algorithm to complete the trial division will be given.

We now state our analogue of Lenstra’s theorem for CM elliptic curves. Since
we cannot directly check that $f_{k}$ is irreducible modulo all prime factors
$\mathfrak{p}$ of $\mathfrak{N}$, we note that we can relax the assumption
that $f_{k}$ is irreducible modulo each prime factor:

######  Lemma 2.13.

Let $f_{k}=x^{k}-a$ for an arbitrary element $a\in\mathcal{O}_{H}$ with
$a\not\in\mathfrak{p}$. Let $P=[x_{0}:y_{0}:z_{0}]\in
E((\mathcal{O}_{H}/\mathfrak{p})[x]/(f_{k}))$. Then
$[\psi(\mathfrak{p})]P\equiv[\sigma_{g}x_{0}:\sigma_{g}y_{0}:\sigma_{g}z_{0}]\mod\mathfrak{p}$
for $\sigma_{g}(\sum a_{i}x^{i})=\sum a_{i}\zeta^{i}_{g}x^{i}$ for $\zeta_{g}$
some $k$-th root of unity modulo $(\mathfrak{p},f_{k})$. In particular,
$\operatorname{ord}_{\mathfrak{p}}([P])|\psi(\mathfrak{p})^{k}-1$.

###### Proof.

By standard theory, the Hecke character $\psi(\mathfrak{p})$ is a well-defined
endomorphism of $E((\mathcal{O}_{H}/\mathfrak{p})[x]/(g))$ for an irreducible
factor $g$ of $f_{k}$ modulo $\mathfrak{p}$. Consider $P$ as a representative
of the equivalence class $[P]=(P\mod(g))$ in
$E((\mathcal{O}_{H}/\mathfrak{p})[x]/(g))$. Then we may compute a
representative of $[\psi(\mathfrak{p})][P]$ as $[\psi(\mathfrak{p})]P$. Let
$P=[x_{0}:y_{0}:z_{0}]$, then for $p^{j}=\\#\mathcal{O}_{H}/\mathfrak{p}$,
$[\psi(\mathfrak{p})]P=[x_{0}^{p^{j}}:y_{0}^{p^{j}}:z_{0}^{p^{j}}]=[\sigma_{g}x_{0}:\sigma_{g}y_{0}:\sigma_{g}z_{0}]\mod\mathfrak{p}$,
since each coordinate may be expressed as $\sum a_{i}x^{i}$ in
$(\mathcal{O}_{H}/\mathfrak{p})[x]/(f_{k})$ (use the binomial theorem modulo a
prime and choice of $f_{k}$). Since $[\psi(\mathfrak{p})^{k}-1]P\equiv
O_{E}\mod\mathfrak{p}$, the latter conclusion follows by the proof of Lemma
2.5. ∎

For the following theorem, let $\rho_{j}$ be a map given by $\rho_{j}(\sum
a_{i}x^{i})=\sum a_{i}\zeta_{j}^{i}x^{i}$ for a $\zeta_{j}$ a _primitive_
$k$-th root of unity modulo $(\mathfrak{N},f_{k})$. Further (after reducing
$\zeta_{j}^{m}-1$ modulo $f_{k}$) let $\gcd(\mathfrak{N},\zeta_{j}^{m}-1)=(1)$
for $1\leq j<k$. This ensures that $\zeta_{j}$ is a primitive $k$-th root of
unity modulo $(\mathfrak{p},f_{k})$.

######  Theorem 2.14.

Let notation be as above and fix some $\mathfrak{N}\nmid(2)$. Assume that
$N>1\neq n^{r}$ for some integer $n$ and $r>1$. Let
$(\psi(\mathfrak{N})^{k}-1)=\Gamma\Lambda$, with $\Lambda=(\lambda)$
principal, the primary factorization $\prod\mathfrak{q}^{e_{q}}$ of $\Lambda$
known, and ${N_{K/\mathbb{Q}}(\Lambda)}>N^{1/2}$. If one can choose an
$f_{k}=x^{k}-a$ with $a$ a primitive $k$-th non-residue modulo $\mathfrak{N}$,
and if for each $\mathfrak{q}$, $\exists
P_{q}=[x_{q}:y_{q}:z_{q}]\in{E}((\mathcal{O}_{F}/\mathfrak{N})[x]/(f_{k}))$
such that

$\displaystyle\text{(1) }[\lambda]P_{q}=O_{E},$ $\displaystyle\text{(2)
}[\lambda_{\mathfrak{q}}]P_{q}\text{ is strongly nonzero modulo
$(\mathfrak{N},f_{k})$},\text{ where $\lambda_{\mathfrak{q}}$}$
$\displaystyle\text{is some element of ${\Lambda}/{\mathfrak{q}}$},$
$\displaystyle\text{(3)
}[\psi(\mathfrak{N})^{m}]P_{q}=[\rho_{j}^{m}x_{q}:\rho_{j}^{m}y_{q}:\rho_{j}^{m}z_{q}],\text{
for some $j$ and $1\leq m\leq k$,}$

then $\psi(\mathfrak{p})=\psi(\mathfrak{N})^{m}$ in
$\mathcal{O}_{K}/(\Lambda)$ for $m=1,...,k$. If further none of the
$O(4(-d)+4d^{2})$ residues $\beta$ of $\psi(\mathfrak{N})^{m}$, $m=1,...,k$
with $N_{K/\mathbb{Q}}(\beta)\leq N_{K/\mathbb{Q}}(\Lambda)$ have that
$N_{K/\mathbb{Q}}(\beta)$ properly divides $N$, then $N$ is prime.

###### Proof.

Assume that conditions $(1)$ and $(2)$ hold for some prime divisor
$\mathfrak{q}|\Lambda$. Reducing modulo each $\mathfrak{p}$, we can consider
our calculations done over the field $(\mathcal{O}_{H}/\mathfrak{N})[x]/(g)$
for some $g|f_{k}$ irreducible modulo $\mathfrak{p}$. Condition $(1)$ yields
that
$\operatorname{ord}_{\mathfrak{p}}(P_{q})\supset\mathfrak{q}^{v_{\mathfrak{q}}(\Lambda)}$
by definition of order, for each prime ideal $\mathfrak{p}|\mathfrak{N}$.
Condition $(2)$ yields that there is an element $\lambda_{\mathfrak{q}}$ of
$\Lambda/\mathfrak{q}$, and thus of
$\mathfrak{q}^{v_{\mathfrak{q}}(\Lambda)-1}$ such that
$[\lambda]P_{q}\not\equiv O_{E}\mod\mathfrak{p}$. Thus
$\operatorname{ord}_{\mathfrak{p}}(P_{q})\not\supset\mathfrak{q}^{v_{\mathfrak{q}}(\Lambda)-1}$
by definition of order. So we have that
$\operatorname{ord}_{\mathfrak{p}}(P_{q})\subset\mathfrak{q}^{v_{\mathfrak{q}}(\Lambda)}$
by primality. Note this holds for each $\mathfrak{q}|\Lambda$.

By condition $(3)$,
$[\psi(\mathfrak{N})^{m}]P_{q}=[\rho_{j}^{m}x_{q}:\rho_{j}^{m}y_{q}:\rho_{j}^{m}z_{q}]$,
$1\leq m<k$. Writing $z_{q}=\sum a_{i}x^{i}$, by construction of $\rho_{j}$,

$\rho_{j}^{m}z_{q}\equiv\sum a_{i}\zeta^{im}_{j}x^{i}\not\equiv
z_{q}\mod\mathfrak{p},1\leq m<k$

since $\zeta_{j}$ is a primitive $k$-th root of unity modulo $\mathfrak{p}$.
Further $\rho_{j}^{k}z_{q}\equiv z_{q}\mod\mathfrak{p}$ (and similarly for
$x_{q},y_{q}$). By Lemma 2.13,
$[\psi(\mathfrak{p})]P_{q}\equiv[\sigma_{g}x_{q}:\sigma_{g}y_{q}:\sigma_{g}z_{q}]\mod\mathfrak{N}$.
In particular $\sigma_{g}z_{g}=\sum a_{i}\zeta_{g}^{i}x^{i}$ for some $k$-th
root of unity modulo $(\mathfrak{p},f_{k})$ and so

$\displaystyle[\psi(\mathfrak{N})^{m}]P_{q}$
$\displaystyle\equiv[\rho_{j}^{m}x_{q}:\rho_{j}^{m}y_{q}:\rho_{j}^{m}z_{q}]$
$\displaystyle\equiv[\rho_{j}^{m}x_{q}:\rho_{j}^{m}y_{q}:\sum
a_{i}\zeta^{im}_{j}x^{i}]$
$\displaystyle\equiv[\sigma_{g}x_{q}:\sigma_{g}y_{q}:\sigma_{g}z_{q}]\equiv[\psi(\mathfrak{p})]P_{q}\mod\mathfrak{p}$

for $1\leq m<k$ with $\zeta_{j}^{m}\equiv\zeta_{g}\mod\mathfrak{p}$ (such an
$m$ exists by primitivity). In particular we know that
$[\psi(\mathfrak{N})^{m}-\psi(\mathfrak{p})]P_{q}\equiv
O_{E}\mod\mathfrak{p}$. By the results of the first paragraph and Lemma 2.5,
$\psi(\mathfrak{N})^{m}-\psi(\mathfrak{p})\in\mathfrak{q}^{e_{q}}$. Since this
is true for each prime $\mathfrak{q}|\Lambda$,
$\psi(\mathfrak{N})^{m}-\psi(\mathfrak{p})\equiv 0\mod\Lambda$.

Assume now that none of the residues $\beta$ of $\psi(\mathfrak{N})^{m}$,
$m=1,...,k$ modulo $\Lambda$ with $N_{K/\mathbb{Q}}(\beta)\leq N^{1/2}$ have
$N_{K/\mathbb{Q}}(\beta)|N$. Then for every distinct prime divisor
$\mathfrak{p}|\mathfrak{N}$, $N_{K/\mathbb{Q}}(\psi(\mathfrak{N}))>N^{1/2}$
and $N_{K/\mathbb{Q}}(\psi(\mathfrak{N}))|N$. Clearly there can thus be only
one distinct prime divisor $\mathfrak{p}$ of $\mathfrak{N}$. If
$\mathfrak{p}^{r}=\mathfrak{N}$ for $r>1$, then by norm multiplicativity,
$N=p^{r}$, which is a contradiction since we assumed $N$ was not a prime
power. Thus $\mathfrak{N}$ is prime. Since we assumed $N$ is not a prime
power, $N$ is also prime by Remark 2.11.

By Theorem 2.20, there are $O(4(-d)+4d^{2})$ residues to check for each given
$m$.

∎

In practice, an issue that arises with condition $(3)$ of the initial test is
that one must compute the action of the (non-integer) complex multiplication
isogenies in precomputation. There is no repository of such isogenies known to
the author online. Additionally, the test, although a sufficient condition for
primality, is not a necessary one, and one that runs in
$\widetilde{O}(\log^{3}N)$ for fixed $k$, see the analysis of Lemma 3.6,
Remark 3.5 (an asymptotically similar runtime to Lenstra’s criterion). We will
now introduce the framework for a Las Vegas test for primality that runs in
average time $\widetilde{O}(\log^{2}N)$ on certain classes of integers, serves
as an _efficient primality test_ , and certifies primality in one run for
nearly all choices of input points.

We begin with some lemmata. We say a solution to $x^{k}=1$ is _$k$ -primitive_
if $x^{m}\neq 1$ for $0<m<k$. We have the following well-known lemma.

######  Lemma 2.15.

Let $\mathfrak{p}$ be a prime ideal which is not inert and $\mathfrak{p}\nmid
2$. Then $\mathcal{O}_{K}/\mathfrak{p}^{n}$ is generated by one element when
considered as a multiplicative group. In particular, if $x^{k}=1$ in
$\mathcal{O}_{K}/\mathfrak{p}^{n}$ has a $k$-primitive solution, then it has
precisely $k$ solutions.

######  Lemma 2.16.

Let $N=\psi\overline{\psi}$ split in $\mathcal{O}_{K}$. Let $n$ be a positive
integer such that $(n)|\psi-1$, then $N\equiv 1\mod n$.

###### Proof.

If $(n)|\psi-1$, then
$(n=\overline{n})|(\overline{\psi-1}=\overline{\psi}-1)$. But then
$N=\psi\overline{\psi}\equiv 1\cdot 1=1\mod n$, as desired. ∎

Thus we do not lose much by taking $\mathfrak{q}$ to be non-inert. If it were
inert in the following theorem, the classical finite fields test could be
used. Further, it does not hurt to assume
$(q^{e_{q}})\nmid(\psi(\mathfrak{N})^{2k}-1)$, as otherwise
$q^{e_{q}}|N^{2k}-1$ by Lemma 2.16 and the classical Lenstra primality test
may be used.

######  Theorem 2.17.

Let notation be as above and fix some $\mathfrak{N}\nmid(2)$. Assume $N>1$.
Let $(\psi(\mathfrak{N})^{k}-1)=\Gamma\mathfrak{q}^{e_{q}}$ with
$\mathfrak{q}\nmid(2)$ a non-inert principal prime and
$q^{e_{q}}:=N_{K/\mathbb{Q}}(\mathfrak{q}^{e_{q}})>N^{1/2}$. Further assume
$((\psi(\mathfrak{N}))^{m}-1)\not\in\mathfrak{q}^{e_{q}}$ for $0<m<k$, and
that $(q^{e_{q}})\nmid((\psi(\mathfrak{N}))^{2k}-1)$. If there is an
$f_{k}=x^{k}-a$ with $a$ a primitive $k$-th non-residue modulo $\mathfrak{N}$,
and if $\exists P\in E((\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k}))$ such that

$\displaystyle\text{(1) }[q^{e_{q}}]P$ $\displaystyle=O_{E},$
$\displaystyle\text{(2) }[q^{e_{q}-1}]P$ $\displaystyle\text{ is strongly
nonzero modulo $\mathfrak{N}$},$

then $\psi(\mathfrak{p})=\psi(\mathfrak{N})^{m}$ in
$\mathcal{O}_{K}/\mathfrak{q}^{e_{q}}$ for some prime
$\mathfrak{p}|\mathfrak{N}$ up to units. If further none of the
$O(4(-d)+4d^{2})$ residues $\beta$ of $\psi(\mathfrak{N})^{m}$, $m=1,...,k$
with $N_{K/\mathbb{Q}}(\beta)\leq N_{K/\mathbb{Q}}(\Lambda)$ have that
$N_{K/\mathbb{Q}}(\beta)$ properly divides $N$, then $N$ is prime.

###### Proof.

Condition $(1)$ gives
$\operatorname{ord}_{\mathfrak{p}}(P)\supset({q}^{e_{q}})$ by definition, for
every prime $\mathfrak{p}|\mathfrak{N}$. Condition $(2)$ yields that there is
an element $\lambda$ of $({q}^{e_{q}-1})$ such that $[\lambda]P\not\equiv
O_{E}\mod\mathfrak{p}$ for each prime $\mathfrak{p}|\mathfrak{N}$. This
implies that $\operatorname{ord}_{\mathfrak{p}}(P)\not\supset({q}^{e_{q}-1})$
and thus that $\mathfrak{q}^{e_{q}}|\operatorname{ord}_{\mathfrak{p}}(P)$ or
$\overline{\mathfrak{q}}^{e_{q}}|\operatorname{ord}_{\mathfrak{p}}(P)$ for
each $\mathfrak{p}$. Assume for contradiction that
$\overline{\mathfrak{q}}^{e_{q}}|\operatorname{ord}_{\mathfrak{p}}(P)|(\psi(\mathfrak{p})^{k}-1)$
for each $\mathfrak{p}$ (Lemma 2.5). By Theorem 5.3 of [28],
$\pi_{\mathfrak{p}}^{k}=u_{p}\psi(\mathfrak{p})^{k}$ for some unit
$u_{p}\in\mathcal{O}_{K}^{\times}$. This implies that
$\overline{\mathfrak{q}}^{e_{q}}|(u_{p}\pi_{\mathfrak{p}}^{k}-1)$ and thus
that
$\overline{\mathfrak{q}}^{e_{q}}|(u_{p}^{v_{p}}\pi_{\mathfrak{p}}^{v_{p}k}-1)$
where $v_{p}$ is the highest power of $\mathfrak{p}$ dividing $\mathfrak{N}$
by norm multiplicativity. Again by multiplicativity, we see that

$\displaystyle\overline{\mathfrak{q}}^{e_{q}}|(u_{p}^{v_{p}}\pi_{\mathfrak{p}}^{v_{p}k}-1)$
$\displaystyle\Rightarrow\overline{\mathfrak{q}}^{e_{q}}|(u\pi^{k}-1)$

for some unit $u$. By construction, $\psi(\mathfrak{N})=u^{\prime}\pi$ for
some unit $u^{\prime}$, and thus

$\displaystyle\psi(\mathfrak{p})^{k}-1$ $\displaystyle=u^{\prime k}\pi^{k}-1$

Note $u^{\prime}=\pm 1$. If $u^{\prime}=1$, then since
$\overline{\mathfrak{q}}^{e_{q}}|\psi(\mathfrak{N})^{k}-1$, we have
$q^{e_{q}}|\psi(\mathfrak{N})^{k}-1$, a contradiction by assumption. But if
$u^{\prime\prime}=-1$ then
$\overline{\mathfrak{q}}^{e_{q}}|\psi(\mathfrak{N})^{k}+1$. This implies that
$q^{e_{q}}|(\psi(\mathfrak{N})^{k}+1)(\psi(\mathfrak{N})^{k}-1)=\psi(\mathfrak{N})^{2k}-1$
by construction, a contradiction to the assumptions in the theorem. Thus there
is some $\mathfrak{p}|\mathfrak{N}$ such that
$\mathfrak{q}^{e_{q}}|\operatorname{ord}_{\mathfrak{p}}(P)$. Fix this
$\mathfrak{p}$.

We have by definition of $f_{k}$ and Lemma 2.13 that
$[\psi(\mathfrak{p})^{k}]P=P\mod\mathfrak{p}$ and thus that
$\psi(\mathfrak{p})^{k}=1$ in $\mathcal{O}_{K}/\mathfrak{q}^{e_{q}}$ by
definition of order as the annihilator (Lemma 2.5). Since we have by choice
that $\psi(\mathfrak{N})^{k}=1$ and $\psi(\mathfrak{N})^{m}\neq 1$ in
$\mathcal{O}_{K}/\mathfrak{q}^{e_{q}}$ for $0<m<k$, and since by Lemma 2.15
there are precisely $k$ elements $e$ in $\mathcal{O}_{K}/\mathfrak{q}^{e_{q}}$
with $e^{k}=1$, we have that said $k$ elements are precisely
$\psi(\mathfrak{N})^{m}$, $0\leq m<k$. In particular,
$\psi(\mathfrak{p})=\psi(\mathfrak{N})^{m}$ in
$\mathcal{O}_{K}/\mathfrak{q}^{e_{q}}$ for some $0\leq m<k$.

The result then follows exactly as in Theorem 2.14.

∎

To specify a quasi-quadratic Las Vegas algorithm from this theorem, we do the
following discussion. Assume $\mathfrak{q}^{x}|\psi(\mathfrak{p})^{k}-1$. By
[35], we have that, as groups,

$E((O_{H}/\mathfrak{p})[x]/(f_{k}))\simeq_{\phi}\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}$

where $n|m$ and the groups are additive. Denote
$\\#E_{p,k}=\\#E((O_{H}/\mathfrak{p}))[x]/(f_{k})$. Assume $q^{x}|\\#E_{p,k}$.
By primality we have that $q^{x}|nm$ implies $q^{x-y}|n$, $q^{y}|m$. Since
$n|m$, we must have that $y\geq x-y$, so we can take $y\geq x/2$. Thus we have

$\left[\dfrac{\\#E_{p,k}}{q^{x}}\right]P=O_{E}\Leftrightarrow(P\mapsto_{\phi}(a,b):\text{
$n|a\cdot\frac{\\#E_{p,k}}{q^{x}}$ and $m|b\cdot\frac{\\#E_{p,k}}{q^{x}}$})$

Note that since $n,m|\\#E_{p,k}$ ($nm=\\#E_{p,k}$),

$(P\mapsto_{\phi}(a,b):\text{ $n|a\cdot\frac{\\#E_{p,k}}{q^{x}}$ and
$m|b\cdot\frac{\\#E_{p,k}}{q^{x}}$})\Leftrightarrow(P\mapsto_{\phi}(a,b):\text{
$q^{x-y}|a$ and $q^{y}|b$})$

Wlog, $0\leq a\leq n,0\leq b\leq m$. There are $\lfloor{m/q^{y}}\rfloor+1$
such $b$ that are multiples of $q^{y}$. This implies that randomly choosing
$(a,b)\in\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}$, the probability
that $q^{y}|b$, $q^{x-y}|a$ (which is less than or equal to the probability
that $q^{y}|b$) is at most

$\displaystyle\dfrac{n(\lfloor{m/q^{y}}\rfloor+1)}{nm}$
$\displaystyle\leq\dfrac{n{m/q^{y}}+n}{nm}$
$\displaystyle=\dfrac{1}{q^{y}}+\dfrac{1}{m}$
$\displaystyle\leq\dfrac{2}{q^{x/2}}.$

We can now show the following theorem.

######  Theorem 2.18.

Let $\mathfrak{N}$ be prime and satisfy the assumptions of Theorem 2.17 and
let $f_{k}$, $E/H$ also be as in Theorem 2.17, and further suppose
$(\psi(\mathfrak{N})^{k}-1)=\Gamma\mathfrak{q}^{e^{\prime}}$ with
$\mathfrak{q}$ principal and $q^{e^{\prime}}>N^{1/2+\alpha}$. Then for a
randomly chosen $Q$, conditions $(1),(2)$ are satisfied for

$P=\left[\dfrac{\\#E_{p,k}}{q^{e^{\prime}}}\right]Q=\left[\dfrac{(\psi(\mathfrak{N})^{k}-1)(\overline{\psi(\mathfrak{N})}^{k}-1)}{q^{e^{\prime}}}\right]Q$

with probability at least $1-\frac{1}{N^{\alpha/2}}$ for some $e_{q}$ such
that $N^{1/2}<q^{e_{q}}\leq q^{e^{\prime}}$.

###### Proof.

By the above discussion, if $\mathfrak{N}$ is prime then

$\displaystyle\left[q^{x}\right]P$ $\displaystyle\equiv O_{E}\mod\mathfrak{N}$
$\displaystyle\Leftrightarrow\left[\dfrac{\\#E_{p,k}}{q^{e^{\prime}-x}}\right]Q$
$\displaystyle\equiv O_{E}\mod\mathfrak{N}$

occurs with probability at most $1/q^{e^{\prime}-x}$. If we let
$x=\lfloor{N^{1/2}/q}\rfloor$, then $q^{x}$ is the largest power of $q$ less
than or equal to $N^{1/2}$ and $q^{e^{\prime}-x}>N^{\alpha}$. Thus
$[q^{x}]P\equiv O_{E}\mod\mathfrak{N}$ with probability at most
$1/N^{\alpha/2}$ by the above discussion. If it is not the identity, then by
the Lemma 2.5 and that
$(q^{e^{\prime}})\subset\operatorname{ord}_{\mathfrak{N}}(P)$ and
$(q^{x})\not\subset\operatorname{ord}_{\mathfrak{N}}(P)$,
$q^{e_{q}}=\operatorname{ord}_{\mathfrak{N}}(P)$ with $q^{e_{q}}>N^{1/2}$ by
definiton of $x$, satsifying condition $(1)$ for $e_{q}$. Condition $(2)$ is
satisfied for $e_{q}-1$ since by choice of $e_{q}$, $[q^{e_{q}-1}]P\not\equiv
O_{E}\mod\mathfrak{N}$, and since $\mathfrak{N}$ is prime, this yields
strongly-nonzero modulo $\mathfrak{N}$. ∎

If the test fails to certify primality or prove compositness in one run
through with a non-negligible $\alpha$, then the number is very likely
composite, so utilize the Miller-Rabin compositness test, which has an average
runtime of $\widetilde{O}(\log^{2}N)$ [6, 22, 27]. As will be shown in the
Implementation section, this provides a quasi-quadratic Las Vegas algorithm
for primality of a new class of integers with an average runtime of
$\widetilde{O}(\log^{2}N)$, and furthermore that certifies primes in
$\widetilde{O}(\log^{2}N)$ with probability $1-1/N^{\alpha/2}$, which is
nearly $1$ for large $N$, non-negligible $\alpha$. We first introduce
machinery for the trial division step in the next section.

###  2.5 Residue Classes in Non-Euclidean Quadratic Rings

Let $K=\mathbb{Q}[\sqrt{d}]$ be a quadratic number field, with $d$ squarefree,
equipped with the standard norm $|\bullet|$. Let
$\mathfrak{I}\subset\mathcal{O}_{K}$ be an ideal. For
$\alpha\in\mathcal{O}_{K}$, let $\overline{\alpha}$ denote the image of
$\alpha$ under the quotient map
$\phi_{\mathfrak{I}}:\mathcal{O}_{K}\rightarrow\mathcal{O}_{K}/\mathfrak{I}$.
In this section we seek for $\overline{\beta}\in\mathcal{O}_{K}/\mathfrak{I}$
to find all lifts $\phi_{\mathfrak{I}}^{-1}(\overline{\beta})$ with norms
below a certain bound.

For the purposes of this paper, we will assume that $\mathfrak{I}=(\iota)$ is
principal. We will also restrict to the case of $d<0$ as we will be working
with imaginary quadratic number fields. It is well known that for $d<0$, there
are only finitely many norm-Euclidean $\mathcal{O}_{K}$:

######  Theorem 2.19.

The norm-Euclidean quadratic number fields with $d<0$ are precisely given by

$\displaystyle d$ $\displaystyle=-1,-2,-3,-7,-11.$

For these quadratic number fields alone we can in general guarantee and
determine a lift $\phi_{\mathfrak{I}}^{-1}(\overline{\beta})$ such that
$|\phi_{\mathfrak{I}}^{-1}(\overline{\beta})|<|\iota|$. For other $d$, such a
lift may not exist. We consider in this section the following theorem.

######  Theorem 2.20.

Let $K=\mathbb{Q}[\sqrt{d}]$ for $d<0$ squarefree. Again let
$\overline{\beta}\in\mathcal{O}_{K}/\mathfrak{I}$ with $\mathfrak{I}=(\iota)$
principal. Then there exist $O(4(-d)+4d^{2})$ lifts
$\phi_{\mathfrak{I}}^{-1}(\overline{\beta})$ such that
$|\phi_{\mathfrak{I}}^{-1}(\overline{\beta})|\leq|\iota|$. Furthermore they
may be found or ruled out in deterministic $O(4(-d)+4d^{2})$ steps.

Note that the lifts $\phi_{\mathfrak{I}}^{-1}(\overline{\beta})$ are given
precisely by $\iota X+\beta$ for $X\in\mathcal{O}_{K}$ and a choice of lift,
$\beta$, since $\mathfrak{I}=(\iota)$. In general, we have the following
lemma.

######  Lemma 2.21.

Let $\iota,\beta,X\in\mathcal{O}_{K}$ be any elements. Assume $|X|\geq
4(-d)+4d^{2}$ and $(-d+d^{2})|\iota|\geq|\beta|$. Then $|\iota
X+\beta|\geq|\iota|$.

###### Proof.

If for a positive constant $k$, $|X|\geq k(-d)+kd^{2}$, then by
multiplicativity of field norms, $|\iota X|\geq(k(-d)+kd^{2})|\iota|$. Then we
can write $\iota X=a+b\sqrt{d}$ with $a^{2}+b^{2}(-d)=|\iota X|\Rightarrow
a^{2}\geq|\iota X|/2$ or $b^{2}(-d)\geq|\iota X|/2$. Writing
$\beta=c+e\sqrt{d}$, we have an analogous inequality. Thus we have that

$\displaystyle|\iota X+\beta|$
$\displaystyle\geq\max((|a|-|c|)^{2},(|b|-|e|)^{2}d)\text{, since
$|x+y\sqrt{d}|\geq x^{2},y^{2}d$ for $d<0$,}$ $\displaystyle\geq(\sqrt{|\iota
X|/2}-\sqrt{(-d+d^{2})|\iota|/2})^{2}\text{, since
$|\beta|\leq(-d+d^{2})|\iota|$,}$
$\displaystyle\geq(\sqrt{|\iota|(-kd+kd^{2})/2}-\sqrt{(-d+d^{2})|\iota|/2})^{2}\text{,
by assumption,}$ $\displaystyle=1/2(-1+d)d(-1+\sqrt{k})^{2}|\iota|.$

We want $1/2(-1+d)d(-1+\sqrt{k})^{2}\geq 1$, and for all $d$ it suffices to
choose $k=4$.

∎

To prove theorem 2.20, the general idea is, given a representative
$\overline{\beta}$ of an equivalence class, find a new representative of the
same equivalence class, $\beta$, with $(-d+d^{2})|\iota|\geq|\beta|$, and then
to apply theorem 2.20. Let $\iota=a+b\sqrt{d}$. One may naively attempt to
consider the image of $\overline{\beta}$ under the surjection with kernel
$|\iota|\in\mathfrak{I}$, but this in worst case has
$|\beta|=(|\iota|-1+\sqrt{d}(|\iota|-1))^{2}\sim|\iota|^{2}$. Attempting to
modify Lemma 2.21 to allow this larger bound yields that we must take that
$|X|$ grows with $|\iota|$, which prohibits iterating through the lifts $\iota
X+\beta$ for large $|iota|$.

Consider instead a coordinate plane with horizontal axis the real line and
vertical axis given by real multiples of $\sqrt{d}$. Thus a point $(x,y)$
represents $x+y\sqrt{d}$. Form a new grid with sides
$1(\iota)=a+b\sqrt{d},-1(\iota)=-a-b\sqrt{d},\sqrt{d}\iota=bd+a\sqrt{d},$
$-\sqrt{d}\iota=-bd-a\sqrt{d}$ by applying the change of coordinates matrix

$\displaystyle\begin{bmatrix}a&-bd\\\ b&-a\end{bmatrix}$

to the plane. Each grid square now represents all distinct classes of elements
of $\mathcal{O}_{K}$ modulo $(\iota)$. In particular, in this new coordinate
system, moving one step in any direction corresponds to adding a multiple of
$\iota$ and thus adding $0\mod(\iota)$.

To transform $\overline{\beta}=c+e\sqrt{d}$ into these coordinates, solve

$\displaystyle\begin{bmatrix}c\\\ e\end{bmatrix}$
$\displaystyle=\begin{bmatrix}a\\\ b\end{bmatrix}A+\begin{bmatrix}b(-d)\\\
-a\end{bmatrix}B$

for $(A,B)$. Then consider
$(A^{\prime},B^{\prime})=(A-\lfloor{A}\rfloor,B-\lfloor{B}\rfloor)$. Then take

$\beta=A^{\prime}\begin{bmatrix}a\\\
b\end{bmatrix}+B^{\prime}\begin{bmatrix}b(-d)\\\ -a\end{bmatrix}$

as a representative of the same equivalence class as $\overline{\beta}$ (since
we have subtracted elements of $\iota$), that lies within the four grid boxes
nearest the origin (those with coordinates $(\pm 1,\pm 1)$). Importantly, both
the real and imaginary parts of $\beta$ are bounded above in magnitude by the
magnitude of the real and imaginary parts of the four coordinate boxes (given
in the new coordinates by $(\pm 1,\pm 1)$) nearest the origin, so:

$\displaystyle|\beta|\leq|\max(|bd|,|a|)+\sqrt{d}\max(|a|,|b|)|$
$\displaystyle\leq\max(a^{2}(1-d),b^{2}d^{2}(1-d))$ $\displaystyle\leq
d^{2}b^{2}(1-d)-da^{2}(1-d)$ $\displaystyle=|\iota||-d+d^{2}|$

In particular this element $\beta$ satisfies the norm size constraint of Lemma
2.21. This suffices to prove 2.20 as seen in the next section.

##  3 Implementation and Runtime

We now provide the aforementioned Las Vegas algorithm.

From the discussion in the previous section, we get the following algorithm
which proves Theorem 2.20:

######  Algorithm 3.1.

$\displaystyle\text{1.
}K=\mathbb{Q}[\sqrt{d}],\overline{\beta}\in\mathcal{O}_{K}/(\iota),\iota=a+b\sqrt{d},\overline{\beta}=c+e\sqrt{d}$
2\. Compute $(A,B)=$ the solution of $\begin{bmatrix}c\\\
e\end{bmatrix}=\begin{bmatrix}a\\\ b\end{bmatrix}A+\begin{bmatrix}b(-d)\\\
-a\end{bmatrix}B$ 3\. Compute
$(A^{\prime},B^{\prime})=(A-\lfloor{A}\rfloor,B-\lfloor{B}\rfloor)$ to
sufficient precision $\displaystyle\text{4. Compute
}\beta=A^{\prime}\begin{bmatrix}a\\\
b\end{bmatrix}+B^{\prime}\begin{bmatrix}b(-d)\\\ -a\end{bmatrix}$ 5\.
Initialize return values $\\{\\}$ $\displaystyle\text{6. For all integers
}0\leq N,M<\sqrt{4(-d)+4d^{2}},$ if $|(N+\sqrt{d}M)\iota+\beta|\leq|\iota|$,
append $\\{(N,M)\\}$ to the result values 7\. Return the result values

######  Proposition 3.2.

Algorithm 3.1 runs in $O(4(-d)+4d^{2})$ steps.

###### Proof.

Inspection. ∎

We now seek to implement the Las Vegas test based on Theorem 2.17 and the
subsequent discussion. We will utilize notation as in Theorem 2.17. Recall
that we are assuming an elliptic curve $E/H$ with CM by $\mathcal{O}_{K}$ and
good reduction modulo $\mathfrak{N}$ in precomputation. Before beginning the
following algorithm, compute $\psi(\mathfrak{N})^{k}$ utilizing Definition 2.3
of the section Hecke Character Properties. The heuristic runtime of this step
is dominated by that of the following algorithm, and it may be done in
precomputation for a sequence of integers using reciprocity laws as in [2,
Section 6] if one wishes to make the step deterministic.

######  Algorithm 3.3.

Let notation be as above and fix some $\mathfrak{N}\nmid(2)$. Assume $N>1$.
Let $(\psi(\mathfrak{N})^{k}-1)=\Gamma\mathfrak{q}^{e^{\prime}}$ with
$\mathfrak{q}\nmid(2)$ a non-inert principal prime and
$q^{e^{\prime}}:=N_{K/\mathbb{Q}}(\mathfrak{q}^{e^{\prime}})>N^{1/2+\alpha}$.
Further assume $(\psi(\mathfrak{N})^{m}-1)\not\in\mathfrak{q}^{y}$ for $0<m<k$
and $\mathfrak{q}^{y}>N^{1/2}$, and that
$(q^{y})\nmid((\psi(\mathfrak{N}))^{k}-1)$. Choose an $f_{k}$ as in Theorem
2.17.

1\. Choose some $Q\in E((\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k}))$ 2\.
Compute
$P=\left[\frac{(\psi(\mathfrak{N})^{k}-1)(\overline{\psi(\mathfrak{N})}^{k}-1)}{{q}^{e_{q}}}\right]Q\mod\mathfrak{N}$
3\. Compute and store $[q^{x}]P\mod\mathfrak{N}$ until
$[q^{x+2}]P\mod\mathfrak{N}$ is computed, for $x=0,1,...,e^{\prime}$ until
$[q^{x}]P\equiv O_{E}\mod\mathfrak{N}$. If this does not hold for any such
$x$, then return composite 4\. Check that $[q^{x-1}]P$ is strongly nonzero
modulo $\mathfrak{N}$ If this does not hold, then return composite 5\. Check
if ${q}^{x}>N^{1/2}$. If so, return possibly prime If not, return probably
composite

######  Remark 3.4.

We can efficiently compute modulo $\mathfrak{N}$ by simply partially reducing
modulo $N=N_{H/\mathbb{Q}}(\mathfrak{N})$. Then when checking whether some
point $P=[x_{0}:y_{0}:z_{0}]\equiv O_{E}\mod\mathfrak{N}$, one can for example
check that $a_{i}\in\mathfrak{N}$ in $\mathcal{O}_{H}$ for each $a_{i}$ in
$z_{0}=\sum_{i=0}^{k-1}a_{i}x^{i}$.

######  Remark 3.5.

A similar algorithm can be developed for the more general case of Theorem
2.14, but complex isogenies must be precomputed for condition $(3)$ of Theorem
2.14, and one must test multiple strongly nonzero conditions, one for each
$\mathfrak{q}$. This increasing the complexity of the algorithm to cubic in
$\log N$ in the worst case, although for a small number of prime factors
$\mathfrak{q}$, say $O(\log\log N)$, the algorithm remains quasi-quadratic.
However, Theorem 2.18 does not apply and so the algorithm in the general case
does not certify primality for almost all choices of input point $Q$.

######  Proposition 3.6.

Algorithm 3.3 is quasi quadratic in $c=O(\log N)$ for a fixed $k$.

###### Proof.

For step $2$, use ’binary exponentiation’ to compute $P$ as

$P=\bigoplus_{j}[2^{j}]Q,$

where

$M=\sum_{j}2^{j}=\frac{(\psi(\mathfrak{N})^{k}-1)(\overline{\psi(\mathfrak{N})}^{k}-1)}{{q}^{e_{q}}}$

To compute a single isogeny $[2]Q$ or $Q_{1}+Q_{2}$, use the standard formula
for isogenies, and there are at most $2\log M$ such isogenies to compute in
this step (compute $[2^{x}]Q$, $1\leq x\leq j$ and the addition isognies)
[32]. The cost of computing each isogeny is asymptotically the cost of
multiplication in $(\mathcal{O}_{H}/\mathfrak{N})[x]/(f_{k})$. The cost of
multiplication given remark 3.4 and by using the Schonhage-Strassen algorithm
on the real and imaginary parts of elements of $\mathcal{O}_{H}$ modulo $N$ is
$O(k^{2}(2)^{2}\log N\log\log N)$ with $K=\sqrt{d}$ [29, 2]. Since $2\log M$
is $O(k\log N)$ by the Hasse-Weil bound [32], this step is
$O(\log^{2}N\log\log N)$ for fixed $k$. The next isogenies to compute are
$[q^{x}]Q$ which by the same analysis is $O(\log^{2}N\log\log N)$. Notice that
the other steps are dominated by this. Thus the complexity is $O(c^{2}\log c)$
for fixed $k$. ∎

If _possibly prime_ is returned, run Algorithm 3.1 for $K$,
$\psi(\mathfrak{N})^{m}$, $0\leq m\leq k-1$, and $(\iota)=\mathfrak{q}^{x}$.
Check if the norms of any of the results in the result values divide $N$. If
not, return _prime_. If one does, return _composite_. These return values are
correct by Theorem $2.17$.

######  Proposition 3.7.

In algorithm 3.3, if _prime_ is returned, then $N$ is prime. If _composite_ is
returned, then $N$ is composite.

###### Proof.

The prime case follows directly from Theorem 2.17 and the subsequent
discussion. If composite is returned in step $3$, then
$[(\psi(\mathfrak{N})^{k}-1)(\overline{\psi(\mathfrak{N})}^{k}-1)]Q\not\equiv
0\mod\mathfrak{N}$ and so by definition of the Hecke character (Lemma 2.2),
$\mathfrak{N}$ is not prime. If composite is returned in step $4$, then a
proper factor of $\mathfrak{N}$ was found. ∎

The remaining case is when _probably composite_ is returned. In this case by
Lemma 2.18, with probability at least $1-1/N^{\alpha/2}$, $N$ is composite.
Thus run it through the Miller-Rabin compositeness test, which proves a number
is composite in average $O(\log^{2}N)$ time [6, 22, 27]. If this does not
terminate in $c^{\prime}\log^{2}N$ for some small $c^{\prime}$, utilize the
AKS primality test which runs in $\widetilde{O}(\log^{6}N)$ [3].

######  Theorem 3.8.

Fix $K,k$. Choose a random $Q$ as above. Running Algorithm 3.3 for an $N$ that
satisfies its conditions, along with the subsequent discussion yields a Las
Vegas algorithm for primality with average runtime $\widetilde{O}(\log^{2}N)$
for large enough $\alpha$. Further if $N$ is prime, it is proven prime in
$\widetilde{O}(\log^{2}N)$ time for $1-1/N^{\alpha/2}$ of the input parameters
$Q$.

###### Proof.

The runtime of Algorithm 3.1 is dominated by that of Algorithm 3.3 for fixed
$K=\mathbb{Q}[\sqrt{d}]$. By the above analysis, if _prime_ or _composite_ is
returned before the AKS primality test is used, we have a runtime of
$\widetilde{O}(\log^{2}N)$. The AKS primality test has to be used for a prime
input $N$ with probability less than or equal to $1/N^{\alpha/2}$ by Theorem
2.18. Thus if $N$ is prime the average runtime is
$O((1-1/N^{\alpha/2})\widetilde{O}(\log^{2}N)+1/N^{\alpha/2}\widetilde{O}(\log^{6}N))$.
If $\alpha\leq 1$ is large enough, this average runtime is quasi-quadratic. It
is known that the average runtime of the Miller Rabin compositeness test is
$\widetilde{O}(\log^{2}N)$ for composite $N$ [6, 22, 27]. Thus if $N$ is
composite, the overall average runtime is quasi-quadratic as well.

The latter claim for when $N$ is prime is a direct consequence of Theorem
2.18. ∎

### Example Primality Tests

We outline one more simplification in this section to make it unnecessary to
compute $\mathfrak{N}\subset\mathcal{O}_{H}$ explicitly.

######  Remark 3.9.

Note that class field theory straightforwardly describes the splitting of
prime ideals in the Hilbert class field extension $L/K$ of a quadratic
imaginary field $K$. In particular, if $\mathfrak{k}$ is prime ideal of
$\mathcal{O}_{K}$, then $\mathfrak{k}$ splits into $h_{K}/n$ where $h_{K}$ is
the class number of $K$, and $n$ is the order of $\mathfrak{k}$ in the class
group $Cl(\mathcal{O}_{K})$.

In particular if we wish to test the primality of a rational (non-power)
integer $M$ that splits into two principal ideals $(\iota),(\overline{\iota})$
in $\mathcal{O}_{K}$, we cannot be sure that every prime ideal factor of
$(\iota)$ is principal. Say $\mathfrak{M}$ lies above $(\iota)$ in $H/K$. If
$M$ is prime, however, then $(\iota)$ is a principal prime ideal and by Remark
3.3, $(\iota)$ splits completely in $H/K$. Thus
$N_{H/K}(\mathfrak{M})=(\iota)$ and $\psi(\mathfrak{M})=\pm\iota$ by
Definition 2.3.

We can utilize Theorem 2.17 and Algorithm 3.3, assuming $M$ is prime. However
since $\mathfrak{N}$ is not computed, we must more subtly check conditions
$(1),(2)$. Since $M$ splits completely in $\mathcal{O}_{H}$, we can carry out
computations not on $E/H$ modulo $\mathfrak{M}$ but on the curve
$E_{b}/\mathbb{Q}$ modulo $M$ with coefficients transformed under the
isomorphism
$\phi:(\mathcal{O}_{H}/\mathfrak{M})[x]/(f)\rightarrow\mathbb{Z}/M\mathbb{Z}$,
which would require precomputing roots modulo $M$ for the sequence of rational
integers to test. Alternatively one could do computations on $E/H$ modulo
$\mathfrak{M}$ via remark 3.4 and checking conditions $(1),(2)$ of Theorem
2.17 as follows:

######  Lemma 3.10.

Use notation as above and in Theorem 2.17. If $[q^{e_{q}}]P\equiv O_{E}\mod M$
then condition $(1)$ is satisfied. Otherwise, write $[q^{e_{q}}]P\mod
M=[x_{0}:y_{0}:\sum_{i=0}^{k-1}a_{i}x^{i}]$ and check whether
$M|N_{H/\mathbb{Q}}(a_{i})$ for each $a_{i}$. If so, condition $(1)$ is
satisfied for some $\mathfrak{M}$ above $(\iota)$ in $H/K$; if not, condition
$(1)$ does not hold.

###### Proof.

The first statement is because $(M)\subset\mathfrak{M}$. Iff
$M|N_{H/\mathbb{Q}}(a_{i})$ for each $a_{i}$, then by definition some
$[q^{e_{q}}]P\equiv O_{E}$ modulo _some_ $\mathfrak{M}$ above $(\iota)$. ∎

Then condition $(2)$ is modified:

######  Lemma 3.11.

Condition $(2)$ holds for the same $\mathfrak{M}$ that condition $(1)$ holds
for if $[q^{e_{q}-1}]P$ is strongly nonzero modulo ${M}$.

###### Proof.

This follows immediately because $\mathfrak{M}|M$. ∎

Consider the setup in Theorem 2.18, wherein we must choose $\iota$ so that
$(\iota^{k}-1)=\Gamma\mathfrak{q}^{e^{\prime}}$ with
$q^{e^{\prime}}>N^{1/2+\alpha}$ and $\mathfrak{q}$ principal. We must also
assume that $\iota=\psi(\mathfrak{M})$ for some ideal $\mathfrak{M}$ above
$(\iota)$ in $H/K$, so that condition $(1)$ may be satisfied by Lemma 2.5.
This has an a priori chance of $1/2$ since $\psi(\mathfrak{M})=\pm\iota$. With
these assumptions, utilizing Theorem 2.18 and the fact that there are $h_{K}$
prime ideals $\mathfrak{M}$ above $(\iota)$, there is an
$1-h_{K}/N^{\alpha/2}$ of some $e_{q}$ satsifying conditions $(1),(2)$ with
$N^{1/2}<q^{e_{q}}\leq q^{e^{\prime}}$. The rest of Algorithm 3.3 and the
subsequent discussion may be carried out identically. Note that $h_{K}$ grows
roughly as $\sqrt{|-d|}$ for $K=\mathbb{Q}[\sqrt{-d}]$.

This latter method gives us a very flexible framework for testing the
primality of certain new sequences of rational integers. All the information
required is an elliptic curve $E/H$ with CM by $\mathcal{O}_{K}$, a rational
prime $q=\iota\overline{\iota}$ splitting into two principal ideals over
$\mathcal{O}_{K}$, a primitive $k$-th root of unity $b$ modulo $(\iota)^{n}$
(which can be computed deterministically given a $k$-th root of unity modulo
$(\iota)^{n-1}$ with standard techniques, e.g. in the work of Deng and Lv [8,
Section 4.1]), some $k$-th power non-residue $a$ modulo
$\alpha_{n}=\gamma\iota^{n}+b$, and that $E/H$ has good reduction modulo each
ideal above $(\alpha_{n})$ in $H/K$ (it is sufficient to check
$\gcd(N_{K/\mathbb{Q}}(\alpha_{n}),N_{H/\mathbb{Q}}(\operatorname{disc}(E)))=(1)$).
Then we can test the primality of rational integers in the sequence

$N_{K/\mathbb{Q}}(\alpha_{n})$

when $N_{K/\mathbb{Q}}(\iota^{n})>N^{1/2+\alpha}$. In particular, we expect to
be able to test and prove the primality of $1/2$ of the rational primes in the
sequence (those with $\psi(\mathfrak{M})=\iota$ for $\mathfrak{M}$ above
$(\iota)$, so that $(\psi(\mathfrak{M})^{k}-1)$ is highly factored).

For an example, consider $K=\mathbb{Q}[\sqrt{-17}]$. By sequence A046085 in
the OEIS [33], $K$ has class number $4$. We can write the Hilbert Class field
as $H=\mathbb{Q}[\sqrt{-17},\sqrt{(1+\sqrt{17})/2}]$, as is verified in [16,
Example 1.8.14.]. We can consider the elliptic curve

$E:y^{2}+xy=x^{3}-36/(j-1728)x-1/(j-1728)$

with
$j=8000(5569095+1350704\sqrt{17}+4\sqrt{3876889241278+940283755330\sqrt{17}}),$
which has CM by $K$. Because $-17\equiv 3\mod 4$,
$\mathcal{O}_{K}=\mathbb{Z}[\sqrt{-17}]$. Notice that
$157=(2+3\sqrt{-17})(2-3\sqrt{-17})$ splits into two prime principal ideals in
$\mathcal{O}_{K}$. Consider the sequence

$\alpha_{n}=(2+3\sqrt{-17})^{n}+14\in\mathcal{O}_{K}$

noting that $14^{13}\equiv 1\mod(2+3\sqrt{-17})$ in $\mathcal{O}_{K}$. We have
that $(\alpha_{n})$ is prime to $N_{H/K}(\Delta(E))$ by direct computation.
First checking that $N_{K/\mathbb{Q}}(\alpha_{n})$ is not a power of some
rational integer naively, we can test the primality of the sequence
$N_{K/\mathbb{Q}}(\alpha_{n})$.

##  4 Acknowledgements

I would like to thank Andrew Sutherland for his guidance on this paper and
mentorship in general on elliptic curves, number theory, and algebraic
geometry.

## References

  * [1] Alexander Abatzoglou, Alice Silverberg, Andrew Sutherland, and Angela Wong.  Deterministic elliptic curve primality proving for a special sequence of numbers.  The Open Book Series, 1(1):1–20, 2013.
  * [2] Alexander Abatzoglou, Alice Silverberg, Andrew Sutherland, and Angela Wong.  A framework for deterministic primality proving using elliptic curves with complex multiplication.  Mathematics of Computation, 85(299):1461–1483, 2016.
  * [3] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  Primes is in p.  Annals of mathematics, pages 781–793, 2004.
  * [4] A Oliver L Atkin and François Morain.  Elliptic curves and primality proving.  Mathematics of Computation, 61(203):29–68, 1993.
  * [5] Wieb Bosma.  Primality testing with elliptic curves.  Doctoraalscriptie Report, University of Amsterdam, pages 85–12, 1985.
  * [6] Keith Conrad.  The miller–rabin test.  Encyclopedia of Cryptography and Security, 2011.
  * [7] Richard Crandall and Carl Pomerance.  Prime numbers.  Springer, 2001.
  * [8] Yingpu Deng and Chang Lv.  Primality test for numbers of the form apn+ wn.  Journal of Discrete Algorithms, 33:81–92, 2015.
  * [9] Robert Denomme and Gordan Savin.  Elliptic curve primality tests for fermat and related primes.  Journal of Number Theory, 128(8):2398–2412, 2008.
  * [10] M Deuring.  Die zetafunktion einer algebraischen kurve vom geschlechte eins, i. ii, iii, iv, gott.  Nachr. Akad. Wiss. Göttingen Math.-Phys., 1953.
  * [11] Shafi Goldwasser and Joe Kilian.  Almost all primes can be quickly certified.  In Proceedings of the eighteenth annual ACM symposium on Theory of computing, pages 316–329, 1986.
  * [12] JM Grau, AM Oller-Marcén, and D Sadornil.  A primality test for 4 kp^ n-14 kpn-1 numbers.  Monatshefte für Mathematik, 191(1):93–101, 2020.
  * [13] José Grau, Antonio Oller-Marcén, and Daniel Sadornil.  A primality test for $kp^{n}+1$ numbers.  Mathematics of Computation, 84(291):505–512, 2015.
  * [14] Benedict H Gross.  An elliptic curve test for mersenne primes.  Journal of Number Theory, 110(1):114–119, 2005.
  * [15] Alexander Gurevich and Boris Kunyavskiĭ.  Deterministic primality tests based on tori and elliptic curves.  Finite Fields and Their Applications, 18(1):222–236, 2012.
  * [16] Andrew Kobin.  Class field theory and the study of N-Fermat primes.  Wake Forest University, 2015.
  * [17] Franz Lemmermeyer.  Reciprocity laws: from Euler to Eisenstein.  Springer Science & Business Media, 2013.
  * [18] Arjen K Lenstra and Hendrik W Lenstra Jr.  Algorithms in number theory.  In Algorithms and complexity, pages 673–715. Elsevier, 1990.
  * [19] Hendrik Willem Lenstra.  Elliptic curves and number-theoretic algorithms.  1986\.
  * [20] HW Lenstra.  Primality testing algorithms [after adleman, rumely and williams].  In Séminaire Bourbaki vol. 1980/81 Exposés 561–578, pages 243–257. Springer, 1981.
  * [21] Preda Mihailescu.  Dual elliptic primes and applications to cyclotomy primality proving.  arXiv preprint arXiv:0709.4113, 2007.
  * [22] Gary L Miller.  Riemann’s hypothesis and tests for primality.  Journal of computer and system sciences, 13(3):300–317, 1976.
  * [23] François Morain.  Implementing the asymptotically fast version of the elliptic curve primality proving algorithm.  Mathematics of Computation, 76(257):493–505, 2007.
  * [24] Hiroshi Onuki.  A primality proving using elliptic curves with complex multiplication by imaginary quadratic fields of class number three.  arXiv preprint arXiv:2211.15137, 2022.
  * [25] Carl Pomerance.  Very short primality proofs.  Mathematics of Computation, pages 315–322, 1987.
  * [26] Carl Pomerance.  Primality testing: variations on a theme of lucas.  Congr. Numer, 201:301–312, 2010.
  * [27] Michael O Rabin.  Probabilistic algorithm for testing primality.  Journal of number theory, 12(1):128–138, 1980.
  * [28] Karl Rubin and Alice Silverberg.  Point counting on reductions of cm elliptic curves.  Journal of Number Theory, 129(12):2903–2923, 2009.
  * [29] Arnold Schönhage and Volker Strassen.  Schnelle multiplikation grosser zahlen.  Computing, 7(3):281–292, 1971.
  * [30] Alice Silverberg.  Some remarks on primality proving and elliptic curves.  Advances in Mathematics of Communications, 8(4):427, 2014.
  * [31] Joseph H Silverman.  Advanced topics in the arithmetic of elliptic curves, volume 151\.  Springer Science & Business Media, 1994.
  * [32] Joseph H Silverman.  The arithmetic of elliptic curves, volume 106.  Springer, 2009.
  * [33] Neil J. A. Sloane and OEIS Foundation Inc.  The On-Line Encyclopedia of Integer Sequences, 2022.  Published electronically at http://oeis.org.
  * [34] Yu Tsumura.  Primality tests for $2^{p}\pm 2^{(p+1)/2}+1$ using elliptic curves.  Proceedings of the American Mathematical Society, 139(8):2697–2703, 2011.
  * [35] Lawrence C Washington.  Elliptic curves: number theory and cryptography.  Chapman and Hall/CRC, 2008.


11institutetext: Lund University, Lund, Sweden

# Studying strangeness and baryon production in small systems through
$\bf\Xi-$hadron correlations using the ALICE detector

Jonatan Adolfsson (for the ALICE Collaboration) 11<EMAIL_ADDRESS>
###### Abstract

These proceedings summarise recent measurements of angular correlations
between the $\Xi$ baryon and identified hadrons in pp collisions at
$\sqrt{s}=13\,\mathrm{TeV}$ using the ALICE detector. The results are compared
with both string-based (PYTHIA8 with extensions) and core-corona (EPOS-LHC)
models, to improve our understanding of strangeness and baryon production in
small systems. The results favour baryon production through string junctions
over diquark breaking, but the PYTHIA models fail at describing the relatively
wide $\Xi-$strangeness jet peak, indicating stronger diffusion of strange
quarks in data. On the other hand, EPOS-LHC is missing local conservation of
quantum numbers, making it difficult to draw any conclusion about the core-
corona model.

##  1 Introduction

Today, it is widely accepted that a quark–gluon plasma (QGP) is formed in
heavy-ion collisions. What is not yet understood, however, is that several QGP
key signatures have also been observed in small systems such as high-
multiplicity proton–proton (pp) collisions, where the QGP is not expected to
form. One such signature is the enhanced yields of multi-strange baryons,
which seem to scale smoothly with system size ALICE nature paper .

Several phenomenological models are being developed to try to understand the
origin of this. Two different approaches are being explored. In one approach,
microscopic models based on colour strings are extended with new mechanisms
for strange-baryon formation and other features to mimic collective behaviour.
This approach is used in PYTHIA Sjostrand PYTHIA8 manual , where baryons in
the standard configuration (Monash tune) are formed through diquark breaking.
This is extended by allowing string junctions Skands junctions  and – as a
further extension – rope hadronisation Bierlich ropes , where the latter
provides strangeness enhancement. The other approach is the core-corona model,
which is based on a two-phase state with a QGP-like core and a string-like
corona. This approach is used in EPOS Pierog EPOS-LHC .

The strangeness and baryon production mechanisms predicted by these models are
tested through angular correlations between the $\Xi$ baryon (quark content
dss) and other hadrons, and in particular those with opposite charge or baryon
number. In the string models, strangeness is mostly formed at hadronisation,
which results in short-ranged $\Xi$-strangeness correlations, as opposed to
the core-corona model where strange quarks are largely formed in the core and
can diffuse prior to hadronisation.

##  2 Method

The quantity measured here is the per-trigger yield,

$\mathbb{Y}(\Delta y,\Delta\varphi)=\dfrac{1}{N_{\rm
trig}}\dfrac{\mathrm{d}^{2}N_{\rm pairs}}{\mathrm{d}\Delta
y\mathrm{d}\Delta\varphi},$

which is the distribution of particle pairs in relative rapidity ($\Delta y$)
and azimuthal angle ($\Delta\varphi$) space, divided by the number of triggers
$N_{\rm trig}$. To extract the part that is due to balancing charges, same-
charge (or baryon number) correlations were subtracted from those of opposite
charge.

This was measured for identified $\Xi-\pi$, $\Xi-\rm K$, $\Xi-\rm p$,
$\Xi-\Lambda$, and $\Xi-\Xi$ pairs using approximately $8\cdot 10^{8}$
minimum-bias pp events at $\sqrt{s}=13$ TeV recorded by the ALICE detector
ALICE detector . Pions, kaons, and protons were identified via the specific
energy loss in the Time Projection Chamber and the velocity in the Time-Of-
Flight detectors (pseudorapidity $|\eta|<0.8$). The $\Xi$ and $\Lambda$
baryons were reconstructed from their decay products (e.g.
$\rm\Xi^{-}\rightarrow\pi^{-}+\Lambda$, $\Lambda\rightarrow\pi^{-}+\rm p$), by
making use of their invariant masses and various topological cuts (similar to
what is done in Ref. ALICE strangeness production ). Finally, the multiplicity
dependence of the correlation function was measured by dividing the events
into multiplicity classes (where the lowest percentiles correspond to the
highest multiplicities) based on the response from the V0 counters in the
forward regions ($-3.7<\eta<-1.7$ and $2.8<\eta<5.1$).

##  3 Results

Figure 1 shows angular $\Xi-\pi$ correlations projected on $\Delta\varphi$ and
$\Delta y$ (for the near side, $|\Delta\varphi|<$ $3\pi/10$), for both ALICE
data and models.

Figure 1: Per-trigger yields of $\Xi-\pi$ correlations compared with
predictions from PYTHIA8 (including two extensions) and EPOS-LHC, projected
onto (left) $\Delta\varphi$ and (right) $\Delta y$ on the near side. The lower
panels show the difference between opposite- and same-sign correlations.
Figure 2: Differences between opposite- and same-sign (or baryon number)
correlations projected onto $\Delta y$ on the near side, for (top left)
$\Xi-\rm K$ pairs, (top right) $\Xi-\rm p$ pairs, (bottom left) $\Xi-\Lambda$
pairs, and (bottom right) $\Xi-\Xi$ pairs.

Here, the same-sign correlations are reasonably well described by PYTHIA8
Monash, which can be attributed to good tuning of the single-particle yields,
whereas there is a slight offset for the other models. Similar observations
have also been made for $\Xi-\rm K$ and $\Xi-\rm p$ correlations. On the other
hand, PYTHIA8 Monash underestimates the difference between opposite- and same-
sign (OS-SS) correlations, which is better described by the other models or
tunes. This means that these models more accurately predict the fraction of
the charge from the $\Xi$ baryons that is balanced by pions.

For the other minimum-bias results, only the near-side projections of the OS-
SS difference are shown here, which are summarised in Fig. 2. Here the
predictions from the different models differ significantly, with EPOS-LHC
predicting a nearly flat behaviour, which is not observed in data. The reason
is that local conservation of quantum numbers is not implemented in EPOS, and
this is not necessarily a feature of core-corona models in general. The PYTHIA
models, on the other hand, predict a stronger and narrower peak than what is
observed in data, except for $\Xi-\rm p$ correlations, where no direct
correlations are expected from the diquark breaking mechanism. The junction
and rope extensions are better at predicting $\Xi-$baryon correlations, but
fail at describing $\Xi-\rm K$ correlations. This favours the additional
baryon production mechanism from the junction model, but more development is
needed to accurately describe all observations.

Figure 3: Per-trigger yields of (left) $\Xi-\pi$, (middle) $\Xi-\rm K$, and
(right) $\Xi-\Lambda$ correlations, measured for three different multiplicity
classes and projected onto $\Delta y$ on the near side. The lower panels show
the differences between opposite- and same-sign correlations.

Multiplicity dependent $\Xi-\pi$, $\Xi-\rm K$, and $\Xi-\Lambda$ correlations
are shown in Fig. 3 (similar trends are seen also in $\Xi-\rm p$ and $\Xi-\Xi$
correlations). The shift observed in the baseline with increasing multiplicity
is simply due to the increased particle yields, but a small enhancement is
also observed for the OS-SS difference, along with some narrowing. A similar
behaviour is predicted by PYTHIA, where this can be attributed to radial flow
from colour reconnection, so this effect is likely present also in data
(although possibly from a different origin). However, the relative difference
between multiplicity classes for $\Xi-\Lambda$ correlations is weaker in data
than in PYTHIA (not shown), pointing towards a competing mechanism. This could
mean that the strangeness production mechanism changes with multiplicity, but
more quantitative comparisons with models are needed to conclude in which way.

##  4 Conclusions

While the same-sign $\Xi-$hadron yields predicted by PYTHIA8 Monash largely
describe what is observed in data, which is likely due to good tuning of the
single-particle yields, the same cannot be said about the OS-SS difference.
For this observable, EPOS-LHC predicts an almost flat behaviour, because local
conservation of quantum numbers is not implemented in this model, and thus it
is difficult to conclude anything about the accuracy of the core-corona
approach. On the other hand, the PYTHIA models predict a too strong and narrow
OS-SS peak for $\Xi-$strangeness correlations, which means that the strange
quarks seem to have diffused somewhat in data prior to hadronisation. Finally,
for $\Xi-$baryon correlations the junction extension describes the data better
than the Monash tune, favouring this mechanism for producing baryons.

The multiplicity dependence seems to be dominated by radial flow, but some
observations indicate a competing mechanism, possibly related to changes in
the $\Xi$ production. However, more work is required to conclude how.

## References

  * (1) ALICE Collaboration, Nature Phys. 13, 535-539 (2017)
  * (2) T. SjÃstrand _et al_ , Comput. Phys. Commun. 191, 159-177 (2015)
  * (3) J.R. Christiansen & P.Z. Skands, J. High Energ. Phys. 2015, 3 (2015)
  * (4) C. Bierlich _et al_ , J. High Energ. Phys. 2015, 148 (2015)
  * (5) T. Pierog _et al_ , Phys. Rev. C92, 034906 (2015)
  * (6) ALICE Collaboration, JINST 3, S08002 (2008)
  * (7) ALICE Collaboration, Eur. Phys. J. C71, 1594 (2011)