text:
\section{Introduction}

Cryptosystems based on curves of genus $2$ offer per-bit security
and efficiency comparable with elliptic curve cryptosystems.
However, many of the computational problems
related to creating secure instances of genus~$2$ cryptosystems
are considerably more difficult
than their elliptic curve analogues.
Point counting---or, from a cryptographic point of view,
computing the cardinality of a cryptographic group---offers
a good example of this disparity,
at least for curves defined over large prime fields.
Indeed, while computing the order of a cryptographic-sized
elliptic curve with the Schoof--Elkies--Atkin algorithm
is now routine,
computing the order of a comparable genus $2$ Jacobian requires a significant
computational effort~\cite{GaSc04,GaSc10}.

In this article
we describe a number of improvements to the classical Schoof--Pila algorithm
for genus $2$ curves with explicit and efficient real multiplication (RM).
For explicit RM curves over $\mathbb{F}_p$,
we reduce the complexity of Schoof--Pila from ${\widetilde{O}}(\log^8 p)$
to ${\widetilde{O}}(\log^5 p)$.
We applied a first implementation of our algorithms
to find prime-order Jacobians over 128-bit fields
(comparable to prime-order elliptic curves over 256-bit fields,
and therefore suitable for contemporary cryptographic applications).
Going further,
we were able to compute the order of an RM Jacobian defined over a 512-bit prime field,
far beyond the cryptographic range.
(For comparison, the previous record computation in genus $2$
was over a 128-bit field.)

While these RM curves are special, they are not ``too special'':
Every ordinary genus $2$ Jacobian over a finite field
has RM; our special requirement is that this RM be known in advance
and be efficiently computable.
The moduli of curves with RM by
a fixed ring form $2$-dimensional subvarieties (Humbert surfaces)
in the $3$-dimensional moduli space of all genus~$2$ curves.
We can generate random curves with the specified RM by choosing
random points on an explicit model of the corresponding Humbert
surface~\cite{Gruenewald}.
In comparison with elliptic curves,
for which the moduli space is one-dimensional, this
still gives an additional degree of freedom in the random curve selection.
To generate random curves with efficiently computable RM, we choose
random curves from some known one and two-parameter families
(see~\S\ref{sec:families}).

Curves with efficiently computable RM
have an additional benefit in cryptography:
the efficient endomorphism can be used to accelerate scalar multiplication
on the Jacobian, yielding faster encryption and
decryption~\cite{Kohel--Smith,Parketal,Takashima}.
The RM formul\ae{} are also compatible with
fast arithmetic based on theta functions~\cite{Gaudry-theta}.

\section{Conventional Point Counting for Genus $2$ Curves}

Let $\mathcal{C}$ be a curve of genus 2 over a finite field $\mathbb{F}_q$, of odd
characteristic, defined by an affine model $y^2 = f(x)$,
where $f$ is a squarefree polynomial of degree $5$ or $6$ over $\mathbb{F}_q$.
Let $\Jac{\mathcal{C}}$ be the Jacobian of $\mathcal{C}$; we assume $\Jac{\mathcal{C}}$ is ordinary and
absolutely simple.  Points on $\Jac{\mathcal{C}}$ correspond to
degree-$0$ divisor classes on $\mathcal{C}$;
we use the Mumford representation for divisor classes
together with the usual Cantor-style composition and reduction algorithms
for divisor class arithmetic~\cite{Galbraith--Harrison--Mireles-Morales,Cantor-reduction}.
Multiplication by $\ell$ on $\Jac{\mathcal{C}}$ is denoted by $[\ell]$, and
its kernel by $\Jac{\mathcal{C}}[\ell]$. More generally, if $\phi$ is an
endomorphism of $\Jac{\mathcal{C}}$ then $\Jac{\mathcal{C}}[\phi] = \ker(\phi)$,
and if $S$ is a set of endomorphisms then $\Jac{\mathcal{C}}[S]$ denotes
the intersection of $\ker(\phi)$ for $\phi$ in $S$.

\subsection{The Characteristic Polynomial of Frobenius}
\label{sec:Frobenius-charpoly}

We let $\pi$ denote the Frobenius endomorphism of $\Jac{\mathcal{C}}$,
with Rosati dual $\dualof{\pi}$ (so $\pi\dualof{\pi} = [q]$).
The characteristic polynomial of $\pi$
has the form
\begin{equation}
\label{eq:Frobenius-charpoly}
  \chi(T) = T^4 - s_1 T^3 + (s_2 + 2q)\, T^2 - q s_1 T + q^2,
\end{equation}
where $s_1$ and $s_2$ are integers, and $s_2$ is a translation
of the standard definition.
The polynomial $\chi(T)$ determines the cardinality of $\Jac{\mathcal{C}}(\mathbb{F}_{q^k})$
for all $k$: in particular, $\#\Jac{\mathcal{C}}(\mathbb{F}_{q}) = \chi(1)$.
We refer to the determination of $\chi(T)$ as the {\it point counting problem}.

The polynomial $\chi(T)$ is a {\it Weil polynomial}:
all of its complex roots lie on the circle $|z| = \sqrt{q}$.
This implies the Weil bounds
\begin{equation}
\label{eq:s_1s_2-Weil-bounds}
    |s_1| \le 4\sqrt{q}\quad \text{ and }\quad |s_2| \le 4q.
\end{equation}
However, the possible values of $(s_1,s_2)$
do not fill the whole rectangle specified by the Weil bounds.
R\"uck~\cite[Theorem 1.1]{Ruck90}
shows that in fact $s_1$ and $s_2$ satisfy
\[
	s_1^2 - 4 s_2 \ge 0 \text{ and } s_2 + 4q \ge 2|s_1| ,
\]
so the possible values of $(s_1,s_2)$ are in the following domain:
\begin{center}
\scalebox{0.75}{
\begin{tikzpicture}[yscale=0.5]
\draw[very thick,->] (-4,0) -- (4,0) node[right] {$s_1/\sqrt{q}$};
\draw[very thick,->] (0,-4) -- (0,4) node[above] {$s_2/q$};
\path[thick,draw=blue, fill=blue!20, opacity=0.6]
(0,-4) -- (-4,4) --
plot[domain=-4:4] (\x,\x*\x/4) -- cycle;
\foreach \x in {-4,...,4} \draw[yscale=2] (\x,-0.1) -- (\x,0.1);
\foreach \x in {-4,...,4} \draw (-0.1,\x) -- (0.1,\x);
\end{tikzpicture}
}
\end{center}

\subsection{The Classical Schoof--Pila Algorithm for Genus $2$ Curves}
\label{sec:Schoof--Pila}

The objective of point counting is to compute $\chi(T)$, or equivalently
the tuple of integers $(s_1,s_2)$.  When the characteristic of $\mathbb{F}_{q}$
is large, the conventional approach
is to apply the Schoof--Pila algorithm
as far as is practical, before passing to a baby-step giant-step
algorithm if necessary (see~\S\ref{sec:BSGS}).
The strategy of Schoof's algorithm
and its generalizations is to compute the polynomials
$\chi_\ell(T) = \chi(T) \bmod (\ell)$ for sufficiently many primes (or prime
powers) $\ell$ to reconstruct $\chi(T)$ using the Chinese Remainder Theorem.

Since $\chi_\ell(T)$ is the characteristic polynomial of $\pi$
restricted to $\Jac{\mathcal{C}}[\ell]$ (see~\cite[Proposition 2.1]{Pila}),
we have
$$
\chi_\ell(\pi)(D) = 0 \text{ for all } D \text{ in } \Jac{\mathcal{C}}[\ell].
$$

Conversely, to compute $\chi_\ell(T)$ we let $D$ be a generic
element of $\Jac{\mathcal{C}}[\ell]$ (as in~\S\ref{sec:kernel-ideal} below),
compute the three points
\[
    (\pi^2 + [\bar{q}])^2(D),\ \
    (\pi^2 + [\bar{q}])\pi(D),\ \text{and}\ \
    \pi^2(D),
\]
and then search for the coefficients $(\bar{s}_1,\bar{s}_2)$ of
$\chi_\ell(T)$ in $(\mathbb{Z}/\ell\mathbb{Z})^2$, for which the linear relation
\begin{equation}
\label{eq:conventional-ell-test}
     (\pi^2 + [\bar{q}])^2(D)
    - [\bar{s}_1]\,(\pi^2 + [\bar{q}])\pi(D)
    + [\bar{s}_2]\,\pi^2(D) = 0
\end{equation}
holds.
If the minimal polynomial of $\pi$ on $\Jac{\mathcal{C}}[\ell]$ is
a proper divisor of $\chi_\ell(T)$---which occurs for at most
a finite number of $\ell$ dividing $\mathrm{disc}(\chi)$---then
the polynomial so determined is not unique, but
$\chi_\ell(T)$ can be determined by deducing the correct
multiplicities of its factors.

Once we have computed $\chi_\ell(T)$ for sufficiently many $\ell$,
we reconstruct~$\chi(T)$ using the Chinese Remainder Theorem.
The Weil and R\"uck bounds together with
a weak version of the prime number theorem tell us how many
$\ell$ are required: Pila notes in~\cite[\S1]{Pila}
that the set of $O(\log q)$ primes $\ell < 21\log q$ will suffice.
We analyse the complexity of the classical Schoof--Pila algorithm
in~\S\ref{sec:Schoof--Pila-complexity}.

\subsection{Endomorphisms and Generic Kernel Elements}
\label{sec:kernel-ideal}

We now recall how to contruct an effective version of a generic
$\ell$-torsion element. We present it in a slightly more general setting,
so that we can use this ingredient in the subsequent RM-specific
algorithm. Therefore, we show how to compute with a generic element
of the kernel of some endomorphism $\phi$ of $\Jac{\mathcal{C}}$, whereas $\phi$ is
just $[\ell]$ in the classical algorithm.

\begin{definition}\label{def:explicit}
    Fix an embedding $P \mapsto D_P$ of $\mathcal{C}$ in $\Jac{\mathcal{C}}$.
    We say that an endomorphism $\phi$ of~$\Jac{\mathcal{C}}$
    is \emph{explicit} if we can effectively compute polynomials
    $d_0,d_1,d_2,e_0,e_1,$ and $e_2$ such that
    if $P = (x_P,y_P)$ is a generic point of $\mathcal{C}$, then
    the Mumford representation of $\phi(D_P)$ is given by
    \begin{equation}
    \label{eq:endomorphism-image}
        \phi(D_P)
        =
        \Mumfordbig{
            x^2 + \frac{d_1(x_P)}{d_2(x_P)}x + \frac{d_0(x_P)}{d_2(x_P)} ,
            y - y_P\left(
                \frac{e_1(x_P)}{e_2(x_P)}x + \frac{e_0(x_P)}{e_2(x_P)}
            \right)
        }
        .
    \end{equation}
    The $d_0$, $d_1$, $d_2$, $e_0$, $e_1$, and $e_2$
    are called the \emph{$\phi$-division polynomials}.
\end{definition}

If $\phi$ is an explicit endomorphism, then
we can use \eqn{eq:endomorphism-image} (extending $\mathbb{Z}$-linearly)
to evaluate $\phi(D)$ for general divisor classes $D$ in $\Jac{\mathcal{C}}$.
In the case $\phi = [\ell]$, the $[\ell]$-division polynomials
are the $\ell$-division polynomials of Cantor~\cite{Cantor-division}.
The $\phi$-division polynomials depend on the choice of embedding $P
\mapsto D_P$;
we will make this choice explicit when computing the $\phi$-division
polynomials for each of our families
in~\S\ref{sec:families}.

To compute a generic element of $\Jac{\mathcal{C}}[\phi]$,
we generalize the approach of~\cite{GaSc04}
(which computes generic elements of $\Jac{\mathcal{C}}[\ell]$).
The resulting algorithm is essentially the same as in~\cite[\S3]{GaSc04}
(except for the parasite computation step, which we omit)
with $\phi$-division polynomials replacing $\ell$-division polynomials,
so we will only briefly sketch it here.

Let $D = \Mumford{x^2 + a_1x + a_0, y - (b_1x + b_0)}$
be (the Mumford representation of) a generic point of $\Jac{\mathcal{C}}$.
We want to compute a triangular ideal $I_\phi$
in $\mathbb{F}_{q}[a_1,a_0,b_1,b_0]$
vanishing on the nonzero elements of $\Jac{\mathcal{C}}[\phi]$.
The element~$D$ equals $D_{(x_1,y_1)} + D_{(x_2,y_2)}$,
where $(x_1,y_1)$ and $(x_2,y_2)$ are generic points of $\mathcal{C}$.
To find a triangular system
of relations on the $a_i$ and $b_i$
such that $D$ is in $\Jac{\mathcal{C}}[\phi]$
we solve for $x_1$, $y_1$, $x_2$, and $y_2$ in
\[
    \phi(D_{(x_1,y_1)}) = -\phi(D_{(x_2,y_2)}) ,
\]
applying \eqn{eq:endomorphism-image} and using resultants
computed with the evaluation--interpolation technique
of~\cite[\S 3.1]{GaSc04}.
We then resymmetrize as in~\cite[\S 3.2]{GaSc04}
to express the result in terms of the~$a_i$ and~$b_i$.
We can now compute with a ``generic'' element
$\Mumford{x^2 + a_1x + a_0, y - (b_1x + b_0)}$
of~$\Jac{\mathcal{C}}[\phi]$
by reducing the coefficients modulo~$I_\phi$
after each operation.

Following the complexity analysis of~\cite[\S3.5]{GaSc04},
we can compute a triangular representation for $I_\phi$
in $O(\delta^2\mathsf{M}(\delta)\log\delta + \mathsf{M}(\delta^2)\log\delta)$
field operations,
where $\delta$ is the maximum among the degrees of
the $\phi$-division polynomials,
and $\mathsf{M}(d)$ is the number of operations
required to multiply polynomials of degree $d$ over $\mathbb{F}_{q}$.
Using asymptotically fast multiplication algorithms,
we can therefore compute~$I_\phi$ in~${\widetilde{O}}(\delta^3)$ field operations.
The degree of $I_\phi$ is in $O(\delta^2)$;
with this triangular representation,
each multiplication modulo $I_\phi$ costs
${\widetilde{O}}(\delta^2)$ field operations.

\subsection{Complexity of Classical Schoof--Pila Point Counting}
\label{sec:Schoof--Pila-complexity}

\begin{proposition}
    The complexity of the classical Schoof--Pila algorithm
    for a curve of genus $2$ over $\mathbb{F}_{q}$ is in ${\widetilde{O}}((\log q)^8)$.
\end{proposition}
\begin{proof}
    To determine $\chi(T)$,
    we need to compute $\chi_\ell(T)$ for $O(\log q)$ primes $\ell$
    in $O(\log q)$.
    To compute $\chi_\ell(T)$,
    we must first compute the $\ell$-division polynomials,
    which have degrees in $O(\ell^2)$.
    We then compute the kernel ideal $I_\ell$;
    according to the previous subsection,
    the total cost is in ${\widetilde{O}}(\ell^6)$ field operations.
    The cost of checking \eqn{eq:conventional-ell-test}
    against a generic element of $\Jac{\mathcal{C}}[\ell]$
    decomposes into the cost of computing Frobenius images of the generic
    element in ${\widetilde{O}}(\ell^4\log q)$ and of finding the matching pair $(\bar s_1,
    \bar s_2)$ in ${\widetilde{O}}(\ell^5)$ field operations.
    So the total complexity for computing $\chi_\ell(T)$ is
    in ${\widetilde{O}}(\ell^4(\ell^2+\log q))$ field operations.
    In terms of bit operations, for each $\ell$ bounded by $O(\log q)$,
    we compute $\chi_\ell(T)$ in time ${\widetilde{O}}((\log q)^7)$, and the result
    follows from the addition of these costs for all the different
    $\ell$'s.
\qed
\end{proof}

\subsection{Baby-Step Giant-Step Algorithms}
\label{sec:BSGS}

In practice, computing $\chi_\ell(T)$ with classical Schoof--Pila becomes
impractical for large values of $\ell$. The usual approach is to carry out
the Schoof--Pila algorithm to the extent possible, obtaining congruences
for $s_1$ and $s_2$ modulo some integer $M$, before completing the calculation
using a generic group algorithm such as baby-step giant-step (BSGS).
Our BSGS algorithm of choice is the low-memory parallelized variant of the
Matsuo--Chao--Tsuji algorithm~\cite{GaScXX,Matsuo--Chao--Tsuji}.

The bounds in \eqn{eq:s_1s_2-Weil-bounds} imply that the
search space of candidates for $(s_1,s_2)$ is in $O(q^{3/2})$, and
a pure BSGS approach finds $(s_1,s_2)$ in time and space ${\widetilde{O}}(q^{3/4})$.
However, when we apply BSGS after a partial Schoof--Pila computation,
we obtain a congruence for $(s_1,s_2)$ modulo~$M$.
If $M < 8q$, then the size of the search space
is reduced to $O(q^{3/2}/M^2)$, and the complexity for
finding $(s_1,s_2)$ is reduced to ${\widetilde{O}}(q^{3/4}/M)$.
For larger $M$, the value of $s_1$ is fully determined, and the problem
is reduced to a one-dimensional search space of size $O(q/M)$ for
which the complexity becomes ${\widetilde{O}}(\sqrt{q/M})$.

\section{Point Counting in Genus $2$ with Real Multiplication}
\label{sec:RM}

By assumption, $\Jac{\mathcal{C}}$ is ordinary and simple, so $\chi(T)$
is an irreducible polynomial defining a quartic CM-field with
real quadratic subfield $\mathbb{Q}(\sqrt{\Delta})$.  We say that $\Jac{\mathcal{C}}$
(and~$\mathcal{C}$) has \emph{real multiplication} (RM) by $\mathbb{Q}(\sqrt{\Delta}\,)$.
For a randomly selected curve, $\Delta$ is in $O(q)$; but in the sequel
we consider families of curves with RM by $\mathbb{Q}(\sqrt{\Delta})$ for small
$\Delta$ (= $5$ or $8$), admitting an explicit (in the sense of
Definition~\ref{def:explicit}) endomorphism
$\phi$ such that
\begin{equation}
\label{eq:real-subring}
    \mathbb{Z}[\phi] = \mathbb{Q}(\sqrt{\Delta}) \cap \ensuremath{\mathrm{End}}(\Jac{\mathcal{C}})
\end{equation}
(that is, $\mathbb{Z}[\phi]$ is the full real subring of $\ensuremath{\mathrm{End}}(\Jac{\mathcal{C}})$), and
\[
    \mathrm{disc}\left(\mathbb{Z}[\phi]\right) = \Delta .
\]
We presume that
the trace $\mathrm{Tr}(\phi)$ and norm $\mathrm{N}(\phi)$, such that
$\phi^2 - \mathrm{Tr}(\phi)\phi + \mathrm{N}(\phi) = 0$, are known.
We also suppose that $\phi$ is \emph{efficient}, in the following sense:

\begin{definition}
    We say that an explicit endomorphism $\phi$ is
    \emph{efficiently computable}
    if the cost of evaluating $\phi$ at points of $\Jac{\mathcal{C}}(\mathbb{F}_{q})$
    requires only $O(1)$
    field operations
    (comparable to a few group operations in $\Jac{\mathcal{C}}$).
    In practice,
    this means that
    the $\phi$-division polynomials have small degree.
\end{definition}

The existence of an efficiently computable $\phi$ and knowledge
of $\Delta$ allows us to make significant improvements to each stage
of the Schoof--Pila algorithm.
Briefly:
in~\S\ref{sec:RM-char-poly} we use~$\phi$ to simplify the testing
procedure for each~$\ell$;
in~\S\ref{sec:split-prime} we show that when~$\ell$ splits in~$\mathbb{Z}[\phi]$,
we can use $\phi$ to obtain a radical reduction in complexity for
computing $\chi_\ell(T)$; and
in~\S\ref{sec:search-space} we show that knowing an effective $\phi$ allows
us to use many fewer primes $\ell$.

\subsection{The RM Characteristic Polynomial}
\label{sec:RM-Frobenius-charpoly}

Let $\psi = \pi+\pi^\dagger$;
we consider $\mathbb{Z}[\psi]$,
a subring of the real quadratic subring of $\ensuremath{\mathrm{End}}(\Jac{\mathcal{C}})$.
The characteristic polynomial of $\psi$ is the {\it real Weil polynomial}
\begin{equation}
\label{eq:real-charpoly}
    \xi(T) = T^2 - s_1 T + s_2;
\end{equation}
the discriminant of $\mathbb{Z}[\psi]$ is $\Delta_0 = s_1^2 - 4 s_2$.
The analogue for $(s_1,\Delta_0)$ of R\"uck's bounds is
\begin{equation}
\label{eq:s_1d_0-Ruck-bounds}
    (|s_1| - 4\sqrt{q})^2 \ge \Delta_0 = s_1^2 - 4 s_2 \ge 0 .
\end{equation}
Equation \eqn{eq:real-subring} implies that
$\mathbb{Z}[\psi]$ is contained in $\mathbb{Z}[\phi]$,
so there exist integers $m$ and $n$ such that
\begin{equation}
\label{eq:RM-psi-relation}
    \psi = m + n\phi .
\end{equation}
Both $s_1$ and $s_2$ are determined by $m$ and $n$: we have
\begin{equation}
\label{eq:s_1s_2-from-nm}
    s_1 = \mathrm{Tr}(\psi) = 2m + n\mathrm{Tr}(\phi)
    \quad \text{and} \quad
    s_2 = \mathrm{N}(\psi) = (s_1^2 - n^2\Delta)/4.
\end{equation}
In fact \(n\) is the conductor of \(\mathbb{Z}[\psi]\) in \(\mathbb{Z}[\phi]\)
up to sign: \( |n| = [\mathbb{Z}[\phi]:\mathbb{Z}[\psi]] \),
and hence
\[
    \Delta_0 = \mathrm{disc}(\mathbb{Z}[\psi]) = s_1^2 - 4 s_2 = n^2 \Delta .
\]
The square root of the bounds
in \eqn{eq:s_1d_0-Ruck-bounds} gives
bounds on $s_1$ and~$n$:
\[
    4\sqrt{q} - |s_1| \ge \sqrt{\Delta_0} = |n| \sqrt{\Delta} \ge 0 ;
\]
In particular,
\( |s_1| \le 4\sqrt{q} \)
and
\( |n| \le 4\sqrt{q/\Delta} \).
Applying the relation in~\eqn{eq:s_1s_2-from-nm},
we have the bounds
\begin{equation}
\label{eq:m-n-bounds}
    |m| \le 2(|\mathrm{Tr}(\phi)| + \sqrt{\Delta})\sqrt{q/\Delta}
    \quad \text{and}\quad
    |n| \le 4\sqrt{q/\Delta}
    .
\end{equation}
Both $|m|$ and $|n|$ are in $O(\sqrt{q})$.

\subsection{An Efficiently Computable RM Relation}
\label{sec:RM-char-poly}

We can use our efficiently computable endomorphism $\phi$
to replace the relation
of \eqn{eq:conventional-ell-test}
with a more efficiently computable alternative.
Multiplying \eqn{eq:RM-psi-relation} through by $\pi$,
we have
\[
    \psi\pi = \pi^2 + [q] = m\pi + n\phi\pi.
\]
We can therefore compute $\bar{m} = m\bmod\ell$ and $\bar{n} = n\bmod\ell$
by letting $D$ be a generic $\ell$-torsion point,
computing the three points
\[
    (\pi^2 + [\bar{q}])(D) ,
    \ \
    \pi(D) ,
    \ \ \text{and} \ \
    \phi\pi(D) ,
\]
and then
searching for the $\bar{m}$ and $\bar{n}$ in $\mathbb{Z}/\ell\mathbb{Z}$
such that
\begin{equation}
\label{eq:RM-ell-test}
  (\pi^2 + [\bar{q}])(D) - [\bar{m}]\pi(D) - [\bar{n}]\phi\pi(D) = 0
\end{equation}
holds; we can find such an $\bar{m}$ and $\bar{n}$ in $O(\ell)$ group
operations.

Solving \eqn{eq:RM-ell-test} rather than
\eqn{eq:conventional-ell-test} has several advantages.
First, computing
\((\pi^2 + [\bar{q}])(D)\), \(\pi(D)\), and \(\phi\pi(D)\)
requires only two applications of Frobenius,
instead of the four required to compute
\((\pi^2 + [\bar{q}])^2(D)\),
\((\pi^2 + [\bar{q}])\pi(D)\),
and \(\pi^2(D)\)
(and Frobenius applications are costly in practice).
Moreover, either $s_2$ needs to be determined in $O(q)$, or else
the value of $n$ in \eqn{eq:conventional-ell-test}
leaves a sign ambiguity for each prime $\ell$, because only
$n^2 \bmod \ell$ can be deduced from $(\bar{s}_1, \bar{s}_2)$.
In contrast, \eqn{eq:RM-ell-test} determines $n$ directly.

\subsection{Exploiting Split Primes in $\mathbb{Q}(\sqrt{\Delta})$}
\label{sec:split-prime}

Let $\mathbb{Z}[\phi] \subset \ensuremath{\mathrm{End}}(\Jac{\mathcal{C}})$ be an RM order in $\mathbb{Q}(\phi) \cong \mathbb{Q}(\sqrt{\Delta})$.
Asymptotically, half of all primes $\ell$ split: $(\ell) = \mathfrak{p}_1 \mathfrak{p}_2$
in $\mathbb{Z}[\phi]$, where $\mathfrak{p}_1 + \mathfrak{p}_2 = (1)$ (and this carries over to
prime powers $\ell$).
This factorization gives a decomposition of the $\ell$-torsion
\[
    \Jac{\mathcal{C}}[\ell] = \Jac{\mathcal{C}}[\mathfrak{p}_1] \oplus \Jac{\mathcal{C}}[\mathfrak{p}_2].
\]
In particular, any $\ell$-torsion point $D$ can be uniquely expressed
as a sum $D = D_1 + D_2$ where $D_i$ is in $\Jac{\mathcal{C}}[\mathfrak{p}_i]$.

According to the Cohen--Lenstra heuristics~\cite{CohenLenstra}, more
than 75\% of RM fields have class number 1;
in each of the explicit RM families in \S\ref{sec:families},
the order $\mathbb{Z}[\phi]$ has class number 1.
All ideals are principal in such an order,
so we may find a generator
for each of the ideals $\mathfrak{p}_i$.  Furthermore, the following lemma shows
that we can find a generator which is not too large.

\begin{lemma}
\label{lemma:generator-reduction}
    If $\mathfrak{p}$ is a principal ideal of norm $\ell$ in a real quadratic order $\mathbb{Z}[\phi]$,
    then there exists an effectively computable generator of $\mathfrak{p}$
    with coefficients in $O(\sqrt{\ell})$.
\end{lemma}
\begin{proof}
    Let $\alpha$ be a generator of $\mathfrak{p}$,
    and $\varepsilon$ a fundamental unit of $\mathbb{Z}[\phi]$.
    Let $\gamma \mapsto \gamma_1$
    and $\gamma \mapsto \gamma_2$
    be the two embeddings of $\mathbb{Z}[\phi]$ in $\mathbb{R}$,
    indexed so that
    $|\alpha_1| \ge |\alpha_2|$ and $|\varepsilon_1| > 1$
    (replacing $\varepsilon$ with $\varepsilon^{-1}$ if necessary).
    Then $R = \log(|\varepsilon_1|)$ is the regulator of $\mathbb{Z}[\phi]$.
    Set $\beta = \varepsilon^{-k}\alpha$,
    where $k = [\log(|\alpha_1/\sqrt{\ell}|)/R]$;
    then $\beta = a + b\phi$ is a new generator for $\mathfrak{p}$ such that
    \[
        -\frac{1}{2}
        \le
        \frac{\log(|\beta_i/\sqrt{\ell}|)}{R}
        \le
        \frac{1}{2}\cdot
     \]
    From the preceding bounds,
    \( |\beta_1+\beta_2| = |2a + b\mathrm{Tr}(\phi)| \)
    and
    \( |\beta_1-\beta_2| = |b\sqrt{\Delta}| \)
    are bounded by $2e^{R/2}\sqrt{\ell}$.
    Since $\mathrm{Tr}(\phi)$, $\Delta$ and $R$ are
    fixed constants, $|a|$ and $|b|$ are in $O(\sqrt{\ell})$.
    The ``effective'' part of the result follows from classical
    algorithms for quadratic fields.
    \qed
\end{proof}

\begin{lemma}
\label{lemma:alpha-division-polynomials}
    Let $\Jac{\mathcal{C}}$ be the Jacobian of a genus $2$ curve
    over a finite field $\mathbb{F}_q$
    with an efficiently computable RM endomorphism $\phi$.
    There exists an algorithm which, given a principal ideal $\mathfrak{p}$ of
    norm $\ell$ in $\mathbb{Z}[\phi]$,
    computes an explicit generator $\alpha$ of $\mathfrak{p}$
    and the $\alpha$-division polynomials in $O(\ell)$ field operations.
\end{lemma}
\begin{proof}
    By Lemma~\ref{lemma:generator-reduction}, we can compute a generator
    $\alpha = [a] + [b]\phi$ with $a$ and $b$ in $O(\sqrt{\ell})$.
    The $[a]$- and $[b]$-division polynomials have degrees in $O(\ell)$,
    and can be determined in $O(\ell)$ field operations. The division
    polynomials for the sum $\alpha = [a] + [b]\phi$ require one sum
    and one application of $\phi$; and since $\phi$ is efficiently
    computable, this increases the division polynomial degrees and
    computing time by at most a constant factor.
\qed
\end{proof}
We can now state the main theorem for RM point counting.
\begin{theorem}
\label{theorem:RM-ptc-complexity}
    There exists an algorithm for the point counting problem in a family
    of genus~2 curves with efficiently computable RM of class number 1,
    whose complexity is in ${\widetilde{O}}((\log q)^5)$.
\end{theorem}
\begin{proof}
    Let $\Jac{\mathcal{C}}$ be a Jacobian in a family with efficiently computable
    RM by $\mathbb{Z}[\phi]$.
    Suppose that $\ell$ is prime, $(\ell) = \mathfrak{p}_1 \mathfrak{p}_2$ in $\mathbb{Z}[\phi]$,
    and that the $\mathfrak{p}_i$ are principal.
    By Lemma~\ref{lemma:alpha-division-polynomials} we can compute
    representative $\alpha$-division polynomials for $\Jac{\mathcal{C}}$ for
    each $\mathfrak{p}$ in $\{\mathfrak{p}_1,\mathfrak{p}_2\}$ in time ${\widetilde{O}}(\ell)$, hence
    generic points $D_i$ in $\Jac{\mathcal{C}}[\mathfrak{p}_i]$.

    We recall that \eqn{eq:RM-ell-test} is the homomorphic
    image under $\pi$ of the equation
    $$
    \psi(D) - [\bar{m}](D) - [\bar{n}]\phi(D) = 0.
    $$
    When applied to $D_i$ in $\Jac{\mathcal{C}}[\mathfrak{p}_i]$, both $\psi$ and $\phi$
    act as elements of $\mathbb{Z}[\phi]/\mathfrak{p}_i \cong \mathbb{Z}/\ell\mathbb{Z}$. Moreover
    $\bar{x}_i = \phi \bmod \mathfrak{p}_i$ is known, and it remains to determine
    $\bar{y}_i = \psi \bmod \mathfrak{p}_i$ by means of
    the discrete logarithm
    $$
    \psi(D_i) = [\bar{y}_i](D_i) = [\bar{m}+\bar{n}\bar{x}_i](D_i)
    $$
    in the cyclic group $\langle D_i \rangle \cong \mathbb{Z}/\ell\mathbb{Z}$.
    The application of $\pi$ transports this discrete logarithm
    problem to that of solving for $\bar{y}_i$ in
    $$
    D_i'' = [\bar{y}_i]D',
    $$
    where $D_i' = \pi(D_i)$ and $D_i'' = (\pi^2+[\bar{q}])(D_i)$.
    By the CRT, from $(\bar{y}_1,\bar{y}_2)$ in $(\mathbb{Z}/\ell\mathbb{Z})^2$
    we recover $\bar{y}$ in $\mathbb{Z}[\phi]/(\ell)$, from which we solve
    for $(\bar{m},\bar{n})$ in $(\mathbb{Z}/\ell\mathbb{Z})^2$ such that
    $$
    \bar{y} = \bar{m} + \bar{n}\phi \in \mathbb{Z}[\phi]/(\ell).
    $$
    The values of $(\bar{s}_1,\bar{s}_2)$ are then recovered from
    \eqn{eq:s_1s_2-from-nm}.

    The ring $\mathbb{Z}[\phi]$ is fixed, so as $\log q$ goes to infinity
    we find that 50\% of all primes $\ell$ split in $\mathbb{Z}[\phi]$
    by the Chebotarev density theorem.
    It therefore suffices to consider split
    primes in $O(\log q)$.
    In comparison with the conventional algorithm
    presented in \S\ref{sec:Schoof--Pila}, we reduce from
    computation modulo the ideal for $\Jac{\mathcal{C}}[\ell]$ of degree in
    $O(\ell^4)$, to computation
    modulo the ideals for $\Jac{\mathcal{C}}[\mathfrak{p}_i]$ of degree in $O(\ell^2)$.
    This means a reduction from ${\widetilde{O}}(\ell^4(\ell^2+\log q))$
    to ${\widetilde{O}}(\ell^2(\ell+\log q))$ field operations for the determination of
    each $\chi_{\ell}(T)$,
    giving the stated reduction in
    total complexity from ${\widetilde{O}}((\log q)^8)$ to ${\widetilde{O}}((\log q)^5)$.
\qed
\end{proof}

\begin{remark}
\label{remark:RM-Schoof-Pila-reduction}
    Computing $(m,n)$ instead of $(s_1,s_2)$ allows us to reduce the number
    of primes~$\ell$ to be considered by about a half, since
    by~\eqn{eq:m-n-bounds} their product
    needs to be in $O(\sqrt{q})$ instead of $O(q)$.
    While this changes only the constant in the asymptotic complexity
    of the algorithm, it yields a significant improvement in practice.
\end{remark}

\begin{remark}
\label{remark:RM-class-number-not-1}
If $\mathbb{Z}[\phi]$ does not have class number $1$, and if $(\ell) = \mathfrak{p}_1\mathfrak{p}_2$
where the $\mathfrak{p}_i$ are not principal, then we may
use a small complementary ideal $(c) = \mathfrak{c}_1\mathfrak{c}_2$ such that $\mathfrak{c}_i\mathfrak{p}_i$
are principal in order to apply Lemma~\ref{lemma:alpha-division-polynomials}
to a larger proportion of small ideals.
Moreover, if $(\bar{m},\bar{n})$ is known modulo $c$, this can be used
to reduce the discrete log problem modulo $\ell$.
Again, since a fixed positive density $1/2h$ of primes are both split
and principal, where $h$ is the class number of $\mathbb{Z}[\phi]$, this does
not affect the asymptotic complexity.
Moreover, the first occurrence of a nontrivial class group is for
$\Delta = 65$, beyond the current range for which an explicit RM
construction is currently known.
\end{remark}

\subsection{Shrinking the BSGS Search Space}
\label{sec:search-space}

In the context of the conventional Schoof-Pila algorithm, we need to
find $s_1$ in $O(\sqrt{q})$ and $s_2$ in $O(q)$.
However, \eqn{eq:RM-psi-relation}, and the effective form of
\eqn{eq:RM-ell-test} (valid for all points $D$ of $\Jac{\mathcal{C}}$),
replaces the determination of $(s_1,s_2)$ with the tuple $(m,n)$ of
integers in $O(\sqrt{q})$.
As a result, the search space is reduced from $O(q^{3/2})$ to $O(q)$.
Thus the BSGS strategy can find $(m,n)$ (which determines $(s_1,s_2)$)
in time and space $O(\sqrt{q})$, compared with $O(q^{3/4})$ when searching
directly for $(s_1,s_2)$.

As in the general case, if one knows $(m,n)$ modulo an integer $M$, then
the area of the search rectangle is reduced by a factor of $M^2$, so we
find the tuple $(m,n)$ in $O(\sqrt{q}/M)$ group operations.
Contrary to the general case of \S\ref{sec:BSGS}, since $m$ and $n$ have
the same order of magnitude, the speed-up is always by a factor of $M$.

\section{Examples of Families of Curves with Explicit RM}
\label{sec:families}

We now exhibit some families of curves and efficient RM endomorphisms
that can be used as sources of inputs to our algorithm.

\subsection{Correspondences and Endomorphisms}
\label{sec:correspondences}

To give a concrete representation for endomorphisms of $\Jac{\mathcal{C}}$,
we use \emph{correspondences}:
that is, divisors on the surface $\XxX{\family{C}}$.
Suppose that $\family{R}$ is a curve on $\XxX{\family{C}}$,
and
let $\pi_1: \family{R} \to \family{C}$ and $\pi_2: \family{R} \to \family{C}$
be the restrictions to $\family{R}$
of the natural projections from $\XxX{\family{C}}$
onto its first and second factors.
We have a pullback homomorphism
\(
    (\pi_1)^*: \Pic{\family{C}} \to \Pic{\family{R}}
\),
defined by
\[
    (\pi_1)^*\Big(\Big[
        \sum_{P \in \family{C}(\overline{\mathbb{F}}_{q})}\!\!\! n_P P\
    \Big]\Big)
    =
    \Big[
        \sum_{P \in \family{C}(\overline{\mathbb{F}}_{q})}\!\!\! n_P\!\!\!
        \sum_{Q \in \pi_{1}^{-1}(P)}\!\!\! Q\
    \Big]
    ,
\]
where the preimages $Q$ are counted with the appropriate multiplicities.
(A standard moving lemma shows that
we can always choose divisor class representatives
so that each $\pi^{-1}(P)$ is zero-dimensional.)
We also have a pushforward homomorphism
\(
    (\pi_2)_*: \Pic{\family{R}} \to \Pic{\family{C}}
\),
defined by
\[
    (\pi_2)_*\Big(\Big[
        \sum_{Q \in \family{R}(\overline{\mathbb{F}}_{q})}\!\!\! n_Q Q\
    \Big]\Big)
    =
    \Big[ \sum_{Q \in \family{R}(\overline{\mathbb{F}}_{q})}\!\!\! n_Q \pi_2(Q)\  \Big]
    .
\]
Note that $(\pi_1)^*$ maps $\Pic[n]{\family{C}}$
into $\Pic[(n\deg\pi_1)]{\family{R}}$
and $(\pi_2)_*$ maps $\Pic[n]{\family{R}}$
into $\Pic[n]{\family{C}}$
for all $n$.
Hence $(\pi_2)_*\circ(\pi_1)^*$
maps $\Pic[0]{\family{C}}$ into
$\Pic[0]{\family{C}}$,
so we have an \emph{induced endomorphism}
\[
    \phi = (\pi_2)_*\circ(\pi_1)^* : \Jac{\family{C}} \to \Jac{\family{C}}
    .
\]

We write $x_1,y_1$ and $x_2,y_2$ for the coordinates on the first and second
factors of $\XxX{\family{C}}$, respectively
(so $\pi_i(x_1,y_1,x_2,y_2) = (x_i,y_i)$).
In our examples,
the correspondence
$\family{R}$
will be defined by two equations:
\[
    \family{R}
    =
    \variety{A(x_1,x_2),B(x_1,y_1,x_2,y_2)}
    .
\]
On the level of divisors,
the image of a generic point $P = (x_P,y_P)$ of $\family{C}$
(that is, a generic prime divisor)
under the endomorphism
\(\phi\)
is given by
\[
    \phi:
    (x_P,y_P)
    \longmapsto
    \variety{A(x_P,x),B(x_P,y_P,x,y)}
    .
\]
Using
the relations $y_P^2 = f(x_P)$ and $y^2 = f(x)$
(and the fact that correspondences cut out by principal ideals
induce the zero homomorphism),
we can easily replace $A$ and $B$ with
Cantor-reducible generators
to
derive the Mumford representation of $\phi(P)$,
and thus the $\phi$-division polynomials.

\subsection{A $1$-dimensional Family with RM by $\mathbb{Z}[\big(1+\sqrt{5}\big)/2]$}
\label{sec:CTfamily}

\newcommand{\TTV}[1]{\ensuremath{{#1}_{\mathrm{T}}}}

Let $t$ be a free parameter,
and suppose that $q$ is not a power of $5$.
Let $\TTV{\family{C}}$ be the family of curves of genus $2$ over $\mathbb{F}_{q}$
considered by Tautz, Top, and Verberkmoes
in~\cite[Example 3.5]{Tautz--Top--Verberkmoes},
defined by
\[
    \TTV{\family{C}}: y^2 = x^5 - 5x^3 + 5x + t .
\]
Let $\tau_5 = \zeta_5 + \zeta_5^{-1}$,
where $\zeta_5$ is a $5$th root of unity in $\overline{\mathbb{F}}_{q}$.
Let
$\TTV{\phi}$
be the endomorphism induced by
the (constant) family of
correspondences
\[
    \TTV{\family{R}}
    =
    \variety{ x_1^2 + x_2^2 - \tau_5 x_1x_2 + \tau_5^2 - 4 , y_1 - y_2 }
    \subset \XxX{\TTV{\family{C}}}
    .
\]
(Note that \(\TTV{\family{R}}\) and $\TTV{\phi}$
are defined over $\mathbb{F}_{q}(\tau_5)$,
which is equal to $\mathbb{F}_{q}$
if and only if $q \not\equiv\pm2\bmod5$.)
The family $\TTV{\family{C}}$ has an unique point $P_\infty$ at
infinity,
which we can use to define an embedding
\[
    P = (x_P,y_P)
    \longmapsto
    D_P := [(P) - (P_\infty)]
    \leftrightarrow
    (x - x_P, y - y_P)
\]
of $\TTV{\family{C}}$ in $\Jac{\TTV{\family{C}}}$.
With respect to this embedding,
the $\TTV{\phi}$-division polynomials are
\[
    d_2 = 1 ,
    \quad
    d_1 = -\tau_5 x ,
    \quad
    d_0 = x^2 + \tau_5^2 - 4 ,
    \quad
    e_2 = 1,
    \quad
    e_1 = 0,
    \quad
    e_0 = 1.
\]

\begin{proposition}
\label{proposition:TTV}
    The minimal polynomial of \(\TTV{\phi}\)
    is \(T^2 + T - 1\):
    that is, \(\TTV{\phi}\)
    acts as multiplication by $-(1 + \sqrt{5})/2$
    on~\(\Jac{\TTV{\family{C}}}\).
    A prime \(\ell\)
    splits into two principal ideals in \(\mathbb{Z}[\TTV{\phi}]\)
    if and only if \(\ell \equiv \pm1\bmod 5\).
\end{proposition}
\begin{proof}
    The first claim is proven
    in~\cite[\S3.5]{Tautz--Top--Verberkmoes}.
    More directly,
    if \(P\) and \(Q\)
    are generic points of \(\TTV{\family{C}}\),
    then on the level of divisors we find
    \[
        (\TTV{\phi}^2 + \TTV{\phi})((P) - (Q))
        =
        (P) - (Q) + \mathrm{div}\left(\frac{y - y(P)}{y - y(Q)}\right).
    \]
    Hence \(\mathbb{Z}[\TTV{\phi}]\)
    is isomorphic to the ring of integers of \(\mathbb{Q}(\sqrt{5})\).
    The primes~\(\ell\) splitting in \(\mathbb{Q}(\sqrt{5})\)
    are precisely those congruent to \(\pm 1\) modulo \(5\);
    and \(\mathbb{Q}(\sqrt{5})\) has class number \(1\),
    so the primes over \(\ell\) are principal.
    \qed
\end{proof}

The Igusa invariants of $\TTV{\family{C}}$,
viewed as a point in weighted projective space, are
\( ( 140 : 550 : 20(32t^2 - 3) : 25(896t^2 - 3109) : 64(t^2-4)^2) \);
in particular,
$\TTV{\family{C}}$
has a one-dimensional image in the moduli space of curves of genus~$2$.
The Jacobian of the curve with the same defining equation over $\mathbb{Q}(t)$
is absolutely simple (cf.~\cite[Remark 15]{Kohel--Smith}).

\subsection{A $2$-dimensional Family with RM by $\mathbb{Z}[\big(1+\sqrt{5}\big)/2]$}
\label{sec:MestreFive}

\newcommand{\MestreFive}[1]{\ensuremath{{#1}_{\mathrm{H}}}}

Let $s$ and $t$ be free parameters,
and consider the family of curves
\( \MestreFive{\family{C}} : y^2 = \MestreFive{F}(x) \),
where
\[
    \MestreFive{F}(x)
    =
    sx^5 - (2s + t)x^4 + (s^2 + 3s + 2t - 1)x^3 - (3s + t - 3)x^2 + (s - 3)x + 1
    .
\]
This family is essentially due to Humbert;
it is equal to the family of Mestre~\cite[\S2.1]{Mestre}
with \( (U,T) = (s,t) \),
and the family of Wilson~\cite[Proposition 3.4.1]{Wilson}
with \( (A,B) = (s,-t-3s+3) \).
The family has a full $2$-dimensional image
in the moduli space of genus $2$ curves.

Let $\MestreFive{\family{R}}$ be the family of correspondences
on \( \XxX{\MestreFive{\family{C}}} \)
defined by
\[
    \MestreFive{\family{R}}
    =
    \variety{ x_1^2x_2^2 + s(s-1)x_1x_2 - s^2(x_1 - x_2) + s^2 , y_1 - y_2 }
    ;
\]
let \(\MestreFive{\phi}\)
be the induced endomorphism.
The family $\MestreFive{\family{C}}$ has a
unique point $P_\infty$ at infinity,
which we can use to
define an embedding
\[
    P = (x_P,y_P)
    \longmapsto
    D_P := [(P) - (P_\infty)]
    \leftrightarrow
    (x - x_P, y - y_P)
\]
of $\MestreFive{\family{C}}$ in $\Jac{\MestreFive{\family{C}}}$.
With respect to this embedding,
the \(\MestreFive{\phi}\)-division polynomials
are
\[
    d_2 = x^2,
    \ \
    d_1 = (s^2-s)x + s^2,
    \ \
    d_0 = -s^2x + s^2,
    \ \
    e_2 = 1,
    \ \
    e_1 = 0,
    \ \
    e_0 = 1.
\]
\begin{proposition}
\label{proposition:MestreFive}
    The minimal polynomial of \(\MestreFive{\phi}\)
    is \(T^2 + T - 1\):
    that is, \(\MestreFive{\phi}\)
    acts as multipliction by $-(1 + \sqrt{5})/2$
    on~$\Jac{\MestreFive{\family{C}}}$.
    A prime \(\ell\)
    splits into two principal ideals in \(\mathbb{Z}[\MestreFive{\phi}]\)
    if and only if \(\ell \equiv \pm 1 \bmod 5\).
\end{proposition}
\begin{proof}
    The first assertion is~\cite[Proposition 2]{Mestre}
    with \(n = 5\);
    the rest of the proof is exactly as in
    Proposition~\ref{proposition:TTV}.
    \qed
\end{proof}

\subsection{A $2$-dimensional Family with RM by $\mathbb{Z}[\sqrt{2}]$}
\label{sec:MestreTwo}

\newcommand{\MestreTwo}[1]{\ensuremath{{#1}_{\mathrm{M}}}}

For an example with $\Delta = 8$,
we present a twisted and reparametrized version
of a construction due to Mestre~\cite{Mestre-09}.
Let $s$ and $t$ be free parameters,
let $v(s)$ and $n(s)$ be the rational functions
\[
    v = v(s) := \frac{s^2+2}{s^2-2}
    \quad \text{and}\quad
    n = n(s) := \frac{4s(s^4+4)}{(s^2-2)^3} ,
\]
and let $\MestreTwo{\family{C}}$ be the family of curves
defined by
\[
    \MestreTwo{\family{C}}
    :
    y^2
    =
    \MestreTwo{F}(x)
    :=
    (vx - 1)(x-v)(x^4 - tx^2 + vt - 1)
    .
\]
The family
of correspondences
on \(\XxX{\MestreTwo{\family{C}}}\)
defined by
\[
    \MestreTwo{\family{R}}
    =
    V\left(\begin{array}{l}
        x_1^2x_2^2 - v^2(x_1^2+x_2^2) + 1,
        \\
        y_1y_2-n(x_1^2+x_2^2-t)(x_1x_2-v(x_1+x_2)+1)
    \end{array}\right)
\]
induces an endomorphism
\( \MestreTwo{\phi} \)
of $\Jac{\MestreTwo{\family{C}}}$.

The family $\MestreTwo{\family{C}}$
has two points at infinity, $P_\infty^+$ and $P_\infty^-$.
which are generically only defined over a quadratic extension of
$\mathbb{F}_{q}(s,t)$.
Let $D_\infty = (P_\infty^+) + (P_\infty^-)$
denote the divisor at infinity.
We can use the rational Weierstrass point $P_v = (v,0)$
on $\MestreTwo{\family{C}}$
to define an embedding
\[
    P = (x_P,y_P)
    \longmapsto
    D_P :=
    [ (P) + (P_v) - D_\infty ]
    \leftrightarrow
    \Big((x-x_P)(x - v), y - \frac{y_P}{x_P-v}(x-v)\Big)
\]
of $\MestreTwo{\family{C}}$ in $\Jac{\MestreTwo{\family{C}}}$
(the appropriate composition and reduction algorithms for
divisor class arithmetic on genus 2 curves with an even-degree model,
such as $\Jac{\MestreTwo{\family{C}}}$,
appear in~\cite{Galbraith--Harrison--Mireles-Morales}.)
With respect to this embedding,
the $\MestreTwo{\phi}$-division polynomials are
\[
\begin{array}{r@{\;=\;}l@{\qquad}r@{\;=\;}l}
    d_2  &  x^2 - v^2  ,
    &
    e_2  &  (x^2 - v^2)\MestreTwo{F}(x) ,
    \\
    d_1  &  0 ,
    &
    e_1  &  n(x-v)(x^4 - tx^2 + tv^2 - 1) ,
    \\
    d_0  &  -v^2x^2 + 1 ,
    &
    e_0  &  n(vx - 1)(x^4 - tx^2 + tv^2 - 1)  .
\end{array}
\]

\begin{proposition}
\label{proposition:MestreTwo}
    The minimal polynomial of \(\MestreTwo{\phi}\)
    is \(T^2 - 2\):
    that is,
    \(\MestreTwo{\phi}\) acts as multiplication by $\sqrt{2}$
    on $\Jac{\MestreTwo{\family{C}}}$.
    A prime \(\ell\)
    splits into two principal ideals in \(\mathbb{Z}[\MestreTwo{\phi}]\)
    if and only if \(\ell\equiv\pm1\bmod{8}\).
\end{proposition}
\begin{proof}
    Let \(P\) and \(Q\)
    be generic points of \MestreTwo{\family{C}}.
    An elementary but lengthy calculation shows that
    on the level of divisors,
    \[
        \MestreTwo{\phi}^2((P) - (Q))
        =
        2(P)-2(Q) + \mathrm{div}\left(\frac{x+x(P)}{x+x(Q)}\right)
        ,
    \]
    so
    \(\MestreTwo{\phi}^2([D]) = 2[D]\) for all \([D]\) in
    \(\Pic[0]{\MestreTwo{\family{C}}}\).
    Hence \(\MestreTwo{\phi}^2 = [2]\),
    and $\mathbb{Z}[\MestreTwo{\phi}]$ is isomorphic to
    the maximal order of $\mathbb{Q}(\sqrt{2})$.
    The primes \(\ell\) splitting in $\mathbb{Q}(\sqrt{2})$
    are precisely those congruent to \(\pm 1\) modulo \(8\);
    further, $\mathbb{Q}(\sqrt{2})$ has class number 1,
    so the primes over \(\ell\) are principal.
    \qed
\end{proof}
\begin{remark}
    As noted above,
    this construction is a twisted reparametrization
    of a family of isogenies described by
    Mestre in~\cite[\S2.1]{Mestre-09}.
    Let \(a_1\) and \(a_2\)
    be the roots of $T^2 - tT + v^2t-1$ in $\overline{\mathbb{F}_{q}(v,t)}$.
    Mestre's curves \(C'\) and \(C\)
    are equal
    (over \(\mathbb{F}_{q}(v,a_1,a_2)\))
    to
    our \(\MestreTwo{\family{C}}\)
    and its quadratic twist by
    \(A = 2(v^2-1)(v^2+1)^2 = (2n)^2 \),
    respectively.
    We may specialize the proofs in~\cite{Mestre-09}
    to show that $\MestreTwo{\family{C}}$
    has a two-dimensional image in the moduli space of curves of genus $2$,
    and that the Jacobian of the curve with the same defining equation over $\mathbb{Q}(s,t)$
    is absolutely simple.
    Constructions of curves with RM by \(\mathbb{Z}[\sqrt{2}]\)
    are further investigated in Bending's thesis~\cite{Bending}.
\end{remark}

\begin{remark}
    The algorithms described here should be readily adaptable
    to work with Kummer surfaces instead of Jacobians.
    In the notation of~\cite{Gaudry-theta},
    the Kummers with parameters $(a,b,c,d)$
    satisfying $b^2 = a^2-c^2-d^2$
    have RM by $\mathbb{Z}[\sqrt{2}]$,
    which can be made explicit as follows:
    the doubling algorithm decomposes into two identical steps,
    since $(A:B:C:D) = (a:b:c:d)$,
    and the components after one step are
    the coordinates of a Kummer point.
    The step therefore defines an efficiently computable endomorphism
    which squares to give multiplication by 2.
\end{remark}

\section{Numerical Experiments}

We implemented our algorithm in C++ using the NTL library.
For non-critical steps, including computations in quadratic fields, we
used Magma for simplicity. With this implementation,
the determination of $\chi(T)$ for a curve over a 128-bit prime field
takes approximately 3 hours on one core of a Core2 processor at 2.83 GHz.
This provides a proof of concept rather than an optimized implementation.

\subsection{Cryptographic Curve Generation}

When looking for a cryptographic curve, we used an early-abort
strategy, where we switch to another curve as soon as either the
order of the Jacobian order or its twist can not be prime.
Using our adapted version of Schoof algorithm, we guarantee that
the group orders are not divisible by any prime that splits in the real
field up to the CRT bound used.

In fact, any prime that divides the group order of a curve having RM
by the maximal order of $\mathbb{Q}(\sqrt{\Delta})$ must either be a split (or
ramified) prime, or divide it with multiplicity 2.
As a consequence, the early abort strategy works much better than in
the classical Schoof algorithm, because, it suffices to test half the
number of primes up to our CRT bound.

We ran a search for a secure curve over a prime field of 128 bits, using
a CRT bound of 131.
Our series of computations frequently aborted early, and resulted in 245
curves for which $\chi(T)$ was fully determined, and for which neither
the group order nor its twist was divisible by a prime less than 131.
Considering these twists, this provided 490 group orders, of which 27 were
prime, and therefore
suitable for cryptographic use.
We give here the data for one of these curves, that was furthermore
twist-secure: both the Jacobian and the twist Jacobian order are prime.

Let $\mathcal{C}/\mathbb{F}_q$, where $q=2^{128}+573$, be the curve in the family
$\TTV{\family{C}}$ of \S\ref{sec:CTfamily} specialized to
$t=75146620714142230387068843744286456025$.  The characteristic
polynomial $\chi(T)$ is determined by
$$
(s_1,s_2) = (-26279773936397091867,\;
-90827064182152428161138708787412643439),
$$
giving prime group orders for the Jacobian:
$$
115792089237316195432513528685912298808995809621534164533135283195301868637471,
$$
and for its twist:
$$
115792089237316195414628441331463517678650820031857370801365706066289379517451.
$$
We note that correctness of the orders is easily verified on
random points in the Jacobians.

\subsection{A Kilobit Jacobian}

Let $q$ be the prime $2^{512}+1273$,
and consider the curve over $\mathbb{F}_{q}$ from the family
$\TTV{\family{C}}$ of \S\ref{sec:CTfamily}
specialized at
\[
    \begin{array}{rl}
    t = &
    2908566633378727243799826112991980174977453300368095776223\\ &
    2569868073752702720144714779198828456042697008202708167215\\ &
    32434975921085316560590832659122351278 .
    \end{array}
\]
This value of $t$ was randomly chosen, and carries no special structure.
We computed the values of the pair $(s_1\bmod\ell,n\bmod\ell)$ for this curve
for each split prime $\ell$ up to $419$; this was enough to
uniquely determine the true value of $(s_1, n)$ using the Chinese Remainder
Theorem.
The numerical data for the curve follows:
\[
    \begin{array}{r@{\;}c@{\;}l}
    \Delta & = & 5 \\
    s_1 & = &
    -10535684568225216385772683270554282199378670073368228748\\ & &
    7810402851346035223080\\
    n & = &
    -37786020778198256317368570028183842800473749792142072230\\ & &
    993549001035093288492\\
    s_2 & = & (s_1^2 - n^2\Delta)/4 \\
        & = &
    990287025215436155679872249605061232893936642355960654938\\ & &
    008045777052233348340624693986425546428828954551752076384\\ & &
    428888704295617466043679591527916629020\\
    \end{array}
\]
The order of the Jacobian is therefore
\[
    \begin{array}{r@{\;}c@{\;}l}
    N & = & (1+q)^2 - s_1(1+q) + s_2\\
        & = &
    179769313486231590772930519078902473361797697894230657273\\ & &
    430081157732675805502375737059489561441845417204171807809\\ & &
    294449627634528012273648053238189262589020748518180898888\\ & &
    687577372373289203253158846463934629657544938945248034686\\ & &
    681123456817063106485440844869387396665859422186636442258\\ & &
    712684177900105119005520.
    \end{array}
\]
The total runtime for this computation was about 80 days on a single core
of a Core 2 clocked at 2.83 GHz. In practice, we use the inherent
parallelism of the algorithm, running one prime~$\ell$ on each available core.

We did not
compute the characteristic polynomial modulo small prime powers
(as in~\cite{GaSc10}),
nor did we use BSGS to
deduce the result from partial modular information
as in \S\ref{sec:search-space}
(indeed, we were more
interested in measuring the behaviour of our algorithm for large values
of~$\ell$).
These improvements with an exponential-complexity
nature bring much less than in the classical point
counting algorithms, since they have to be balanced with a
polynomial-time algorithm with a lower degree.
For this example, we
estimate that BSGS and small prime powers could have saved a factor
of about 2 in the total runtime.

\subsection{Degrees of Division Polynomials}

For each prime $\ell$ splitting in $\mathbb{Z}[\TTV{\phi}]$,
we report the degree of the $\alpha$-division polynomial $d_2$
(where $\alpha$ is the endomorphism of norm $\ell$ that was used).
By Lemma~\ref{lemma:generator-reduction},
$\deg(d_2)$ is in $O(\ell)$;
the table below gives the ratio $\deg(d_2)/\ell$,
thus measuring the hidden constant in the $O()$ notation.
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c||}
\hline $\ell$ &
11 & 19 & 29 & 31 & 41 & 59 & 61 & 71 & 79 & 89 & 101 & 109 & 131 \\
\hline $\deg d_2 / \ell$ &
1.82 & 2.05 & 2.07 & 1.94 & 2.05 & 2.10 & 1.97 & 2.03 & 2.01 & 2.02 &
1.98 & 2.02 & 2.02 \\
\hline
\hline $\ell$ &
139 & 149 & 151 & 179 & 181 & 191 & 199 & 211 & 229 & 239 & 241 & 251 &
269 \\
\hline $\deg d_2 / \ell$ &
2.12 & 2.04 & 1.99 & 2.00 & 2.01 & 2.09 & 2.21 & 1.99 & 2.18 & 2.01 &
2.05 & 2.07 & 2.17 \\
\hline
\hline $\ell$ &
271 & 281 & 311 & 331 & 349 & 359 & 379 & 389 & 401 & 409 & 419 & & \\
\hline $\deg d_2 / \ell$ &
2.01 & 1.99 & 2.11 & 2.12 & 2.13 & 2.02 & 2.00 & 2.16 & 2.03 & 2.10 &
2.00 & & \\
\hline
\end{tabular}
\end{center}
We have
$\deg(d_1) = \deg(d_2)+1$ and $\deg(d_0) = \deg(d_2)+2$.
All of these degrees depend only on the curve family $\TTV{\family{C}}$,
and not on the individual curve chosen.

redpajama_set_name: RedPajamaArXiv


Three IU students participated in the First Midwest Korean Speech Contest. Shuyao Wang won first place in the intermediate level.
IKS held its Korean Speech Contest on March 2nd. Fourteen students participated. Winners were chosen from Beginner, Intermediate, and Advanced Levels.
IKS showcased the films of director Ryoo Seung-wan at Indiana University and our partner universities. Noted film scholars Darcy Paquet, Kyu Hyun Kim and Molly Kim introduced the films, and Director Ryoo joined the discussion via teleconference.
Participants of the first GW-IU Undergraduate Research Exchange Program have been selected and started research on their projects. These five outstanding students will produce a research paper and travel to George Washington University for a conference in April 2019 to present their research alongside students of GW. Congratulations to all of the participants!
Keith Seidel, Assistant Director of the Institute for Korean Studies won second prize in the 2018 Global Korean Literature Translation Award competition for his translation of the short story, Bukchon, by Lee Hye-kyung.
The Institutes for Korean Studies at the George Washington University and Indiana University Bloomington invite students to apply for GW-IU Undergraduate Research Exchange Program. We are seeking to select students who are interested in conducting research about Korea. All students receive mentoring from faculty at the Institute for Korean Studies.
Roald Maliangkay IKS Scholar-in-Residence visits IU partner institutions.
Read about IU President Michael McRobbie's trip to Korea with IKS Director Seung-kyung Kim.


ACE is a member-led social justice organization that develops and mobilizes undocumented working youth and adults, students, and LGBTQ individuals to strategically take ownership and responsibility to advance economic, social, and racial justice. By building power through leadership development, Citizenship, civic engagement, advocacy and education, we are creating a more inclusive and just standard of equality in the state of Arizona. Income equality, protection of public education, immigrant rights, and health care are just a few of ACE's priorities in creating a better Arizona for all.


text:
2016 year in review: Motorola's resurgence
May 14, 2017 by palm-communications | Categories: Uncategorized
Motorola have always been a brand we have looked up to, in our eyes they produce some of the best equipment on the market, sometimes they don't sell as well as they should do. The business has been split and sold several times over the last year, but they are now on the rise and business is going well, as this article shows.
2014 saw Motorola's ownership change hands from the west to the east. Lenovo acquired the company off Google on January 29, 2014 but it was not until 2016 that the fruits of Lenovo's ownership started showing up.
The year started off with Motorola in a slightly vulnerable position with the relative failure of both the Moto X Style and Moto X Play. The Moto X line was fading and even the third generation Moto G had failed to impress.
These first devices under Lenovo's ownership however, had been in the pipeline much before Lenovo took over and it was not until the Moto G4 and the Moto Z in 2016 that we saw what the new Motorola could deliver.
Moto G4 series: Ushering in a renaissance
The Moto G4 Plus was one of two variants of Motorola's fourth generation Moto G, the firm's bestselling smartphone range ever. This was the first time Motorola (now owned by Lenovo) launched more than one smartphone in the G range, with the Moto G4, Moto G4 Play and the Moto G4 Plus.
At a starting price of Rs 13,499, the Moto G4 Plus made for a compelling buy, and continued the G series of smartphone's tradition of providing good smartphones at an affordable price. With a superb display, a fast and accurate fingerprint sensor, stock android and great performance, it ticked all the right boxes for a mid-range device.
In comparison to the regular Moto G4, the Moto G4 Plus featured an improved 16MP rear camera with phase auto detection, laser autofocus and a dual LED Flash and also came with a fingerprint sensor.
Motorola also released the Moto G4 Play which was the cheapest device in the G4 lineup at Rs 8,999 and packed a 5-inch 720p HD display, a 2,800mAh battery, 2GB of RAM and 16GB of expandable internal storage.
The Moto G4, G4 Plus and G4 Play were critical as well as commercial hits and announced the comeback of Motorola in the smartphone game. The Plus in particular, presented a fantastic blend of features and affordability that saw it shoot up the sales charts.
Moto E3 Power: The odd one out
Lenovo also unveiled the Moto E3 Power in India which was a more powerful version of the third generation Moto E3. In a surprising move, the company decided against releasing the regular Moto E3 in the country.
The Moto E3 Power came with a massive 3,500mAh battery, 2GB of RAM, a 5-inch HD display and nearly stock Android Marshmallow.
At Rs 7,999, the Moto E3 Power found itself in as odd situation with the much more capable Moto G4 Play priced at just a thousand rupees more.
The attack of the Modular smartphones
Motorola then cemented its position in the smartphone world by releasing the striking Moto Z, the company's most exciting smartphone in years.
The Moto Z came packed to the gills with a Qualcomm Snapdragon 820 SoC, 4GB of RAM, a 13MP rear camera with OIS and 4K recording, a 5MP front shooter and a 2,600mAh battery along with TurboCharging support.
The 'World's thinnest premium smartphone' came with a 5.5-inch QuadHD display protected by corning gorilla glass, a sleek and suave metal/glass body and unlimited feature expansion through the Moto Mods.
The distinguishing feature of the Moto Z were the 'Moto Mods': snap-on accessories that could be attached to the back of smartphone through magnets in order to increase its functionality.
Alongside the flagship Moto Z, Motorola also launched its younger brother, the Moto Z Play which came with a 5.5-inch 1080p Super AMOLED display, a downgrade from the QuadHD resolution of the Moto Z and the largest battery Motorola ever put in any of its smartphones. Just like the Moto Z, the Moto Z Play also supported the innovative Moto Mods.
The Moto Z and Moto Z Play helped bring Motorola back into the spotlight. The Moto Mods in particular were greatly appreciated and were hailed as one of the best implementations of the modular concept in recent years.
The stunning all-metal Moto M
The end of the year saw Motorola launching the stunning all-metal Moto M in India.
The Moto M's full metal unibody design with antenna bands on the top and bottom edges was a complete departure from the design language of previous Motorola smartphones and was again an indication of the company's new ownership.
This is what Sudhin Mathur, Executive Director, Lenovo Mobile Business Group, India had to say about the company's performance in 2016:
"The Moto G franchise continues to be much loved and we witnessed an extremely high conversion from early Moto G buyers opting for the new Moto G 4th Generation. But, our real game changer and technological breakthrough was the Moto Z and Moto Mods series that redefined the evolutionary progress of the smartphone industry. The Moto Z and Moto Mods system is designed to provide connected, intelligent and mobile consumer experiences in a seamless fashion and the power to transform your (Moto Z) smartphone in a snap is revolutionary. We started with four Moto Mods and are continuously working with multiple partners to develop more Mods for smartphone users in 2017."
2017 will be a crucial year for the company as it prepares to build upon the success of the G4 and Z range. It is pivotal for Lenovo to make sure that it retains the essence of the company while at the same time push new boundaries of design and innovation.
£4 billion emergency radio system 'not yet proven'
March 28, 2017 by palm-communications | Categories: Uncategorized
We have been very vocal against the new ESN network, Tetra is proven and works very well, the benefits to moving over to a 4G network are attractive, but will it stand-up to a major incident? Will the network be robust enough when there are thousands of communications in a located area? These concerns have now been picked up by a commons committee, read more below….
An inquiry has revealed deep concerns about the coverage and contracting of a new £4 billion national emergency radio system.
A Commons' Public Accounts Committee report released this month criticised the Home Office for its handling of the proposed the Emergency Services Network, or ESN.
Plans to deploy the "not yet proven" emergency radio system by December 2019 "would not be met", the committee said. The committee also criticised the Home Office for mishandling contracts talks for ESN and failing to plan for delays, that could cost nearly £500 million alone.
"Good communications can make the difference between life and death for both emergency services personnel and the public but the technology ESN will rely on is not yet proven."
Across the UK, 105 ambulance, fire and police services are expected to switch from their existing Airwave Solutions radio system to ESN by December 2019.
Unlike the ageing Airwave network, ESN will operate on an existing retail 4G network rather than a dedicated emergency radio network.
However, the committee said forcing emergency services to share a network with the public had not been attempted at scale.
The approach relied on much improved network coverage across the UK, including on the London Underground, and new technology to prioritise emergency services over other network users.
"Bringing together all the different elements to form an end-to-end system and scaling up these solutions and testing them adequately will be very challenging."
The government is expected to spend £1.2 billion developing ESN, £1.4 billion running down Airwave, and further £2.6 billion operating ESN until 2032.
The contract with Airwaves, which was bought by Motorola last year, expires in December 2019. The committee said extending this contract, which will almost certainly be necessary given expected delays, will cost an additional £475 million a year.
In 2015, Motorola and EE won the user services and networks contracts respectively for ESN.
The committee also criticised the Home Office for not maintaining "competitive pressure" while awarding the contracts and leaving the winning bidders in a "very strong position" when the contract comes up for renewal in 2023.
The committee recommended the Home Officer test the new network coverage rigorously, improve its tendering, budget and plan for an Airwave contract extension and reassess its timeline for switching to the new system.
"It must take responsibility for convincing services to switch to ESN but also be clear at what point it will mandate the switchover."
The Home Office was told to report back to the committee by September this year.
How To To Select A Walkie Talkie Headset For Your Bike
Motorcycle helmet intercoms have recently gained lots of popularity for the safety and convenience they offer. They have lots of enhanced features which help riders focus on driving. That being so, you should know that being able to choose and use the right type of motorcycle helmet intercom is extremely important as it makes it easy for riders to perform all kinds of actions and do all kinds of things without any fear of losing control of their motorcycle. In this article, we're going to be talking about the best features to look for in a motorcycle helmet intercom, and the different types of motorcycle intercoms available in the market;
Here are the features to look for when looking for a walkie talkie headset for your motorcycle helmet:
Well, riding in a motorcycle usually makes the rider quite vulnerable to various kinds of road and environmental factors. This includes dirt, dust, rain, humidity, and all types of things which one can possibly encounter. Because of this, you should consider getting a completely weatherproof motorcycle helmet intercom. Fortunately, most of the motorcycle intercoms in the market today are weatherproof, water resistant or waterproof. For the best protection from the elements, consider choosing a weatherproof or waterproof intercom, instead of the water resistant ones; this ensures that despite any hazards and rain, your system will be safe, and still work efficiently.
You should also consider getting a system that has a headset speaker for both ears or one ear. This particular factor depends on personal preference as some may find it more convenient to use a one ear headset, while others may prefer both years as some riders like hearing sound in both of their ears. That being so, you should know that installation and moving of the intercom to a different helmet is much easier for the systems which have only one ear.
Another important factor to consider is voice activation. Many systems have the voice activation feature which keeps the headset(s) quiet when no one is talking. The voice activation feature also has the ability to get disabled and a push to talk switch feature can be used instead. Apart from that, sound quality and noise cancellation is something you need to put into consideration. Many motorcycle intercoms have the noise reduction feature with digital signal processing which helps reduce the noises/sounds they pick up from your microphone; this feature is especially important if you are a fast rider.
For those who like riding with some music playing, you should consider going for the motorcycle intercoms which come with either a built in FM stereo, or an auxiliary stereo input for iPod, a Walkman, MP3, or a satellite radio unit. This type of input can also be used to receive driving directions from voice prompted GPS unit.
There are some motorcycle intercoms which can be mounted in your helmet, on your belt clip, on your bike or even put directly to your ears; this usually depends on just how big or bulky the intercom is. Choosing this feature depends on personal preference. You should choose the one that you'd be most comfortable using.
Last but not least, connectivity for cell phones is another crucial factor to consider when choosing a motorcycle intercom. This feature allows you to access the phone's features while you're on the road. The feature is best paired with hands free operation.
Without a motorcycle intercom, riding can be a very solitary experience. Using an intercom is a great way of clearing your head and putting your thoughts together when you're riding alone. However, if you've a passenger, or you are biking with another rider, sooner or later you'll want to converse with them. A motorcycle helmet intercom will let you do this, and so much more.
That being said, the problem is that there are very many motorcycle intercoms to choose from. And given the fact that motorcycle helmet intercoms need to work in extremely difficult environments, choosing the best one can mean all the difference between enjoying your ride and hating it. Below, we are going to give you the different types of motorcycle helmet intercoms available, to help you make the best choice for your particular needs;
Acoustic Motorcycle Intercom
This is the most basic form of the motorcycle helmet intercoms. With this type of intercom, there are no electronics involved since it uses hollow tubes which have rubber tips that are normally inserted into the rider's ear. A different tube is used as a mouthpiece for talking into, and they both connect through a junction box. This system simply uses the hollow tubes which the voices travel through.
One of the main benefits of a walkie talkie headset is the fact that you'll find no batteries to mess with; this makes them highly reliable. However, there is no amplification which means that there is no way of regulating or adjusting the volume or filtering the wind noise. therefore at high speeds, it'll likely be much harder to listen to. Another issue with this system is the fact that many riders tend to realize that the ear plugs are uncomfortable in their ears for an extended period of time. These acoustic motorcycle intercoms only work with driver to passenger and not bike-to-bike.
Wireless Intercom Technology
This is a most complex and technologically advanced system as it utilizes different forms of radio technologies namely FM, GMRS, FRS and Bluetooth.
FM (abbreviation for Frequency Modulation) is widely used because it's very efficient when it comes to transmitting clear sound, however, if it's used by driver to driver, its' performance isn't good if they're too far apart. It is quite similar to the FM radio you normally listen to, however for the motorcycle intercom, a much narrower frequency is usually used. The FM intercoms work best when there aren't any kind of obstructions (like hills) between the receiver and the transmitter.
If long range is the most important feature, then the GMRS Walkie talkie headsets will offer a much better performance. The FRS (abbreviation for Family Radio Service) and GMRS (abbreviation for General Mobile Radio Service) are the modern equivalents to old walkie talkies you might have used during your childhood days. The FRS intercoms typically have a maximum range of 2 miles provided there are minimal obstructions in between, while the GRMS intercoms can effectively communicate up to several miles. Just Like the FM, these two are public frequencies which means other people can get to hear your conversations, and vice versa. In some heavily populated areas these FRS/GRMS radios are heavily used, while out on the open road you should enjoy fairly private conversations.
One great thing about using the FRS or GMRS walkie talkie headset is that you can visit Headsetonline and purchase a walkie talkie headset and handheld radio which you can use to contact these units. In case someone is following you in a car, or they have a wired intercom system which allows them connect to an FRS or GMRS handheld radio, they will be able to communicate with you. The only downside is that you'll find countless of these radios in the heavily populated areas and you'll end up picking up lots of other transmissions.
3 Types Of Security Earpieces With Mics
March 9, 2017 by palm-communications | Categories: Uncategorized
If you are looking for a security earpiece with a mic, then you will need to know the varieties available out there. While some types are more expensive than others, what ultimately matters is the quality and durability of what you get at the end. Below is a look at what you get out there:
One wire kit
With this one, there is only a single wire, which emerges from the radio, runs through the PTT and then ends where the earpiece starts. This makes for a simple yet effective look. As for the length of the cable, the one wire kit has a piece that runs between 28 and 34 inches. This means that you have at your disposal a length sufficient to cover the distance between your ears and the waist without any kind of stretching or straining. Of course, the reach of every security earpiece will be determined by the height of the person wearing it. The one wire kit is great for an average height and will work for anyone 6 feet and below.
Most one wire kits come in the original D and G shapes. There are some fancier designs out there as well if that's what you are looking for.
Two wire kits
As the name suggests, there are two wires involved in this scenario. One runs to the Push to Talk (PTT) button. The other runs up to the earpiece, making for a good looking dual connection. For the purposes of discretion, you are allowed to wear this cable partially disguised within your clothing. One wire will emerge from the radio, rising up your back to the ear in a way that keeps you comfortable. The other cable runs from the radio, up the length of your hands and terminates at the cuffs if you are wearing a long-sleeved shirt or sweater. In terms of length, the two-wire kit is essentially the same as its one wire counterpart, with a reach of 30 to 34 inches. This accounts strictly for the length of each individual wire, and allows the unit to comfortably cover the areas between your waist and the ears. Two wire kits commonly come in the form of an acoustic tube that many who know a little about surveillance will be able to understand.
3 Wire kits
Here, you have three wires coming off the radio. The first wire will terminate where the earpiece is built. The second will end where the Push to Talk button is located. The last will end at a connection with the mic. As with the two wire kits, this one is worn under ordinary clothing, with a cable for the mic, earpiece and PTT button. There is really no standard length for all the three wires and there is no guarantee that all of them will be equal in length, but there is a sense of flexibility in the way you get to use the piece. Always try on sample pieces before making a purchase at a store. Over the internet purchases are trickier but then the measurements will be highlighted long before you order.
Understanding the functionality of PTT technology
Push to Talk is a cutting-edge technology that allows for direct communication between parties at agreed-upon frequencies and distances. The greatest thing about PTT is that it switches communications from duplex to half duplex. This means people do not talk over each other but get to alternate between speaking and listening. PTT is able to loop in two or more speakers at an instance of communication, allowing for conference-like types of engagements between participants. This streamlines communication. Most enterprises prefer this approach to communication because there are no limitations in terms of allotted minutes. As such, there is absolutely no need to stay within the confines of a data plan, which would be both expensive, inconvenient and rigid.
There is no such thing as a right security earpiece. What works for you may not work for all other parties across the board. While your budget matters a lot, you are looking for something that works optimally and stands the test of time. The three types mentioned above are alright if you are looking for something that works all the time. Remember, prices will vary across brands and models.
I Bought a Two-Way Radio With a Range of 25 Miles…Why Won't It Work?
Sorry, but you've been had. Although many manufacturers boast that their radios can reach amazing distances, this is, in almost every instance we've encountered, a fallacy.
How is this legal, you may ask?
Essentially, your radio quite probably could work over a range of 25 miles, but that is a theoretical estimate, working on the assumption that the myriad variables that affect two-way radio signal (such as atmospheric conditions, topography, objects in the way and etc) are simply not in effect.
All of them. At the exact same time.
So, assuming that you used your two-way radio in a vacuum, where weather didn't exist and no obstacles, man-made or otherwise, were present, you would be able to communicate with someone else who was further away in that impossible vacuum, maybe even 25 miles away, but otherwise? Forget it.
The fact is that the average two-way radio has a range of between one and two miles and not much more (maybe three, but we're not making any promises). CB radio fares significantly better, largely because it makes use of large aerials. Now, Signal-boosting equipment can be used to improve your two-way's performance (for example, repeaters), but such equipment is expensive and hard to obtain for legal reasons.
There are, however, a few factors that can have an affect on your radio's range. The frequency being used, the power output, the size of the antenna, the complexity of the signal being sent, signal interference, background noise and (as we wrote earlier) objects in the way are all factors that can improve (or hamper) your efforts to get your signal to reach as far as possible.
So, talking on your radio whilst in the car will have a deleterious affect on your signal, as will deliberately walking through wooded areas or places with a lot of rocks/mountains if you can take an easier path.
However, a larger antenna (if you're tech orientated, the antenna can be replaced with a better one – although this should only be attempted if you are
a) Sure about licensing laws
b) Tech savvy enough to void the warranty and not regret it later, can really add a few hundred meters to a radio's range, as can a switch in frequencies.
Also, your choice of VHF or UHF radio will have an affect as well, a UHF signal, for example, generally penetrates buildings and objects better than a VHF signal, whereas VHF is better for outdoor use where there is a lot of open space to transmit across.
Having said/written that, even in optimum conditions, you are extremely unlikely to transmit over a distance of 25 miles. Sorry.
As an aside, mobile phones don't suffer from this lack of coverage, largely because cell towers are in place that bounce the signal from one to the other and thus carry it across a far larger area, your mobile is still your best bet to break that 25 mile mark, we're afraid.
If you really must use radio communications over long distances, we recommend going to the Website 2 way radio online
The arrival of 5G, cognitive radio and the future of connectivity
We are very excited about 5G, we have already reported on how the UK emergency services are moving over to a LTE network, and inevitably 5G is the next step for better, faster and more capable communications. Â Not planned to be deployed until the next decade, we believe that 5G will allow us to communicate better with our Walkie talkies. The original article can be found here.
With faster and more reliable connections, we look at what the next generation of communications could mean for business
From smart cities to the internet of things (IoT), virtually every aspect of the modern world is becoming closely connected.
The extent to which we rely on our devices and the exchange of information means new systems are needed that not only handle far greater bandwidth, but that are capable of being deployed to cover areas that were previously unreachable.
The potential benefits for business are huge, with faster and more reliable connectivity not only enhancing how firms interact with customers and each other, but also lending itself to greater flexible working among staff.
The arrival of 5G
One development that many industry observers believe could be revolutionary is 5G. Following on from 4G, the fifth-generation mobile network is in its early stages of development and is expected to be rolled out between 2020–25.
Any tech that contributes towards the next phase of mobile connectivity is covered by the term 5G. And although there are still no set standards or specifications, the GSMA – a trade body that represents global mobile operators – has outlined eight key criteria, stipulating minimum requirements for speed, capacity and energy in order for something to be considered 5G.
According to Ofcom, once operational 5G could provide between 10–50 Gbps (gigabit per seconds) in download speeds (as compared to the 5–12 Gbps of 4G), and although most experts expect it to be at the lower end of the range, that would still mean you could download an HD movie in seconds.
But rather than simply being faster than the current 4G, it will also allow more devices to access the web – an essential requirement if the IoT is to take off – meaning it could be transformative for business.
Raj Sivalingam, executive director of telecoms for techUK, the trade association for the tech sector, says: "The potential of the IoT, particularly in the enterprise environment, has been hugely debated but its impact is almost certainly still undervalued.
"Mass deployment across sectors will boost efficiency and safety with pre-emptive fault correction; enable automatic reporting of accidents and allow real-time asset tracking, reducing crime and increasing productivity, to name just a few benefits."
One potential bottleneck for 5G is spectrum availability – or lack of it. Radio frequencies for both 3G and 4G are already overcrowded. The provision of a new bandwidth will require widespread cooperation between operators, manufacturers and governments.
Infrastructure is also an issue, says Sivalingam. "Making the leap to 5G mobile services and getting more fibre into the fixed telecommunications networks will require substantial amounts of investment.
"We need the government and industry stakeholders to work to shift the UK from good levels of connectivity to great levels so that we continue to attract investors and startups, and to foster innovation from within the UK."
One possible solution is cognitive radio. An adaptive radio and network technology, it can sense and respond to its operating environment and automatically tune itself to the best available frequencies, this makes it more reliable in extreme locations where signals are weak, potentially providing dependable, robust connections that are not hampered by interference or geography.
Finland-based KNL Networks has developed a system using the technology that uses short wave radio to transmit internet access to sites in remote locations ranging from oil rigs to polar research stations. KNL Networks CEO Toni Linden says: "We can provide similar connectivity to those from satellites but with a terrestrial radio system. Our radios receive the whole spectrum all the time, so rather than scanning, real-time broadband receiving is going on. Thus we can see and measure everything that's going on in the spectrum and we can maintain the network connectivity that way."
The tech opens up the possibility of providing seamless connectivity anywhere, giving business reliable online access to markets in parts of the world that have otherwise been unreachable. It could also enable media and other companies to broadcast without the need for expensive satellites.
Quantum key distribution
It's not just data transmission, speeds and connectivity that pose challenges in the future, but the safety of that data too. Cybercrime is ranked alongside terrorism as among the most serious threats to the UK [pdf], and with data now the lifeblood of modern business, securing that data is of paramount concern. One technology that could provide the answer is quantum communications.
Conventional encryption relies on sending a decryption key alongside your secret data. The receiver then uses that key to decode your secret information. But problems arise because hackers can also copy this key and steal your data.
Quantum key distribution (QKD) is different because it encodes this key on light particles called photons, and an underlying principle of quantum mechanics means that a hacker trying to read or copy such a key would automatically alter its state, effectively leaving a hacker fingerprint so the sender and receiver know their information security had been breached.
China recently launched a quantum satellite to further research into this technology, with the hope of developing an uncrackable communications network.
In the UK, the Quantum Communications Hub is part of a national network of four hubs led by the universities of Birmingham, Glasgow, Oxford and York. Director Tim Spiller says: "We are developing quantum communications technologies along a number of different directions, notably short-range free space QKD, where the transmitter could be in future mobile phones, and chip-to-chip QKD through optical fibre, where the chips could be in future computers and other devices."
With two thirds of British business falling victim to cybercrime in the past year the need for better encryption is clear.
Several companies currently offer commercial quantum key distribution systems include ID Quantique, MagiQ Technologies, QuintessenceLabs, SeQureNet and Toshiba, although its high cost and limited range means mainly banks and governments are its main users, with mainstream adoption still some way off.
Spiller added: "Certainly it would be desirable to improve the size, weight, power and cost points of current technologies and our work in the hub and elsewhere is addressing all these factors."
Paul Lee, head of technology, media, and telecommunications research at Deloitte, highlighted a number of improvements which he expected to see coming down the line, including improved mobile antennae and base stations, as well as improvements to fixed networks such as G.fast that would enable copper cable to operate at much higher speeds.
"As they get steadily faster, new services emerge to exploit these greater speeds, which then requires the deployment of even faster networks. This tail chasing has been going on for decades and won't stop in 2017."
Software Defined Radio (SDR) Market Forecast By End-use Industry 2014-2020
We are seeing a monumental movement in the radio communication industry, as this very technical article shows the transition from hardware to software within the radio communication industry is just around the corner. With 3G and 4G providing Data and Voice Comms covering large distances, RF communication will find it hard to compete, the simple answer seems to be Tetra, but is that long term? There will always be a need for point to point communications, but larger comms infrastructures could possibly be managed in a different way.
With the evolution of digital electronics the radio market and communication technologies have evolved a lot. Though the concept of software defined radio (SDR) is not new, in the recent years, this market has undergone many changes in terms of technology and uses. SDR is a type of radio communication system where communication is carried out by the use of software on embedded system or personal computer instead of implementing hardware such as filters, amplifiers, mixers, detectors, demodulators and modulators, among others. SDR are capable of transmitting and receiving a wide spectrum of frequency. When the data from a source is converted into digital format, the remaining activities involved in radio communications are carried out with the help of software driven automated functions.
SDR optimizes the tactical information system as embedded software used in SDR helps in the dynamic selection of the communication channel. The number of digital service users is increasing resulting into the improved adoption rate of software defined radio. Public safety, military and commercial use are the three major end-use applications of SDR systems. The demand for SDRs in expected to increase in coming years owing to efficiency and cost effectiveness offered by them. The industry has undergone transformation from analog to digital. Thus, the advance capabilities of digital radio are expected to drive the growth of SDR market. Multiple regulations govern the SDR market and this affects the market growth and trends. For instance, the Federal Communications Commission (FCC) legally created a newer class for equipment of SDRs that had streamlined equipment authorization procedure.
Military modernization programs being carried out by several countries such as South Korea, India, Germany, Japan and the U.S and the interoperability provided by SDR are major driving forces for SDR market. The issues faced in the integration of the various sub systems pose a challenge to the SDR market. Further, the development of software platforms, technologies and tools, which allow flexible specification, design and implementation of radio systems, is another significant challenge. Players in software defined radio market have potential opportunity in technical advancements of SDR technology such as resolving the problem of frequency congestion, wide frequency range (spectrum) and improved broadcasting services in future.
Software defined radio market is segmented on the basis of type, end-user application and geography. On the basis of type of SDR, the market is segmented into ideal software defined radio, baseband software defined radio (BBSDR) and high frequency software defined radio (HFSDR). On the basis of end-user industry, SDR market is segmented into defense industry, telecom industry, manufacturing plants, public safety vendors and personal use. U.S. Canada, Japan, France, Brazil, South Korea, India, Germany and Italy have emerged as the leading countries for software defined radio market.
Some of the key vendors in software defined radio market are BAE Systems PLC, Elbit Systems Ltd., IndraSistemas, L3 Communications Corporation, Raytheon Co., Rohde & Schwarz GmbH & Co KG, Thales Group, Viasat Incorporated, SAAB AB, Rockwell Collins, Northrop Grumman Corp., ITT Corporation, Harris Corporation and Datasoft Corporation, among others.
This research report presents a comprehensive assessment of the market and contains thoughtful insights, facts, historical data and statistically-supported and industry-validated market data and projections with a suitable set of assumptions and methodology. It provides analysis and information by categories such as market segments, regions, product type and distribution channels.
What Is The Best Way To Select The Right Radio Earpiece
When choosing a radio earpiece, there are several factors that should be considered. A radio earpiece should not only aid in communication it should also protect the user's ear against cumulative ear damage that may eventually result in ear loss. Below are the factors that you should consider when buying a radio earpiece;
1) Clarity of communication
The most important reason as to why you have a radio is for clear communication and this is what your radio earpiece should enhance. Although there are several radio earpieces out there , many of them use bone conduction when transmitting the user's speech meaning that they heavily rely on vibrations of one's skull as they talk. This does not help much in ensuring that the communications are clear especially when one is on the move.
You should therefore go for a system whose in-ear microphone does not use bone conduction and this will enhance the sound clarity. Such a system can even transmit speeches when one is whispering and this comes in handy especially when in an environment where secrecy is very crucial.
2) Comfort
It is very important to select a system that you feel comfortable with most importantly when you are to wear it on your head. Note that, you will probably be wearing the gear for long hours and that is why it should be of lightweight and should not in any way interfere with your eye wear or helmet.
Avoid heavy, sweaty and coiled tube earpieces that are very uncomfortable and will cause ear fatigue. Instead, go for a radio earpiece whose microphone is built into the earbud itself. Such earpieces come in various shapes and sizes and can even be customized to fit the specific needs of a user. Note that, military-grade materials are specifically designed to be of lightweight.
Durability is a very important factor that should be considered when choosing a radio earpiece. You obviously don't want to be wasting your time and money going back to look for another earpiece just because the one you chose did not last. This is why it is very important to select a system that is durable and has been tested for rugged use of a soldier or a SWAT officer. Go for one whose manufacturer is experienced in manufacturing earpieces that can withstand water, dirt, shock and even extreme temperatures.
Your radio earpiece should be easy to use because you can't afford to mess up with the push-to-talk or the on & off buttons especially when on the move. Your gear should immediately fit into your actions with minimum effort. Look at the operational and the ergonomic features of the various radio earpieces and make sure that all its features are both of the right sizes and in the right places.
5) Hearing protection
Claims related to hearing loss and its related disabilities is on the rise among police & military veterans and this has led to the need for hearing protection for officers. Note that, hearing loss occurs cumulatively over time and it is irreversible. This is in addition to the fact that it has been associated with cognitive decline and that is why even the minor hearing loss can have a huge impact in the course of time. Select a radio earpiece that not only ensures effective communication, but also the hearing safety of the user.
6) Situational awareness
An earpiece is basically meant to keep you focused and keep your hands free. You should be aware of what is happening in their surrounding and that is why a radio earpiece should allow one to hear sounds that are outside, to stay alert with their surroundings.
In order to have full communications (just like one would have without anything in their ears), it is wise to choose a radio earpiece that has an external microphone. There are systems that even enable you to adjust volume of the external microphone and this ensures that you are aware of the happenings in your surroundings.
7) Modularity & Compatibility
There are several systems that are available out there and you should look for one that fits your requirements. As mentioned above, some of them can be customized to fit an individual user's specific needs so you can never run out of options.
A radio earpiece that has a modular connector is good as you can change it to match even a different radio without having to replace the entire system. Some systems can even go with both earbuds and over-the-ear earpieces so depending on your needs, select the appropriate system.
8) Affordability
Many years ago radio earpieces cost £100 and upwards, these days you can get a D-ring earpiece for less than £15 and an acoustic tube for about £25. Bone conductor earpieces that were previously and expensive piece of technology, can be yours for about £40.
Spy Earpiece: A Micro Earpiece That Will Help You Through Presentations, Interviews, Speeches + More
February 5, 2017 by palm-communications | Categories: Uncategorized
When you think of a spy earpiece, the first thing that comes to mind is inspector gadget or Mission impossible, well it does for us anyway. But there are real world applications for these earpieces are wide. As this article explains, when you need a little help with prompts on a big presentation or you need to receive instructions during a lecture, then a micro earpiece could be the answer.
This device originally developed for covert operations is now made available for the public to use. Each earpiece kit can provide a way for you to transmit and receive audio information without anybody in the room knowing. Whether you want to receive pre-recorded messages or information from another party to assist you during your presentation / interview or speech, the earpiece can be set up with your phone, audio recorder, radio, or MP3 player to send the message to your earpiece , placed in your ear channel so that it is undetectable .. All kits also include a built in microphone so that you can engage in 2 way conversation should you wish
So how does it work?
The key is the inductive transmitter that will transmit audio from a phone / mp3 player to the earpiece. The transmitter itself is available in many forms. For example the transmitter may be included within a neckloop to be worn around the users neck, this may connect to your phone or mp3 player via its earphone socket. Or you may have a Bluetooth are often included in everyday objects such as a pair of glasses, a Pen or even a bluetooth watch. The transmitter acts as the aerial for reception and signal transmitter from phone to earpiece. At the same time, output sound picked up by the tiny microphone attached to the neckloop / pen / glasses is sent through your phone just as if the user is talking directly into it.
How to Use The Spy Earpiece?
Depending on what kind of information you wish to receive the earpiece can be set up to suit. For example during a presentation or speech you may wish to pre-record your speech or presentation on an mp3 player, then play it back to yourself during the presentation / speech. Or simply record a simple prompt for each point you would like to make. You could then connect up your mp3 player to an inductive neckloop included in most earpiece kits, and wear a spy earpiece. So long as the battery is inserted into the earpiece you will hear the audio from your mp3 player in the earpiece.
Alternatively you may prefer to have a team prepped in another room to assist you during your speech. This can be achieved by simply starting a mobile phone conversation with your team just before the speech starts. You would then need to either connect an inductive neckloop to the headphone output of your phone, or pair your phone with a bluetooth induction neckloop / pen / glasses. Insert the earpiece into your ear making sure the battery is inserted correctly. Your team should be able to hear your speech in real time over the phone, and can give you tips in your earpiece along the way. The same may apply in an interview situation, you may wish to have a third party issue you advice during your interview.
Each Inductive transmitter whether it be a neckloop or a bluetooth device like a pen, glasses or bluetooth neckloop, will also include a built in microphone so you can also talk back to your colleagues should you wish during your speech / presentation or interview.
Lets not forget the original intention of the Spy Earpiece which is for security and covert surveillance. The Spy Earpiece excels in these situations where the requirement is for a security operative to communicate covertly.
The key to success is in the careful planning and preparation so that everything runs smooth.
The way I see it, when the challenge is great and the results mean everything, why not try the Spy Earpiece and take the risk out of the equation?
Source -Â https://techfeatured.com/1592/spy-earpiece-a-micro-earpiece-that-will-help-you-through-presentations-interviews-speeches-more
MIT's new method of radio transmission could one day make wireless VR a reality
January 16, 2017 by palm-communications | Categories: Uncategorized
VR is the Buzz word for this year, every technology company clambering to get their headset out on to the market. Much of the market needs to catch-up though, the power of home computing needs to improve and removing the inevitable extra cabling and wires that come with current headsets. Luckily this article is about the future technology of VR headsets, see what we can expect as this technology grows.
If you want to use one of today's major VR headsets, whether the Oculus Rift, the HTC Vive, or the PS VR, you have to accept the fact that there will be an illusion-shattering cable that tethers you to the small supercomputer that's powering your virtual world.
But researchers from MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) may have a solution in MoVr, a wireless virtual reality system. Instead of using Wi-Fi or Bluetooth to transmit data, the research team's MoVR system uses high-frequency millimeter wave radio to stream data from a computer to a headset wirelessly at dramatically faster speeds than traditional technology.
There have been a variety of approaches to solving this problem already. Smartphone-based headsets such as Google's Daydream View and Samsung's Gear VR allow for untethered VR by simply offloading the computational work directly to a phone inside the headset. Or the entire idea of VR backpacks, which allow for a more mobile VR experience by building a computer that's more easily carried. But there are still a lot of limitations to either of these solutions.
THE MOVR PROTOTYPE SIDESTEPS TETHERED VR ISSUES
Latency is the whole reason a wireless solution hasn't worked so far. VR is especially latency-sensitive, along with the huge bandwidth requirements that VR needs to display the level of high-resolution video required for virtual reality to work. But the MIT team claims that the millimeter wave signals can transmit fast enough to make a wireless VR headset feasible.
The issue with using millimeter wave technology is that the signal needs a direct line of sight, and fares poorly when it encounters any obstacles. MoVR gets around this by working as a programmable mirror that can direct the direction of the signal to the headset even while it's moving to always make sure the signal is transmitting directly to the headset's receivers.
For now, the MoVR is simply a prototype, with the team hoping to further shrink down the system to allow for multiple wireless headsets in one room without encountering signal interference. But even as a proof-of-concept, it's an interesting perspective on how virtual reality could one day work.
1 2 3 … 16 Next Page ›
Widget Area "Footer Box 1"
New Service Launched
My First Post
Constitution Hill, London
Phone +62 12345689, Fax +62 12345689
Email support@localhost.com
© 2019 palm communications
Powered by Orbit & WordPress.

redpajama_set_name: RedPajamaCommonCrawl