  Let $E$ be an elliptic curve over $\F_p$ without complex multiplication, and
for each prime $p$ of good reduction, let $n_E(p) = | E(\F_p) |$. Let
$Q_{E,b}(x)$ be the number of primes $p \leq x$ such that $b^{n_E(p)} \equiv
b\,({\rm mod}\,n_E(p))$, and $\pi_{E, b}^{\rm pseu}(x)$ be the number of {\it
compositive} $n_E(p)$ such that $b^{n_E(p)} \equiv b\,({\rm mod}\,n_E(p))$
(also called elliptic curve pseudoprimes). Motivated by cryptography
applications, we address in this paper the problem of finding upper bounds for
$Q_{E,b}(x)$ and $\pi_{E, b}^{\rm pseu}(x)$, generalising some of the
literature for the classical pseudoprimes \cite{Erdos56, Pomerance81} to this
new setting.
