My own monologue about pseudoprimes

In Someone else’s conversation about Perrin pseudoprimes and subsequent comments I linked to several posts by John D. Cook and Matt McIrvin on the subject of Perrin and other recurrence sequence pseudoprimes. There’s been enough development, including my own small contribution, that I want to summarize here, although I recommend the linked posts for additional details and further information.

Let’s start with the Lucas numbers L(n), defined by:

L(0) = 2
L(1) = 1
L(n) L(n–2)+L(n–1)    n>1

The Lucas numbers have the same recurrence relation as the more well known Fibonacci numbers F(n) but use a different starting sequence. There are some important connections between the two sequences, some of which I don’t entirely understand, but it’s interesting that in terms of the Golden Ratio ɸ = (1+√5)/2, F(n) = (ɸn–(–ɸ)–n)/√5 while L(n) = (ɸn+(–ɸ)–n).

The first several Lucas numbers, along with L(n) mod n (for n>1), are:

n 0 1 2 3 4 5 6 7 8 9 10 11
L(n) 2 1 3 4 7 11 18 29 47 76 123 199
L(n) mod n 1 1 3 1 0 1 7 4 3 1

You can see that for n = 2, 3, 5, 7, and 11 — the prime numbers here — L(n) mod n = 1, while for the other values of n, L(n) mod n ≠ 1. Coincidence? Yes, and no. It can be proved that if n is prime, L(n) mod n = 1. On the other hand the converse is not true; if L(n) mod = 1n is not necessarily prime. Values of n which are composite but for which L(n) mod n = 1 are called Lucas pseudoprimes, and they are fairly few and far between. The smallest is 705, followed by 2465, 2737, and 3745. Clearly if L(n) mod = 1 is probably prime.

Now consider the Perrin numbers. They’re defined by a similar recurrence relation and a starting sequence:

P(0) = 3
P(1) = 0
P(2) = 1
P(n) = P(n–3)+P(n–2)    n>2

This sequence comes up in graph theory and was mentioned by R. Perrin in 1899. If you calculate P(n) mod you find it equals 0 when n is prime. Again, you can prove this is true for all primes. And similarly to the Lucas numbers, for most composites, P(n) mod n ≠ 0, and similarly we have Perrin pseudoprimes, which are values of n for which n is composite and P(n) mod n = 0. But the Perrin pseudoprimes are far rarer than the Lucas ones. The smallest Perrin pseudoprime is 271,441, and it was not discovered until 1982; as recently as 1996, in Scientific American, Ian Stewart was writing (incorrectly) that no Perrin pseudoprimes were yet known, and that the smallest Perrin pseudoprime had a lower bound of 15 digits. Nowadays, of course, the computing power required to find the first Perrin pseudoprimes is readily available on your desktop. The trick to doing it fast is not to try to calculate the nth Perrin number and then divide by n; these numbers get very large very quickly, too large to be handled directly by most computer languages, and the time required is long. Instead, as McIrvin discusses, it’s best to convert the computation into a matrix exponentiation mod n, which can be done in logarithmic time and involves numbers not much larger than n. There are 17 Perrin pseudoprimes less than 1 billion.

As it turns out, any linear recurrence relation like the ones behind the Lucas and Perrin numbers can be used to generate a sequence for which the nth entry modulo n is equal to a particular value if n is prime. (This arises from a generalization of Fermat’s Little Theorem.) Then you have a corresponding set of pseudoprimes, where the nth entry modulo n has that same value even though n is composite.

McIrvin set his computer searching for sequences that produce particularly few pseudoprimes, and the best he found was:

M(0) = 5
M(1) = –1
M(2) = 3
M(3) = –7
M(4) = 11
= M(n–5)–M(n–3)+M(n–2)–M(n–1)   n>4

(That initial sequence 5, –1, 3, –7, 11 may look arbitrary but in fact it’s determined by the form of the recurrence relation. Again, see the previously linked posts for more.) In this case the prime numbers satisfy M(n) mod n = n–1. Composite numbers satisfying that relation might as well be called McIrvin pseudoprimes, and the smallest of them is … (drum roll please) … 4. All right, that one is kind of small! But the second McIrvin pseudoprime is 14,791,044. It took McIrvin a while to find the third one: 143,014,853. At this point he stopped searching and I started, finding the rest of the McIrvin pseudoprimes less than 1 billion: 253,149,265; 490,434,564; 600,606,332; and 993,861,182. Seven in all, and note that of those, five are even and one is divisible by 5. The only one that’s not obviously composite is 143,014,853 = 907 x 157,679.

So if someone gives you an n in the range 2 to 999,999,999, you can compute M(n) mod n, see if it equals n–1, and thereby determine if n is prime… with a 7 / 999,999,998 chance of being wrong. And that’s only if you don’t examine the last digit of n.

4 thoughts on “My own monologue about pseudoprimes

  1. I found many other sequences with possibly enormous pseudoprimes in my search, but since my automated sweeps didn’t calculate pseudoprimes larger than about 500,000, I’d need to investigate them further to see if any of them do better than this fifth-order one.

    What makes this one particularly interesting is that it not only yields enormous pseudoprimes but also has very small coefficients in the recurrence relation (nothing with an absolute value greater than 1). For sequences of the type I was investigating, with coefficients in {-1, 0, 1}, I know that to do as well you have to go up to at least order 8.

    I had a small crisis of faith over the weekend, in that I technically haven’t proven that all sequences of the type I was investigating all generate a primality test of this sort! I found a proof by Kevin Brown on that it’s true of any sequence whose kth term is (b_0^k + b_1^k + … + b_(n-1)^k), where the numbers b are all the possibly-complex roots of the characteristic equation tr(M – bI) = 0. I *believe* that all the sequences tr(M^k) are of this type, but this is only because it’s true of every case I checked (including the Lucas numbers, the Perrin numbers and my fifth-order one). Proving it is beyond my limited linear algebra smarts, though it may not be hard if you know how (probably there is some kind of symmetry condition on how such a thing can depend on the roots).

  2. …Also, when Kevin Brown was studying these types of sequences, he was more interested in the much stronger primality test, a(cp) mod p = a(c) mod p for *all* (positive?) integers c. (The case I was investigating would just be c=1.)

    He called the composite numbers that slip through this stronger test “symmetric pseudoprimes”, and it turns out the frequency of symmetric pseudoprimes for a recurrence is related to the size of the Galois group of the characteristic polynomial, which is something I have almost no understanding of. I suspect Brown may have somewhere anticipated most of the actual theoretical thinking going on here, and for all I know he may have done the automated searches too and found the results uninteresting. When I dabble in pure mathematics, I feel some pretty strong impostor syndrome.

  3. By the way, the recurrence relation listed above is not quite right: it should be

    M(n) = M(n–5) – M(n–3) + M(n–2) – M(n–1) n>4

    It’s easy to get confused because my code uses a “signature” format that is reversed from the standard used in OEIS. I apologize for that.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s