Some primality tests that eluded Lucas
In the XIX century É. Lucas provided deterministic primality tests for numbers \(N\),\, where \(N\pm 1\)\, is divisible by a large power of a (small) prime \(r\), tests based on properties of the so-called Lucas sequences \(\{u_n\},\{v_n\}\)\, (linear recurring sequences of order two), see [\textit{H. C. Williams}, Édouard Lucas and primality testing. New York, NY: John Wiley \& Sons (1998; Zbl 1155.11363)]. But ``no proof were provided for these tests, and they are not correct as stated. The aim of the present paper is first ``to correct and generalize Lucas's primality tests and second ``to provide further support of Lucas's view that an investigation of (linear) recurring sequences of order 4 would yield new properties of prime numbers. Section 2 deals with the first objective, generalizing and giving correct proofs of primality tests for the Lucas's numbers \(N=Ar^n+\gamma\), \(\gamma^2=1 \) (Theorems 2.8, 2.9 and 2.10). The rest of sections are devoted to the second objective. Section 3 studies properties of the order 4 recurring sequences \(\{U_n\},\{V_n\}\), see [\textit{H. C. Williams} and \textit{R. K. Guy}, Int. J. Number Theory 7, No. 5, 1255--1277 (2011; Zbl 1237.11006)], Section 4 studies the computational complexity for computing these numbers modulo \(N\)\, and Sections 5 and 6 properties of a sequence \(\{G_n\}\)\, derived from \(\{U_n\},\{V_n\}\). Primality tests similar to Lucas's test for numbers \(N=Ar^n+ \eta\gamma_n(r)\)\, where \(\eta^2=1\)\, and \(\gamma_n(r)\)\, a solution of \(x^2\equiv -1 \bmod r^n\),\, are given in Section 7 (Theorems 7.2 and 7.4). The particular case \(r=5\)\, is treated in Theorem 7.5. The authors point out that for \(r=5\)\, another primality test is giving by \textit{P. Berrizbeitia} et al. [Theor. Comput. Sci. 297, No. 1--3, 25--36 (2003; Zbl 1048.11101)] but ``the proof techniques are much different from ours.
- scientific article; zbMATH DE number 7199615
- scientific article; zbMATH DE number 1995935
- A generalised Lucasian primality test
- Primality tests, linear recurrent sequences and the Pell equation
- Some primality conditions for N=2p^n -1
- On primes in Lucas sequences
- Explicit primality criteria for h 2ⁿ 1
- Some primality tests constructed from a cubic extension of the Lucas functions
- Testing numbers of the form N = 2kpm − 1 for primality
- scientific article; zbMATH DE number 4079505
- A cubic extension of the Lucas functions
- A generalization of Proth's theorem
- Determination of the Primality of N by Using Factors of N 2 ± 1
- scientific article; zbMATH DE number 1131675 (Why is no real title available?)
- New Primality Criteria and Factorizations of 2 m ± 1
- On Principal Ideal Testing in Totally Complex Quartic Fields and the Determination of Certain Cyclotomic Constants
- Primality test for numbers \(M\) with a large power of 5 dividing \(M^{4}-1\).
- Some extensions of the Lucas functions
- SOME FOURTH-ORDER LINEAR DIVISIBILITY SEQUENCES
- Some monoapparitic fourth order linear divisibility sequences
- Primality tests, linear recurrent sequences and the Pell equation
- A primality test for \(4Kp^n-1\) numbers
- Some extensions of the Lucas functions
- Explicit primality criteria for h 2ⁿ 1
- Generalized Lucas-Lehmer tests using Pell conics
- A cubic extension of the Lucas functions
- Lucas-Lehmer primality tests for certain prime curios
- A note on Lucas-Lehmer sequences
- Divisibity, iterated digit sums, primality tests
- scientific article; zbMATH DE number 4075155 (Why is no real title available?)
- A Note on Primality Testing Using Lucas Sequences
- scientific article; zbMATH DE number 1024039 (Why is no real title available?)
- scientific article; zbMATH DE number 1131675 (Why is no real title available?)
- scientific article; zbMATH DE number 1995935 (Why is no real title available?)
- scientific article; zbMATH DE number 2154275 (Why is no real title available?)
- On primes in Lucas sequences
- scientific article; zbMATH DE number 878900 (Why is no real title available?)
- Some primality conditions for N=2p^n -1
- scientific article; zbMATH DE number 7626419 (Why is no real title available?)
- scientific article; zbMATH DE number 7199615 (Why is no real title available?)
- Efficient computation of terms of linear recurrence sequences of any order
- Classical and Alternative Approaches to the Mersenne and Fermat Numbers
- A note on public key cryptography based on Williams-Guy functions
This page was built for publication: Some primality tests that eluded Lucas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q887438)
