Biquadratic reciprocity and a Lucasian primality test

Abstract:

Let $\{s_k,k\geq 0\}$ be the sequence defined from a given initial value $s_0$ by the recurrence $s_{k+1}=s_k^2-2,k\geq 0$. Then, for a suitable initial value $s_0$, the number $M_{h,n}=h.2^n-1$ is prime iff $s_{n-2} \equiv 0 \bmod M_{h,n}$. In general $s_0$ depends both on $h$ and on $n$. We describe a slight modification of this algorithm which determines primality of numbers $h.2^n\pm 1$ with a seed which depends only on $h$, provided $h \not \equiv 0 \bmod 15$. The proof of validity uses biquadratic reciprocity.