On a modification of the Lucas primality test
Let \(F_n\) be the Fibonacci series defined by \(F_0 = 0\), \(F_1 = 1\), and \(F_{n+2} = F_n + F_{n+1}\). Set \(e(n) = (n/5)\), where \((\cdot/5)\) is the usual Legendre symbol. The classical Lucas primality test is based on the following result: If \(n > 5\), then \(F_{n-e(n)} \equiv 0 \pmod n\). In this paper, the Lucas test is improved by adding conditions similar to ones used in the Miller-Rabin test for strengthening Fermat's Little Theorem. This improved test is called the Lucas-Miller-Rabin (LMR) test. Let \(n>5\) be an odd integer and \(n - e(n) = t 2^s\), where \(t\) is odd. We say that \(n\) is LMR-prime if \(F_t \equiv 0\pmod n\), or there is an index \(i\) with \(0 \leq i \leq s\) such that \(m = t 2^i\) satisfies \(F_{m-1}+F_{m+1} \equiv 0\pmod n\). Every prime \(>5\) is a \(LMR\)-prime. The LMR test works taking an odd integer and checking if at least one of the previous conditions holds. A composite integer that passes the LMR test is called a LMR-pseudoprime. Sufficient and necessary conditions have been proved for a product of two or three primes to be a LMR-pseudoprime. Furthermore, the problem of the existence of LMR-pseudoprimes divisible by squares is connected with the Wall-Sun-Sun Hypothesis, according to which there are no primes \(p > 5\) satisfying \(F_{p-e(p)} \equiv 0 \pmod{p^2}\).
- Primality testing: variations on a theme of Lucas
- A generalised Lucasian primality test
- On Lucas's Test for the Primality of Mersenne's Numbers
- A Note on Primality Testing Using Lucas Sequences
- scientific article; zbMATH DE number 1995935
- scientific article; zbMATH DE number 1024039
- scientific article; zbMATH DE number 4075155
- Lucas-Lehmer primality tests for certain prime curios
- A new primality test for natural integers
- An intelligent choice of witnesses in the Miller-Rabin primality test. Reinforcement learning approach
- Frobenius pseudoprimes
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- On a combined primality test
- On Strong Pseudoprimes to Several Bases
- On the number of primality witnesses of composite integers
- Primality testing with Gaussian periods
- PRIMES is in P
- Probabilistic algorithm for testing primality
- Strong pseudoprimes to the first eight prime bases
- Strong pseudoprimes to twelve prime bases
This page was built for publication: On a modification of the Lucas primality test
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6059293)
