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 v rounds of our test do not find n != (r + 1)^2 composite, then n is
prime with probability of error less than (2r)^(-v). 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.