\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\<{\langle} \def\>{\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}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 < \cdots < 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} > {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|< 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} < 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} < 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}