Fast Primality Tests for Numbers Less Than 50 ⋅10 9

From MaRDI portal





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.











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)