In Mathematica,

Perrin[n_] := RootSum[#^3 - # - 1 &, #^n &]
PrimeQ[Perrin[581132]]

returns True

To be completed...