Bad witnesses for a composite number (Q6606883)

This paper provides lower and upper bounds for the arithmetic and geometric means of the number of bad witnesses for an odd composite integer \(n\)\, with regard to a particular pseudo (or probabilistic) primality test.\N\NLet us reminder that \(x\)\, is a bad witnesses for a composite \(n\)\, if the test declare that \(n\)\, is prime. In this paper the pseudo-primality test is the product of a multiple rounds of the Miller-Rabin test by a Galois test (a pseudo-primality test based on a cyclic extension of \(\mathbb{Z}/n\mathbb{Z}\),\, see [\textit{J.-M. Couveignes} and \textit{T. Ezome}, Rend. Circ. Mat. Palermo (2) 61, No. 2, 261--278 (2012; Zbl 1257.11106)]. As the authors point out the Miller-Rabin test is more efficient when \(n\)\, has many prime divisors while the Galois test is more efficient when \(n\)\, has few prime divisors.\N\NThe obtained results are synthesizes in Section 1, Theorem 1.1 (for the arithmetic mean) and Theorem 1.2 (for the geometric mean). These theorems are proven in the rest of the paper.\N\NSection 2 deals with the Galois test; 2.1 determines bounds for below and for above for the arithmetic mean of the number of bad witnesses of this test (Theorems 2.2 and 2.3) and subsection 2.3 studies the geometric mean (Theorem 2.4). \N\NFinally Section 3 proves the lower and upper bounds for the arithmetic and geometric mean in the case of the product test, see Theorem 3.1 and Theorem 3.2.