<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf On the Complexity of Testing Elite Primes
}
\vskip 1cm
\large
Michal K\v r\'{\i}\v zek\\
Institute of Mathematics\\
Academy of Sciences\\
\v{Z}itn\'{a} 25\\
CZ -- 115 67, Praha 1 \\
Czech Republic\\
\href{mailto:krizek@math.cas.cz}{\tt krizek@math.cas.cz}\\
\ \\
Florian~Luca\\ 
Instituto de Matem{\'a}ticas\\
Universidad Nacional Autonoma de M{\'e}xico\\
C.P. 58089, Morelia, Michoac{\'a}n\\
M{\'e}xico\\
\href{mailto:fluca@matmor.unam.mx}{\tt fluca@matmor.unam.mx}\\
\ \\
Igor E. Shparlinski  \\
Department of Computing  \\
Macquarie University \\
Sydney, NSW 2109\\
Australia\\
\href{mailto:igor@ics.mq.edu.au}{\tt igor@ics.mq.edu.au}\\
\ \\
Lawrence Somer\\
Department of Mathematics\\
Catholic University of America\\
Washington, DC 20064 \\
USA\\
\href{mailto:somer@cua.edu}{\tt somer@cua.edu}
\end{center}

\newpage

\begin{abstract} Aigner has defined elite primes as primes
$p$ such that all but finitely many of 
Fermat numbers $F(n)= 2^{2^n} + 1$, $n=0,1,2,\ldots$, are quadratic nonresidues
modulo $p$. Since the sequence of Fermat numbers is eventually
periodic modulo any $p$ with at most $p$ distinct elements in
the image, both the period length $t_p$
and the number of arithmetic operations modulo $p$ to test $p$
for being elite are also bounded by $p$. We show that  $t_p =
O(p^{3/4})$, in particular improving the estimate $t_p\le
(p+1)/4$ of M\"uller and Reinhart in 2008.
The same bound $O(p^{3/4})$  also holds for testing
anti-elite primes.
\end{abstract}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}





%\usepackage{amsmath,amssymb,amsbsy,amsfonts,amsthm,latexsym,amsopn,amstext,amsxtra,euscript,amscd}
% \begin{document}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{claim}[theorem]{Claim}
%\newtheorem{cor}[theorem]{Corollary}
%\newtheorem{rem}[theorem]{Remark}
%\newtheorem{definition}{Definition}
%\newtheorem{question}[theorem]{Open Question}

%%%%%%%%%%%%%%%%%%%%%%%%%
% Alphabet calligraphic %
%%%%%%%%%%%%%%%%%%%%%%%%%
\def\cA{{\mathcal A}}
\def\cB{{\mathcal B}}
\def\cC{{\mathcal C}}
\def\cD{{\mathcal D}}
\def\cE{{\mathcal E}}
\def\cF{{\mathcal F}}
\def\cG{{\mathcal G}}
\def\cH{{\mathcal H}}
\def\cI{{\mathcal I}}
\def\cJ{{\mathcal J}}
\def\cK{{\mathcal K}}
\def\cL{{\mathcal L}}
\def\cM{{\mathcal M}}
\def\cN{{\mathcal N}}
\def\cO{{\mathcal O}}
\def\cP{{\mathcal P}}
\def\cQ{{\mathcal Q}}
\def\cR{{\mathcal R}}
\def\cS{{\mathcal S}}
\def\cT{{\mathcal T}}
\def\cU{{\mathcal U}}
\def\cV{{\mathcal V}}
\def\cW{{\mathcal W}}
\def\cX{{\mathcal X}}
\def\cY{{\mathcal Y}}
\def\cZ{{\mathcal Z}}

%%%%%%%%%%%%%%%%%%%%%%%
% Alphabet blackboard %
%%%%%%%%%%%%%%%%%%%%%%%
\def\A{{\mathbb A}}
\def\B{{\mathbb B}}
\def\C{{\mathbb C}}
\def\D{{\mathbb D}}
\def\E{{\mathbb E}}
\def\F{{\mathbb F}}
\def\G{{\mathbb G}}
%% \def\H{{\mathbb H}}
\def\I{{\mathbb I}}
\def\J{{\mathbb J}}
\def\K{{\mathbb K}}
\def\L{{\mathbb L}}
\def\M{{\mathbb M}}
\def\N{{\mathbb N}}
\def\O{{\mathbb O}}
\def\P{{\mathbb P}}
\def\Q{{\mathbb Q}}
\def\R{{\mathbb R}}
\def\S{{\mathbb S}}
\def\T{{\mathbb T}}
\def\U{{\mathbb U}}
\def\V{{\mathbb V}}
\def\W{{\mathbb W}}
\def\X{{\mathbb X}}
\def\Y{{\mathbb Y}}
\def\Z{{\mathbb Z}}

\def\E{{\mathbf E}}
\def\Fp{\F_p}
\def\ep{{\mathbf{e}}_p}
\def\Nm{{\mathrm{Nm}}}
\def\lcm{{\mathrm{lcm}}}
\def\cWe{\cW_\varepsilon}
\def\cMe{\cM_\varepsilon}
\def\pie{\pi_\varepsilon}

\def\scr{\scriptstyle}
\def\\{\cr}
\def\({\left(}
\def\){\right)}
\def\[{\left[}
\def\]{\right]}
\def\&lt;{\langle}
\def\&gt;{\rangle}
\def\fl#1{\left\lfloor#1\right\rfloor}
\def\rf#1{\left\lceil#1\right\rceil}
\def\le{\leqslant}
\def\ge{\geqslant}
\def\eps{\varepsilon}
\def\mand{\qquad\mbox{and}\qquad}

\newcommand{\comm}[1]{\marginpar{%
\vskip-\baselineskip %raise the marginpar a bit
\raggedright\footnotesize
\itshape\hrule\smallskip#1\par\smallskip\hrule}}

\def\xxx{\vskip5pt\hrule\vskip5pt}


\section{Introduction}

Motivated by a generalization of the 
Pepin primality test for  Fermat numbers $F(n)= 2^{2^n} + 1$, $n=0,1,2,\dots$, 
Aigner~\cite{Aig}  introduced the notion of {\it elite
primes\/} which are the primes $p$ such that $F_n$ is a
quadratic nonresidue modulo $p$ 
for all but finitely many $n$. For example, 3, 5, 7, and 41 are
elite primes. See~\cite{KLS,MuRe} and the references 
therein for various results about elite primes and their
generalizations. 

One such generalization appears  in the work of 
M\"uller and Reinhart~\cite{MuRe}, where 
{\it $b$-elite primes\/} have been defined for 
an integer $b\ge 2$ as those primes $p$ for which all but 
finitely many elements 
of the sequence $F_b(n) =  b^{2^n} + 1$ are quadratic nonresidues
modulo $p$. One can easily see that the estimate $O(x/(\log
x)^2)$ on the number of elite primes up to $x \ge 2$, proved 
in~\cite{KLS}, immediately 
extends to $b$-elite primes. It has
also been noted in~\cite{MuRe} that 
for any $p$, the sequence $\{F_b(n)\}_{n\ge 0}$ is
eventually periodic modulo $p$ with some period length $t_p$. That is,
for some period length $t_p$ and 
preperiod length $s_p \ge 0$ we have
\begin{equation}
\label{eq:per}
F_b(n+t_p) \equiv F_b(n) \pmod p, \quad n = s_p, s_p+1, \ldots.
\end{equation}
It is also obvious that the smallest values of $s_p$ and $t_p$
satisfy the inequality
$s_p+t_p \le p$.

M\"uller and Reinhart~\cite[Theorem~2.8]{MuRe}  have shown 
that for 
$b$-elite primes $p$ the period $t_p$ satisfies the inequality
$$
t_p\le \frac{p+1}{4}.
$$
It follows immediately 
from~\cite[Theorem~2.6]{MuRe} that the preperiod $s_p$  is 
less than or equal to the
exponent of the prime $2$ in the factorization of 
$p-1$, and thus  satisfies
\begin{equation}
\label{eq:sp}
s_p \le \frac{\log(p-1)}{\log 2}.
\end{equation}

We now improve these results as follows. 

\begin{theorem}
\label{thm:PerLength} For a $b$-elite prime $p$, we
have 
$$
t_p \le 3p^{3/4}.
$$
\end{theorem}

Clearly, $p$ is $b$-elite if and only if all numbers $F_b(n)$
for $n \ge s_p$ are quadratic nonresidues. 
We also recall that quadratic residuosity on an integer $a$ can be tested 
in $O(\log p)$ arithmetic operations modulo $p$ (for example,
computing $a^{(p-1)/2}$ via repeated squaring).
Thus any prime $p$ can
be tested for being $b$-elite
in $O((s_p+t_p)\log p)$ arithmetic operations modulo $p$
(see~\cite[Section~3]{MuRe} for a description of such an 
algorithm). This complexity can be trivially estimated as
$O(p\log p)$. 

Using Theorem~\ref{thm:PerLength} together with~\eqref{eq:sp} and the fact that the inequality 
$$
s_p\le \frac{\log(p-1)}{\log 2}&lt;p^{3/4}\qquad {\text{\rm for~all}}\quad p\ge 5, 
$$
we now improve this trivial bound as follows:

\begin{corollary}
\label{cor:Test} A prime $p$ can be tested for being a $b$-elite
prime in at most $O(p^{3/4}\log p)$ arithmetic operations modulo $p$. 
\end{corollary}

\section{Proof of Theorem~\ref{thm:PerLength}}

In what follows, we let  $(z/p)$ 
denote, as usual, the Legendre symbol of the integer $z$ 
modulo the odd prime $p$. 

Our main tool is a special case of the {\it Weil bound\/} 
for multiplicative character sums in the following form 
that is convenient for our application
(see~\cite[Theorem~11.23]{IwKow}):

\begin{lemma}
\label{lem:Weil} 
For any polynomial $f(X) \in \Z[X]$ of degree $m$ which is not a
perfect square 
modulo $p$, we have 
$$
\left|\sum_{u=0}^{p-1} \(\frac{f(u)}{p}\) \right|\le m p^{1/2}.
$$
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{thm:PerLength}]
Let us consider the polynomials 
$f_k(X) = X^{2^k} + 1$.
We assume that $p&gt;2$. We take some integer $K\ge 1$ to be fixed
in a way depending on $p$ later on, and count how often
the values 
$$f_k(u), \qquad k=0, \ldots, K-1,
$$ are simultaneously
quadratic nonresidues modulo $p$ for $u = 0, \ldots, p-1$.
Call this number $T_p(K)$. We have
\begin{equation}
\label{eq:TqK}
T_p(K) = \frac{1}{2^K} \sum_{u=0}^{p-1} 
\prod_{k=0}^{K-1} \(1-\(\frac{f_k(u)}{p}\)\).
\end{equation}

Expanding the product in~\eqref{eq:TqK}, we obtain $2^K-1$
character sums of the shape
\begin{equation}
\label{eq:Sums}
\sum_{u=0}^{p-1} \(\frac{F_{k_1, \ldots, k_\nu}(u)}{p}\),
\qquad 0 \le k_1 &lt; \cdots &lt; k_\nu\le K-1,
\end{equation}
where 
\begin{equation}
\label{eq:FkX}
F_{k_1, \ldots, k_\nu}(X) = (-1)^\nu \prod_{j=1}^\nu f_{k_j}(X)
\end{equation}
with $\nu \ge 1$, and one trivial sum that equals $p$
(corresponding to taking all the terms  equal to $1$ in the
product in~\eqref{eq:TqK}). 
Then $f_{k_\nu}(X)$  modulo $p$ is square-free because its
derivative is $2^{k_\nu}X^{2^{k_\nu}-1} \pmod p$ and its only 
zero is $X=0$, which is not a zero of $f_{k_{\nu}}(X)$ modulo
$p$. Since 
$$
\deg f_{k_\nu} ={2^\nu} &gt; {2^\nu}-1 = \sum_{j=0}^{k_\nu -1}\deg f_j,
$$
it follows that the polynomial $F_{k_1, \ldots, k_\nu}$ is not a
perfect square modulo $p$.
Hence, Lemma~\ref{lem:Weil} applies to every 
sum~\eqref{eq:Sums} and implies that each sum of the 
type \eqref{eq:Sums} is at most $2^K p^{1/2}$ by absolute value.
Thus, 
\begin{equation}
\label{eq:O}
\left| T_p(K) - \frac{p}{2^K}\right|&lt; 2^K p^{1/2}.
\end{equation}
The bound~\eqref{eq:O} holds for a general $p$. When $p$ is a $b$-elite prime
there are at least $t_p$ solutions $u$ for which $f_k(u)$
is a quadratic nonresidue for $k=0,1,\dots,K-1$,
namely all $u$ of the form
$$u=b^{2^{n+s_p}}, \qquad n =0, \ldots, t_p-1.
$$ 
Choosing $K$ to satisfy 
\begin{equation}
\label{eq:K}
2^K \le p^{1/4} &lt; 2^{K+1},
\end{equation}
we easily get from~\eqref{eq:O} that 
$$
t_p\le T_p(K)  \le 3p^{3/4},
$$
which is the desired result. \end{proof} 



 

\begin{remark} By replacing the inequalities~\eqref{eq:K} with 
$2^K \le \sqrt{2} p^{1/4} &lt; 2^{K+1}$, we can improve the 
constant $3$ in Theorem~\ref{thm:PerLength} to $2 \sqrt{2}$.
It is easy to see that this can be further  improved by 
a slightly more precise estimation of the degrees of the
polynomials~\eqref{eq:FkX} and thus of the sums~\eqref{eq:Sums}.
\end{remark}

\section{Anti-Elite Primes}

In contrast with the elite primes, M\"uller in~\cite{Mu} defines an
anti-elite prime as a prime $p$ for which $F(n)$ is a quadratic
residue modulo $p$ for all but finitely many $n$. 
For example, 13 and 97 are anti-elite primes and so are all Fermat
primes greater than 5. As with
$b$-elite primes, we can define a $b$-anti-elite prime $p$,
where $b\ge 2$, as a prime for which all but finitely many
elements of the sequence $F_b(n)$ are quadratic residues modulo
$p$. 
Thus, the period of $\{F_b(n)\}_{n\ge 0}$ modulo $p$ consists only of
quadratic residues when $p$ is an anti-elite prime. We can prove
the following analogue of Theorem~\ref{thm:PerLength} for 
$b$-anti-elite primes.

\begin{theorem}
\label{thm:PerLength-anti} For a $b$-anti-elite prime $p$, we
have 
$$
t_p  \le 3 p^{3/4},
$$
where $t_p$ is the period length of the eventually periodic sequence
$\{F_b(n)\}_{n\ge 0}$ modulo $p$.
\end{theorem}

The proof of Theorem~\ref{thm:PerLength-anti} is similar to the proof of
Theorem~\ref{thm:PerLength}.  In the proof of 
Theorem~\ref{thm:PerLength}, we only need to replace
each occurrence of ``quadratic nonresidue" by ``quadratic
residue", replace the minus sign in the equation~\eqref{eq:TqK} by a plus
sign, and delete the factor $(-1)^\nu$ in~\eqref{eq:FkX}. 


\begin{thebibliography}{9}

\bibitem{Aig}  A. Aigner, \"Uber Primzahlen, nach denen (fast) 
alle Fermatische Zahlen quadratische Nichtreste sind, 
{\it Monatsh. Math.\/} {\bf 101} (1986), 85--93.

\bibitem{IwKow} H. Iwaniec and E. Kowalski,
{\it Analytic Number Theory\/}, Amer.\ Math.\ Soc., 
2004.

\bibitem{KLS} M. K{\v r}{\'i}{\v z}ek, F. Luca, and L. Somer, 
On the convergence of series of reciprocals of primes
related to the Fermat numbers,
{\it J. Number Theory\/} {\bf 97} (2002), 95--112.

\bibitem{Mu} T. M\"uller,
On anti-elite prime numbers, {\it J. Integer Sequences\/}
{\bf 10} (2007),
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Mueller/mueller56.html}{Article 07.9.4}.

\bibitem{MuRe} T. M\"uller and A. Reinhart, 
On generalized elite primes, {\it J. Integer Sequences\/}
{\bf 11} (2008), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Mueller/mueller445.html}{Article 08.3.1}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11A07; Secondary 11L40.

\noindent \emph{Keywords: } elite prime testing, character sum.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A102742} and
\seqnum{A128852}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received October 12 2010;
revised version received December 20 2010. 
Published in {\it Journal of Integer Sequences}, January 4 2011.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>