  The calculation of many and large Perrin pseudoprimes is a challenge. This is
mainly due to their rarity. Perrin pseudoprimes are one of the rarest known
pseudoprimes. In order to calculate many such large numbers, one needs not only
a fast algorithm but also an idea how most of them are structured to minimize
the amount of numbers one have to test. We present a quick algorithm for
testing Perrin pseudoprimes and develop some ideas on how Perrin pseudoprimes
might be structured. This leads to some conjectures that still need to be
proved. We think that we have found well over 90% of all 20-digit Perrin
pseudoprimes. Overall, we have been able to calculate over 9 million Perrin
pseudoprimes with our method, including some very large ones. The largest
number found has 3101 digits. This seems to be a breakthrough, compared to the
previously known just over 100,000 Perrin pseudoprimes, of which the largest
have 20 digits. In addition, we propose two new sequences that do not provide
any pseudoprimes up to $10^9$ at all.
