\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}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\usepackage{tikz}
\usetikzlibrary{matrix,arrows}
\newcommand{\mc}{\mathcal}
\newcommand{\mb}{\mathbf}
\newcommand{\F}{\mathbf F}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\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}
\begin{center}
\vskip 1cm{\LARGE\bf
A Proof of the Lucas-Lehmer Test and its
\\
\vskip .1in
Variations by Using a Singular Cubic Curve
}
\vskip 1cm
\large
\"{O}mer K\"{u}\c{c}\"{u}ksakall{\i}\\
Mathematics Department\\
Middle East Technical University\\
06800 Ankara\\
Turkey\\
\href{mailto:komer@metu.edu.tr}{\tt komer@metu.edu.tr} \\
\end{center}
\vskip .2 in
\begin{abstract}
We give another proof of the Lucas-Lehmer test by using a singular cubic
curve. We also illustrate a practical way to choose a starting term
for the Lucas-Lehmer-Riesel test by trial and error. Moreover, we provide
a nondeterministic test for determining the primality of integers of the form
$N=hp^n-1$ for any odd prime $p$. We achieve these by using the group structure
on a singular cubic curve induced from the group law of elliptic curves.
\end{abstract}
\section{Introduction}
The largest primes known are given by expressions of the type $N=2^n-1$ since there is an efficient, deterministic primality test for such integers.
\begin{theorem}[Lucas-Lehmer]\label{lucaslehmer}
Let $S_0=4$. If we define $S_k = S_{k-1}^2-2$ for all $k\geq 1$ recursively, then the integer $N=2^n-1$ is prime if and only if $S_{n-2} \equiv 0 \pmod{N}$.
\end{theorem}
There are already several proofs of this fact in the literature \cite{bruce, gross, lehmer, lucas, rosen, rodseth}. In this
paper, we give another proof by using a singular cubic curve. Secondly, we
illustrate a practical way to choose $S_0$ by trial and error for the
Lucas-Lehmer-Riesel test, which is concerned with the integers of the form
$N=h2^n-1$. Finally, we give a nondeterministic test for determining the
primality of integers of the form $N=hp^n-1$ for an odd prime $p$.
\section{Main results}
Consider the projective curve
\[C:y^2=4x^3+x^2.\]
Let $K$ be an arbitrary field with char$(K)\neq 2$. The curve $C$ is a singular
cubic curve defined over $K$ that has a node at the origin. There are two distinct tangent lines at the origin, namely $y=x$ and $y=-x$. The cubic curve $C$ and these tangent lines are illustrated in Figure~\ref{node}.
\begin{figure}[htbp]
\centering
\includegraphics[scale=0.6]{kucuk-node.eps}
\caption{Cubic curve $C:y^2=4x^3+x^2$.}
\label{node}
\end{figure}
The non-singular part of $C$ with coordinates from $K$ is denoted by
$C_\text{ns}(K)$. The group law of elliptic curves makes $C_\text{ns}(K)$ into
an abelian group. Moreover, we have the following characterization for this
group.
\begin{proposition}\label{silverman}
The map $\psi:C_\text{ns}(K) \rightarrow K^*$ given by the formula $\psi(x,y) =
\frac{y-x}{y+x}$ is a group isomorphism.
\end{proposition}
\begin{proof}
See \cite[Prop.~III.2.5]{sil} and \cite[Exer.~3.5]{sil}.
\end{proof}
There is a connection between the map $x\mapsto x^2-2$ and the duplication map
on $C_\text{ns}(K)$. To see this connection, we follow \cite{kucuksakalli} and
consider
\[ \phi(z)=\frac{e^z}{(1-e^z)^2}\]
and its derivative
\[\phi'(z)=\frac{e^z(e^z+1)}{(1-e^z)^3}.\]
It is easily verified that the cubic curve $C:y^2=4x^3+x^2$ is parametrized
by $x=\phi(z)$ and $y=\phi'(z)$. Note that $\psi((\phi(z),\phi'(z))) = e^z$
under the isomorphism of Proposition~\ref{silverman}. It follows that
$[n](\phi(z),\phi'(z))=(\phi(nz),\phi'(nz))$ since $(e^z)^n = e^{nz}$.
The family of Dickson polynomials, denoted $\mc{D}_n(x)$, is a normalization of
Chebyshev polynomials that is used in the theory of finite fields \cite{lidl}.
For each integer $n$, the polynomial $\mc{D}_n(x)$ is uniquely defined by the
equation $\mc{D}_n(y+y^{-1}) = y^n+y^{-n}$ where $y$ is an indeterminate. The
first few examples of these polynomials are $\mc{D}_1(x) =x, \mc{D}_2(x) =x^2-2$ and $\mc{D}_3(x) =x^3-3x$. Note that $\phi(z) = 1/(e^z+e^{-z}-2)$. Now, it is clear that
\[ \mc{D}_n\left(\frac{1}{\phi(z)}+2\right) = \mc{D}_n(e^z+e^{-z}) =
e^{nz}+e^{-nz} = \frac{1}{\phi(nz)}+2. \]
For any integer $n\geq 1$, define $f_n(x) := 1/(\mc{D}_n(1/x+2)-2)$. The
rational function $f_n(x)$ satisfies the functional equation $f_n(\phi(z)) =
\phi(nz)$ by the computation above. Let $\pi_x$ be the projection to the first
coordinate. Set $L(x)=1/x+2$. We write $\mb{P}^1(K) = K\cup\{\infty\}$. We have the following commutative diagram:
\begin{center}
\begin{tikzpicture}
\matrix (m) [matrix of math nodes,row sep=1.2em,column sep=10em,minimum
width=2em] {
C_\text{ns}(K) & C_\text{ns}(K) \\
\mb{P}^1(K) & \mb{P}^1(K) \\
\mb{P}^1(K) & \mb{P}^1(K)\\};
\path[-stealth]
(m-1-1) edge node [left] {$\pi_x$} (m-2-1)
(m-1-1) edge node [above] {$[n]$} (m-1-2)
(m-2-1) edge node [above] {$f_n$} (m-2-2)
(m-1-2) edge node [right] {$\pi_x$} (m-2-2)
(m-2-1) edge node [left] {$L$} (m-3-1)
(m-3-1) edge node [above] {$\mc{D}_n$} (m-3-2)
(m-2-2) edge node [right] {$L$} (m-3-2);
\end{tikzpicture}
\end{center}
For the case $n=2$, we have
\[[2](x,y) =\left( \frac{x^2}{4x+1},\frac{x^3(2x+1)}{y(4x+1)} \right).\]
The rational map $f_2$ associated with the duplication map on
$C_\text{ns}(K)$ is given by $f_2(x)=x^2/(4x+1)$. Recall that it satisfies
the relation $f_2(x) = 1/(\mc{D}_2(1/x+2)-2)$ where $\mc{D}_2(x)=x^2-2$.
There is a unique point of $C_\text{ns}(K)$ of order two, namely $(-1/4,0)$.
Note that there are two points of order four, namely $(-1/2,i/2)$ and
$(-1/2,-i/2)$. To see this, we can use $f_4(x)=f_2(f_2(x)) =
x^4/((2x+1)^2(4x+1))$.
The following fact is the key argument to our alternative proof of Theorem~\ref{lucaslehmer}.
\begin{lemma}\label{order}
Let $p$ be an odd prime and let $P=(x,y)$ be a point of $C_\text{ns}(\F_{p^2})$. If $x\in \F_p$, then the order of $P$, denoted $o(P)$, satisfies the following:
\begin{enumerate}
\item $o(P)$ divides $p-1$ if $y\in\F_p$, and
\item $o(P)$ divides $p+1$ if $y\not\in\F_p$.
\end{enumerate}
\end{lemma}
\begin{proof}
If both coordinates of $P$ are in $\F_p$, then $\psi(x,y) = \frac{y-x}{y+x} \in
\F_p^*$. We have $\psi(x,y)^{p-1}=1$ and we conclude that $o(P)$ divides $p-1$
by Proposition~\ref{silverman}.
Now suppose that $x\in \F_p$ but $y\not\in\F_p$. We have $y^p=-y$ because $y^2=4x^3+x^2$. Observe that
\[\psi(x,y)^{p+1} = \left(\frac{y-x}{y+x}\right)^p \left(\frac{y-x}{y+x}
\right) = \left( \frac{-y-x}{-y+x} \right) \left(\frac{y-x}{y+x}\right) =1. \]
We conclude that $o(P)$ divides $p+1$ by Proposition~\ref{silverman}.
\end{proof}
A natural generalization of the Lucas-Lehmer test, namely the Lucas-Lehmer-Riesel test, is concerned with integers of the form $N=h2^n-1$ for
odd integers $h$. The recurrence relation is the same for this generalized
test. However, the starting value $S_0$ varies depending on both $h$ and $n$.
Historically, the proof of this theorem was obtained in several steps:
\begin{enumerate}
\item If $h=1$, and if $n\equiv 3\pmod{4}$ then pick $S_0=3$. \cite{lucas}
\item If $h=1$, and if $n\equiv 1\pmod{2}$ then choose $S_0=4$. \cite{lehmer}
\item If $h=3$, and if $n \equiv 0, 3 \pmod{4}$, then choose $S_0 = 5778$.
\cite{lehmer}
\item If $h \equiv 1,5 \pmod{6}$, and if $3 \nmid N$, then choose $S_0 =
w^h+w^{-h}$ where $w=2+\sqrt{3}$. \cite{riesel56}
\item Otherwise, $h$ is a multiple of $3$ and we follow \cite{riesel69}
to choose $S_0$.
\end{enumerate}
Unfortunately, there may not be any canonical value for $S_0$ even though the
$h$ value is fixed \cite{bosma}. On the other hand, it is easy to choose $S_0$
by trial and error in practice by using the Jacobi symbol. For this purpose, we
give the following method, which is inspired by \cite{rodseth}.
\begin{theorem}\label{main}
Given $N=h2^n-1$, with $n>1$, $h$ odd and $01$ and
$\gcd(h,p)=1$. Let $D$ be a positive integer such that the Jacobi symbol
satisfies $\genfrac(){}{}{D}{N} = -1$ and $\genfrac(){}{}{D-1}{N} = 1$. Define
the generalized Lucas sequence by
\[ S_0 = \mc{D}_h\left(\frac{2(D+1)}{D-1}\right) \quad \textnormal{and} \quad
S_k=\mc{D}_p(S_{k-1})\] for $k\geq1$. This sequence has the following
properties:
\begin{enumerate}
\item If $S_k \not \equiv 2 \pmod{N}$ for all $k \leq n$, then $N$ is
composite.
\item If $S_k \equiv 2 \pmod{N}$ for some positive minimal integer
$k \leq n$ and $p^{2k}>N$ then $N$ is prime.
\end{enumerate}
\end{theorem}
\begin{proof}
Suppose that $N$ is prime. As in the proof of the previous theorem, let
$P=(t,t\sqrt{D})$ with $t=L^{-1}(\frac{2(D+1)}{D-1})=(D-1)/4$. The order of
$P\in C_\text{ns}(\F_{N^2})$ is a divisor of $N+1=hp^n$ by Lemma~\ref{order}. It follows that the order of $[h]P$ is a divisor of $p^n$. Then we must have
$[p^k]P = \infty$ for some $k \leq n$. This finishes the proof of the first
part. Now, suppose that $N$ is composite. Let $q$ be a prime factor of $N$ with
the Jacobi symbol $\genfrac(){}{}{D}{q} = -1$. In $C_\text{ns}(\F_{q^2})$, we have $[q+1]P=\infty$ by Lemma~\ref{order}. Therefore $[q+1][h]P=\infty$, too. On the other hand, assume that $\mc{D}_{p^k}(S_0) \equiv 2 \pmod{N}$ for some minimal positive integer $k$. It follows that the order of $[h]P$ is $p^k$.
We conclude that $p^k$ divides $q+1$, i.e., $q+1=p^k\ell$ for some integer
positive integer $\ell$. We have $hp^n - 1 = N = (p^k\ell-1)m$ for some integer
$m$. Reducing everything modulo $p^k$, it is easily seen that $m = p^ka+ 1$
for some integer $a$. Since $N\neq p$, it is obvious that $a\geq1$.
Hence $\ell\geq1$ or $a\geq1$, and therefore $p^{2k} \leq N$.
\end{proof}
We remark that the inequality $p^{2k} > N$ in the second part of the above
theorem can be improved as in \cite{williams87}. We will leave it as it is for simplicity since this test is far from being deterministic in either case. On the other hand it is a common practice in algorithmic number theory to use a random element of a cyclic group since its order is expected to be large most of the time.
In order to make the above theorem deterministic, after $S_0$ is chosen, we
need to prove that the congruence $\mc{D}_p(x) \equiv S_0 \pmod{N}$ has no
solution if $N$ is prime. It would then imply that $P$ has order
precisely $p^n$. In that case, we could replace the second part of the above
theorem as: ``Otherwise, $S_n\equiv 2\pmod{N}$ and $N$ is prime if $p^n>h$''.
This would give us a necessary and sufficient test if $p^n>h$. More precisely,
we would be able to say that $N=hp^n-1$ is prime if and only if $S_n\equiv
2\pmod{N}$. This idea has already been accomplished by Berrizbeitia and Berry for $p=3$ by using the cubic reciprocity law \cite{berry}. We hope that the isomorphism of Proposition~\ref{silverman} together with the higher degree reciprocity laws may shed some light in the future for the cases $p\geq 5$.
\section{Acknowledgment}
The author thanks S. Wong and an anonymous referee for their helpful
comments and suggestions to improve this manuscript.
\begin{thebibliography}{99}
\bibitem{berry}
P.~Berrizbeitia and T.~G.~Berry, Cubic reciprocity and generalised
Lucas-Lehmer tests for primality of $A\cdot3^n\pm1$, \textit{Proc. Amer. Math. Soc.} {\bf 127} (1999), 1923--1925.
\bibitem{bosma}
W.~Bosma, Explicit primality criteria for $h⋅2^k\pm1$, \textit{Math. Comp.} {\bf 61} (1993), 97--109.
\bibitem{bruce}
J.~W.~Bruce, A really trivial proof of the Lucas-Lehmer test, \textit{Amer. Math. Monthly} {\bf 100} (1993), 370--371.
\bibitem{gross}
B.~H.~Gross, An elliptic curve test for Mersenne primes, \textit{J. Number Theory} {\bf 110} (2005), 114--119.
\bibitem{kucuksakalli}
\"{O}. K\"{u}\c{c}\"{u}ksakall\i, Value sets of Latt\`{e}s maps over finite
fields, \textit{J. Number Theory} {\bf 143} (2014), 262--278.
\bibitem{lehmer}
D.~H.~Lehmer, An extended theory of Lucas' functions, \textit{Ann. of Math. (2)} {\bf 31} (1930), 419--448.
\bibitem{lidl}
R.~Lidl and H.~Niederreiter, \textit{Finite Fields}.
Encyclopedia of Mathematics and Its Applications, Vol.~20, Second edition,
Cambridge University Press, 1997.
\bibitem{lucas}
E.~Lucas, Th\'{e}orie des fonctions num\'{e}riques simplement p\'{e}riodiques,
\textit{Amer. J. Math.} {\bf 1} (1878), 184--196.
\bibitem{riesel56}
H.~Riesel, A note on the prime numbers of the forms $N=(6a+1)2^{2n-1}-1$ and
$M=(6a-1)2^{2n}-1$, \textit{Ark. Mat.} {\bf 3} (1956), 245--253.
\bibitem{riesel69}
H.~Riesel, Lucasian criteria for the primality of $N=h\cdot2^n-1$, \textit{Math. Comp.} {\bf 23} (1969) 869--875.
\bibitem{rosen}
M.~I.~Rosen, A proof of the Lucas-Lehmer test, \textit{Amer. Math. Monthly} {\bf 95} (1988), 855--856.
\bibitem{rodseth}
\"{O}.~J.~R\"{o}dseth, A note on primality tests for $N=h⋅2^n-1$, \textit{BIT} {\bf 34} (1994), 451--454.
\bibitem{sil}
J.~H.~Silverman, \textit{The Arithmetic of Elliptic Curves,} Second edition,
Graduate Texts in Mathematics, Vol.~106, Springer, 2009.
\bibitem{williams72}
H.~C.~Williams, The primality of $N=2A3^n-1$, \textit{Canad. Math. Bull.} {\bf 15} (1972), 585--589.
\bibitem{williams87}
H.~C.~Williams, Effective primality tests for some integers of the forms
$A5^n-1$ and $A7^n-1$, \textit{Math. Comp.} {\bf 48} (1987), 385--403.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11Y11; Secondary 11G20.
\noindent \emph{Keywords: } elliptic curve, Jacobi symbol, Dickson polynomial, Lucas sequence.
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received May 29 2018;
revised versions received May 30 2018; July 5 2018.
Published in {\it Journal of Integer Sequences}, July 11 2018.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}