Generalized Strong Pseudoprime Tests and Applications

We describe probabilistic primality tests applicable to integers whose prime factors are all congruent to 1 mod r where r is a positive integer;r = 2 is the Miller–Rabin test. We show that if ν rounds of our test do not find n ≠ = (r + 1)2composite, then n is prime with probability of error less than (2 r) − ν. Applications are given, first to provide a probabilistic primality test applicable to all integers, and second, to give a test for values of cyclotomic polynomials.