On a modification of the Lucas primality test (Q6059293)

From MaRDI portal
scientific article; zbMATH DE number 7759401
Language Label Description Also known as
English
On a modification of the Lucas primality test
scientific article; zbMATH DE number 7759401

    Statements

    On a modification of the Lucas primality test (English)
    0 references
    0 references
    0 references
    0 references
    2 November 2023
    0 references
    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}\).
    0 references
    primality proving
    0 references
    Miller-Rabin primality test
    0 references
    probabilistic algorithms
    0 references
    pseudoprimes
    0 references
    Lucas algorithm
    0 references
    Fibonacci series
    0 references
    Wall-Sun-Sun hypothesis
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references