Generalized Strong Pseudoprime tests and applications
Pedro Berrizbeitia and T.G.Berry
Departamento de Matematicas
Universidad Simón Bolí var
Caracas, Venezuela.
email:pedrob@usb.ve, berry@usb.ve
Abstract
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 n rounds of our test do not find n ¹ ( r+1)2
composite, then n is prime with probability of error
< (2r)-n. 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.
File translated from TEX by TTH, version 2.52.
On 30 May 2000, 13:03.