Extensions in the theory of Lucas and Lehmer pseudoprimes

We begin by briefly explaining the applications and history of primality testing. Chapter 1 surveys the number theory topics that are essential to the study with motivation where possible. After summarizing the current literature in Chapter 2, the remainder of the dissertation extends known research and investigates new ideas in probabilistic primality testing based on Lucas and Lehmer sequences by both theoretical and numerical means.;First, we define Lehmer sequences and give four congruence relations for these sequences which are satisfied by all primes. For given parameters, each congruence gives a probabilistic primality test in which all primes pass the test, but some composites, called pseudoprimes, also pass. For an odd composite integer n with the discriminant of the sequence fixed, we give the number of parameters that yield n as a pseudoprime for Congruence 1 of Chapter 3. Using this formula, we deduce a bound on the number of parameters that yield n as a pseudoprimes. With further results in Chapter 6, we are able to give a count and bound on all parameter sets for all discriminants. In Chapter 4, we explore ways to systematically reduce the number of pseudoprimes exhibited by Congruences 1 and 2 of Chapter 3.;Primality testing based on congruence relations with modulus n2 instead of n are investigated in Chapter 5. We motivate this change and give several such relations. Extensive numerical tables are given for the number of pseudoprimes up to x = 10k for various congruences and methods in Chapters 3, 4, and 5.;By analyzing the characteristic roots of Lehmer sequences in Chapter 6, we are able to give several relationships between parameters sets for congruence relations of previous chapters. We use these relationships to help explain the effectiveness, or ineffectiveness, of specific congruences and methods.;In the final chapter, we consider Lucas and Lehmer sequences where the parameters are taken in the general setting of commutative rings with identity. Much of the theory and results also hold in this setting. We also look at the special case of quotient rings.