Signature (Recurrence Relation)

Let a sequence be defined by

$$A_{-1} = s$$

$$A_0 = 3$$

$$A_1 = r$$

$$A_n = rA_{n-1}-sA_{n-2}+A_{n-3}.$$

Also define the associated Polynomial

$$f(x)=x^3-rx^2+sx+1,$$

and let $\Delta$ be its discriminant. The Perrin Sequence is a special case corresponding to $A_n(0,-1)$. The signature mod $m$ of an Integer $n$ with respect to the sequence $A_k(r,s)$ is then defined as the 6-tuple ($A_{-n-1}$, $A_{-n}$, $A_{-n+1}$, $A_{n-1}$, $A_n$, $A_{n+1}$) (mod $m$).

1. An Integer $n$ has an S-signature if its signature (mod $n$) is ($A_{-2}$, $A_{-1}$, $A_0$, $A_1$, $A_2$).

2. An Integer $n$ has a Q-signature if its signature (mod $n$) is Congruent to ( $A, s, B, B, r, C$) where, for some Integer $a$ with $f(a)\equiv 0\ \left({{\rm mod\ } {n}}\right)$, $A\equiv a^{-2}+2a$, $B\equiv -ra^2+(r^2-s)a$, and $C\equiv a^2+2a^{-1}$.

3. An Integer $n$ has an I-signature if its signature (mod $n$) is Congruent to ( $r, s, D', D, r, s$), where $D'+D\equiv rs-3$ and $(D'-D)^2\equiv \Delta$.

See also Perrin Pseudoprime

References

Adams, W. and Shanks, D. ``Strong Primality Tests that Are Not Sufficient.'' Math. Comput. 39, 255-300, 1982.

Grantham, J. ``Frobenius Pseudoprimes.'' http://www.clark.net/pub/grantham/pseudo/pseudo1.ps.