A recurrence relation signature is a six-term residue tuple associated with the sequence defined by
 |  |  |
(1)
|
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
for integer parameters 
and 
, with the recurrence relation
extended to all integer indices. The associated polynomial
is
 |
(5)
|
where 
is its discriminant. The Perrin
sequence is a special case corresponding to 
. For a positive integer 
,
the signature mod 
of an integer 
with respect to the sequence 
is then defined as the 6-tuple (
, 
, 
, 
, 
, 
) (mod 
). For a positive integer 
,
the following signatures are defined, with every congruence
taken modulo 
(Grantham 2001).
1. The integer 
has an S-signature if its signature (mod 
) is congruent to (
, 
, 
, 
, 
, 
).
2. The integer 
has a Q-signature if its signature (mod 
) is congruent to (
) where, for some integer 
with 
,
,
,
and 
.
3. The integer 
has an I-signature if its signature (mod 
) is congruent to (
), where 
and 
.
