A faster pseudo-primality test (Q1758643)

Probabilistic primality tests provide efficient algorithms to find the huge primes needed in cryptographic applications. Miller-Rabin test, see [\textit{M. O. Rabin}, J. Number Theory 12, 128--138 (1980; Zbl 0426.10006)], is the archetype of these tests. The primality test proposed in the current paper is the product of some rounds of the Miller-Rabin test and a Galois test. Section 1 gives (theorem 2) a compositeness criterion based on \(\mathbb{Z}/n\mathbb{Z}\)-\, algebras \(S\)\, and its associated primality test (with the group \(S^*\)\, of units of \(S\)\, as the set of witnesses). In the following the paper supposes \(S\)\, to be a cyclic Galois extension of \(\mathbb{Z}/n\mathbb{Z}\)\, and theorem 3, Section 2, provides an upper bound for the density of bad witnesses. Section 3 describes the proposed test while Section 4 shows how to construct the required algebra \(S\). Section 5 discusses some implementation issues and proves theorem 1 which gives the running time and error probability of the test. Finally Section 6 shows details of an implementation in MAGMA V2. 18.2 for integers of binary length from 1024 to 8192 bits.