1.0 Introduction

An ordinary pseudoprime to the base c is defined as a composite integer N such that c^N � c (mod N). (We differ slightly from the usual definition by not requiring that N be co-prime to c.) Another way of expressing this definition is to say that N is a pseudoprime relative to the polynomial f(x) = x - c iff the sum of the Nth powers of the roots of f is congruent to the sum of the first powers. In this form the definition is applicable to any monic polynomial with integer coefficients. Lucas considered this generalization in [1], observing that, if s(k) denotes the sum of the kth powers of the roots of f, we have s(np) � s(n) (mod p) for any integer n and prime p. In particular, Lucas gave the (insufficient) primality criterion s(N) � 0 (mod N) for the polynomial f(x) = x³ - x - 1. This criterion was also discussed by Perrin [2].

A stronger criterion relative to f(x) = x³ - x - 1 (and similar cubics) was given in [3] and [4], where an "acceptable composite" was defined as a composite integer N such that the six quantities s(�N), s(�(N+1)), and s(�(N-1)) satisfy certain congruence conditions (mod N). It was reported in [4] that, at least for integers up to 50(10)⁹, the congruences involving s(�(N+1)) and s(�(N-1)) were superfluous, so the test essentially consisted of the requirement s(�N) � s(�1) (mod N).

Although this "two-sided" test can easily be applied to polynomials of higher degree, it does not fully embody the primality criterion implicit in a given polynomial of degree greater than 3 (or of cubics for which the coefficient of x⁰ is not equal to �1). In general, we expect a polynomial with d distinct roots to represent d non-redundant primality conditions, one for each root.

In this paper we propose a general definition of pseudoprimes, applicable to any monic polynomial with integer coefficients. Instead of being based only on the first elementary symmetric function (i.e., the sum) of powers of the roots of f, this definition explicitly considers all of the elementary symmetric functions. Specifically, for any given monic polynomial f with integer coefficients, we define a symmetric pseudoprime relative to f as a composite integer N such that each elementary symmetric function of the Nth powers of the roots of f is congruent (mod N) to the same function of the first powers.

Part 1 of this paper gives basic definitions, nomenclature, and propositions on symmetric pseudoprimes, along with a convenient method for computing the Nth term of any dth order linear recurring sequence in log₂(N) steps, where each step requires only d(d+1)/2 full multiplications (mod N). (Most previously published general methods require d² full multiplications per step, i.e., roughly twice as many as the method used in this paper.) Part 2 illustrates these topics by applying them to selected polynomials of degrees 1 through 5.