A compositeness test based on modified Dickson polynomials
by
Paul Thomas Young
University of Charleston, S. C.

The usual Dickson polynomial compositeness test is based on the congruence D_n(b, a) \equiv b (mod n); it is well known that this congruence is satisfied for all integers a, b when n is a prime. A composite integer n which satisfies this congruence for a fixed value of a and all b is called a strong Dickson pseudoprime to the base a; a number which is a strong Dickson pseudoprime to every base a with (a, n)=1 is called a superstrong Dickson pseudoprime.

In this talk I will propose a compositeness test based on the modified Dickson polynomials which were introduced by P. Filipponi. We'll see how this test contains the usual Dickson polynomial test as a special case, but has the advantage of admitting no strong pseudoprimes to any base.

Date received: April 6, 2000