Abstract view
Pseudoprime Reductions of Elliptic Curves


Published:20110627
Printed: Feb 2012
C. David,
Department of Mathematics and Statistics, Concordia University, Montréal, QC, H3G 1M8
J. Wu,
Institut Elie Cartan Nancy, CNRS, Université Henri Poincaré (Nancy 1), INRIA, 54506 VandœuvrelèsNancy, France
Abstract
Let $E$ be an elliptic curve over $\mathbb Q$ without complex multiplication,
and for each prime
$p$ of good reduction, let $n_E(p) =  E(\mathbb F_p) $. For any integer
$b$, we consider elliptic pseudoprimes to the base
$b$. More precisely, 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 let $\pi_{E,
b}^{\operatorname{pseu}}(x)$ be the number of 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 the problem of finding upper bounds for
$Q_{E,b}(x)$ and $\pi_{E, b}^{\operatorname{pseu}}(x)$,
generalising some of the literature for the classical pseudoprimes
to this new setting.