Biquadratic reciprocity and a Lucasian primality test

Abstract

Let $\{s_k,k\geq 0\}$ be the sequence defined from a given initial value, the seed, $s_0$, by the recurrence $s_{k+1}=s_k^2-2,k\geq 0$. Then, for a suitable seed $s_0$, the number $M_{h,n}=h\cdot 2^n-1$ (where $h<2^n$ is odd) 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 test which determines primality of numbers $h\cdot 2^n\pm 1$ with a seed which depends only on $h$, provided $h \not \equiv 0 \bmod 5$. In particular, when $h=4^m-1$, $m$ odd, we have a test with a single seed depending only on $h$, in contrast with the unmodified test, which, as proved by W. Bosma in Explicit primality criteria for $h\cdot 2^k\pm 1$, Math. Comp. 61 (1993), 97–109, needs infinitely many seeds. The proof of validity uses biquadratic reciprocity.