Fast primality tests for numbers less than $50\cdot 10^ 9$

Abstract:

Consider the doubly infinite set of sequences $A(n)$ given by \[ A(n + 3) = rA(n + 2) - sA(n + 1) + A(n)\] with $A( - 1) = s$, $A(0) = 3$, $A(1) = r$. For a given pair r,s, the "signature" of n is defined to be the sextet \[ A( - n - 1),A( - n),A( - n + 1),A(n - 1),A(n),A(n + 1),\] each reduced modulo n. Primes have only three types of signatures, depending on how they split in the cubic field generated by ${x^3} - r{x^2} + sx - 1$. An "acceptable" composite is a composite integer which has the same type of signature as a prime; such integers are very rare. In this paper, a description is given of the results of a computer search for all acceptable composites $\leqslant 50 \cdot {10^9}$ in the Perrin sequence $(r = 0,s = - 1)$. Also, some numbers which are acceptable composites for both the Perrin sequence and the sequence with $r = 1$, $s = 0$ are presented.