Fast primality tests for numbers less than 50 · 10 9

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(O) = 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 X3 rx2 + 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 < 50 * 109 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.