A detailed investigation is given of the possible use of cubic recurrences in primality tests. No attempt is made in this abstract to cover all of the many topics examined in the paper. Define a doubly infinite set of sequencesA(n)A(n)by\[A(n+3)=rA(n+2)−sA(n+1)+A(n)A(n + 3) = rA(n + 2) - sA(n + 1) + A(n)\]withA(−1)=sA( - 1) = s,A(0)=3A(0) = 3, andA(1)=rA(1) = r. Ifnis prime,A(n)≡A(1)(modn)A(n) \equiv A(1)\;\pmod n. Perrin asked if any composite satisfies this congruence ifr=0r = 0,s=−1s = - 1. The answer is yes, and our first example leads us to strengthen the condition by introducing the "signature" ofn:\[A(−n−1),A(−n),A(−n+1),A(n−1),A(n),A(n+1)A( - n - 1),A( - n),A( - n + 1),A(n - 1),A(n),A(n + 1)\]modn\bmod n. Primes have three types of signatures depending on how they split in the cubic field generated byx3−rx2+sx−1=0{x^3} - r{x^2} + sx - 1 = 0. Composites with "acceptable" signatures do exist but are very rare. TheS-type signature, which corresponds to the completely split primes, has a very special role, and it may even be thatIandQtype composites do not occur in Perrin’s sequence even though theIandQprimes comprise5/65/6ths of all primes.A(n)(modn)A(n)\;\pmod nis easily computable inO(log⁡n)O(\log n)operations. The paper closes with ap-adic analysis. This powerful tool sets the stage for our [12] which will be Part II of the paper.

	Year	Citations

References