Generalized Strong Pseudoprime Tests and Applications |
| |
Affiliation: | Departamento de Matematicas, Universidad Simón Bol?́var, Caracas, Venezuela |
| |
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 ν 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|