Congruences on 4th Order Recurrences

Given a fourth order linear recurrence relation for which the 
resolvant cubic of the characteristic polynomial has a rational 
root, it's possible to derive explicit congruence conditions 
(mod p) for the p-th terms of the solution sequence.  For example, 
consider the sequence of integers given by the recurrence formula

            s(n) = 2s(n-1) - 4s(n-3) - 2s(n-4)

with the arbitrarily chosen initial values s(0)=s(1)=s(2)=s(3)=1.
Notice that s(31) equals 1107179136 which is divisible by 31.  It 
can be shown that 31 is the ONLY prime p for which s(p) is divisible 
by p.  

More generally, we can find all the primes p such that s(p) is 
congruent to some particular value, say 6000, modulo p.  For 
this sequence it turns out that s(p) = 6000 (mod p) if and only 
if p is one of the five primes 29, 857, 1291, 36012017, or 58461031.

Using the recurrence formula defined above but with the new initial 
values s(0)=37, s(1)=19, s(2)=43, and s(3)=101, suppose I have an 
encryption system and the key is known to be the largest prime p 
such that s(p)=5000 (mod p).  How difficult would it be for someone 
to determine the key?