info prev up next book cdrom email home

Signature (Recurrence Relation)

Let a sequence be defined by

$\displaystyle A_{-1}$ $\textstyle =$ $\displaystyle s$  
$\displaystyle A_0$ $\textstyle =$ $\displaystyle 3$  
$\displaystyle A_1$ $\textstyle =$ $\displaystyle r$  
$\displaystyle A_n$ $\textstyle =$ $\displaystyle rA_{n-1}-sA_{n-2}+A_{n-3}.$  

Also define the associated Polynomial

\begin{displaymath}
f(x)=x^3-rx^2+sx+1,
\end{displaymath}

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.




© 1996-9 Eric W. Weisstein
1999-05-26