FROBENIUS PSEUDOPRIMES

Jon Grantham

July 16, 1998

Abstract. The proliferation of probable prime tests in recent years has produced a plethora of definitions with the word “pseudoprime” in them. Examples include pseudoprimes, Euler pseudoprimes, strong pseudoprimes, Lucas pseudoprimes, strong Lucas pseudoprimes, extra strong Lucas pseudoprimes and Perrin pseudoprimes. Though these tests represent a wealth of ideas, they exist as a hodge-podge of definitions rather than as examples of a more general theory. It is the goal of this paper to present a way of viewing many of these tests as special cases of a general principle, as well as to re-formulate them in the context of finite fields.

One aim of the reformulation is to enable the creations of stronger tests; another is to aid in proving results about large classes of pseudoprimes.

§1 Introduction

Fermat’s Little Theorem tells us that a^{p−1} ≡ 1 mod p for p an odd prime; thus we have an easy way to prove that many numbers are composite. For example, since 2^{90} ≡ 64 mod 91, we prove that 91 is composite. The technique of repeated squaring can be used to perform the required exponentiation very rapidly.

This test is not foolproof. n particular, 2^{340} ≡ 1 mod 341. Composites which fool the test with a = 2 are called pseudoprimes, and in general, composites n with a^{n−1} ≡ 1 mod n are pseudoprimes to the base a.

The existence of such numbers provides incentive to create other tests which are similarly fast, but which may have fewer, or at least different, “pseudoprimes.” Two of these tests are more elaborate versions of the test described above and create the notions of Euler pseudoprime and strong pseudoprime.

Most other tests, however, involve recurrence sequences. One reason that pseudoprimes based on recurrence sequences have attracted interest is that the pseudoprimes for these sequence are often different from ordinary pseudoprimes. In fact, nobody has claimed the $620 offered for a Lucas pseudoprime with parameters (1, −1) (see §2 for a definition of this term), congruent to 2 or 3 mod 5, that is also a pseudoprime to the base 2 [22, 14].

Furthermore, some tests based on higher order recurrence sequences seem to have few pseudoprimes. Adams and Shanks [2] introduced such a test based on a third order recurrence sequence known as Perrin’s sequence.

A problem with tests based on recurrence sequences is that analysis of the tests can be difficult. For example, the concepts of Lucas and Lehmer pseudoprimes have

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11Y11.

been analyzed separately in the literature. In §2, we show that they are equivalent definitions. Instead of recurrence sequences, the language used in this paper is that of finite

fields. In particular, when n is a prime, f(x) ∈ ℤ[x], and n does not divide disc(f), the residue ring ℤ[x]/(n, f(x)) is a product of finite fields of characteristic n. When n is composite, this ring is not equal to such a product. For a given composite n, this fact is often easy to discover, thus providing a quick proof of the compositeness of n. Using properties of finite fields, we establish the definition of Frobenius probable prime, which is a generalization, and sometimes a strengthening, of many existing definitions.

We introduce the concept of Frobenius pseudoprimes, not to inict a new and different notion of pseudoprimality on the mathematical world, but to show that many existing pseudoprimality tests can be generalized and described in terms of finite fields. In fact, we show that some specific instances of the Frobenius pseudoprime test are equivalent to other pseudoprimality tests, and stronger than many of them.

In [11], we use the structure given by the introduction of finite fields to show that the probability of error in declaring a number “prime” using a certain Frobenius test is less than \frac{1}{7710}. In 1980, Monier [19] and Rabin [23] proved that the Strong Probable Prime Test has probability of error at most \frac{1}{4}. Although the test introduced in [11] has asymptotic running time three times that of the Strong Probable Prime Test, the proven bound on the error is much smaller than the \frac{1}{64} achieved through three Strong Probable Prime Tests.

Perhaps the primary benefit of this approach is that instead of having to prove ten different theorems about ten different types of pseudoprimes, one can prove one theorem about Frobenius pseudoprimes and apply it to each type of pseudoprime.

In [12], the techniques of [3] are used to prove that for any monic, squarefree polynomial, there are infinitely many Frobenius pseudoprimes. In particular, this theorem answers a 1982 conjecture of Adams and Shanks [2] that there are infinitely many Perrin pseudoprimes. It also proves the infinitude of the types of pseudoprimes defined by Gurak [13] and Szekeres [27].

We should note that the idea of primality testing in finite fields is not entirely new. Lenstra’s Galois Theory Test [17] is a method of proving primality using finite fields. In [10], I describe the relation between the two ideas. The combination of finite fields and pseudoprimes also exists implicitly in some other works, such as [27]. The goal here, however, is different. I am trying to provide a clear theoretical framework in which various existing probable prime tests can be generalized and analyzed.

§2 A Wealth of Pseudoprimes

For the purposes of this paper, the following test for primality will be considered foolproof. If an integer is denoted by the letter p, then p is prime. If q is a prime power, we let 𝔽_{q} denote a finite field with q elements.

We begin by reviewing many of the existing notions of pseudoprimality. Each of these definitions of “pseudoprime” characterizes composite numbers with a certain property. In each of these cases, it can be proven that all prime numbers (with a finite, known set of exceptions) have this property.