A probable prime test with very high confidence for \(n \equiv 3\mod4\) (Q1402367)

The archetype of the probabilistic primality tests usually used in cryptography is the Miller-Rabin test. This test is extremely fast and guarantees the prime character of an odd number with such a small error probability as wanted. It has the drawback however that a composite number can be accepted as prime by a quarter of all possible bases. It is also possible to construct composite numbers which pass the Miller-Rabin test for any given number of bases. Other alternatives have been proposed in the literature to obtain more reliable prime tests, some of them due to the author of the present paper. In [Advances in Cryptology-Asiacrypt'01, Lect. Notes Comput. Sci. 2248, 87--106 (2001)] she analyzes the case of primes \(n\equiv 1 \bmod 4\). In the present paper, following ideas of \textit{C. Pomerance}, \textit{J. Selfridge} and {S. S. Wagstaff jun.} [Math. Comput. 35, 1003--1026 (1980; Zbl 0444.10007)] and \textit{R. Baillie} and \textit{S. S. Wagstaff jun.} [Math. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)], the author gives a new test such that a composite number \(n\equiv 3 \bmod 4\) will pass the test only with probability at most \(1/331000\), in the worst case. The drawback is a running time of about three times the running time of the Miller-Rabin test. Instead of considering only the extraction of square roots of 1, as the authors mentioned before do, the paper proposes incorporating third and four root testing conditions. It combines properties relative to the residue classes of \(n\) modulo 3 and 8. The \` Combined Test' is stated in Section 2 of the paper. The following sections discuss details and some implementation issues of the proposed test.