A probable prime test with very high confidence for n 34
A probable prime test with very high confidence for \(n \equiv 3\mod4\)
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.
- scientific article; zbMATH DE number 2081060
- Generalized strong pseudoprime tests and applications
- scientific article; zbMATH DE number 4049704
- scientific article; zbMATH DE number 1588470
- The generation of random numbers that are probably prime
- scientific article; zbMATH DE number 4103163
- The error probability of the Miller-Rabin primality test
- On practical aspects of the Miller-Rabin primality test
- Four primality testing algorithms
- A probable prime test with high confidence
- A probable prime test with high confidence
- A faster pseudo-primality test
- A new probabilistic primality test
- An unconditional improvement to the running time of the quadratic Frobenius test
- On practical aspects of the Miller-Rabin primality test
- scientific article; zbMATH DE number 1643943 (Why is no real title available?)
- Randomized compositeness testing with Chebyshev polynomials
- A generalization of Miller’s primality theorem
- scientific article; zbMATH DE number 4039974 (Why is no real title available?)
- scientific article; zbMATH DE number 2081060 (Why is no real title available?)
- Information Security Practice and Experience
This page was built for publication: A probable prime test with very high confidence for \(n \equiv 3\mod4\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1402367)
