Fast Primality Tests for Numbers Less Than 50 ⋅10 9
This paper is concerned with a fast primality test for the positive integers less than 50 \(\times 10^ 9\) [it is a sequel to the paper of \textit{W. Adams} and \textit{D. Shanks}, ibid. 39, 255-300 (1982; Zbl 0492.10005), which presents the theoretical background for the work under review]. The test is based on divisibility properties of sequences generated by certain cubic recurrences. The amount of work to test n is O(log n). Any prime less than 50 \(\times 10^ 9\) passes this test, and there are only 55 composite numbers less than 50 \(\times 10^ 9\) which also pass this test. These 55 numbers are tabulated in the paper. For those who want to avoid a table look-up in their computer implementation of the test, a second test is given, which has the property that none of the 55 above numbers passes this second test. Some suggestions are given for further computational work, related to this interesting paper.
- An $O(n^{1/10.89))$ Primality Testing Algorithm,$
- scientific article; zbMATH DE number 4215363
- A faster pseudo-primality test
- A Fast Monte-Carlo Test for Primality
- New fast methods to compute the number of primes smaller than a given value
- Proving the primality of very large numbers with fastECPP
- Fast compact prime number sieves (among others)
- scientific article; zbMATH DE number 1331127
- Infinite Sets of Primes with Fast Primality Tests and Quick Generation of Large Primes
- scientific article; zbMATH DE number 5845877
- Frobenius pseudoprimes
- An \(\tilde{O}(\log^{2}(N))\) time primality test for generalized Cullen numbers
- The Primality of R1031
- Primes at a Glance
- On the Number of Elliptic Pseudoprimes
- A Fast Monte-Carlo Test for Primality
- scientific article; zbMATH DE number 1210365 (Why is no real title available?)
- scientific article; zbMATH DE number 647571 (Why is no real title available?)
- scientific article; zbMATH DE number 1406839 (Why is no real title available?)
- Extending Babbage's (non-)primality tests
- On Almost Primes
This page was built for publication: Fast Primality Tests for Numbers Less Than 50 ⋅10 9
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3724396)