Repository: sympy/sympy
File: sympy/ntheory/primetest.py (Python)

Code before:
             ``(0, 0, 0)`` if we find a nontrivial divisor of ``n``.

    Examples
    ========

    >>> from sympy.ntheory.primetest import _lucas_extrastrong_params
    >>> _lucas_extrastrong_params(101)
    (12, 4, 1)
    >>> _lucas_extrastrong_params(15)
    (0, 0, 0)

    References
    ==========
    .. [1] OEIS A217719: Extra Strong Lucas Pseudoprimes
           https://oeis.org/A217719
    .. [2] https://en.wikipedia.org/wiki/Lucas_pseudoprime

    """
    for P in count(3):
        D = P**2 - 4
        j = jacobi(D, n)
        if j == -1:
            return (D, P, 1)
        elif j == 0 and D % n:
            return (0, 0, 0)
    raise ValueError("Found no Lucas parameters")


def is_lucas_prp(n):
    """Standard Lucas compositeness test with Selfridge parameters.  Returns
    False if n is definitely composite, and True if n is a Lucas probable
    prime.

    This is typically used in combination with the Miller-Rabin test.

    References
    ==========
    .. [1] Robert Baillie, Samuel S. Wagstaff, Lucas Pseudoprimes,
           Math. Comp. Vol 35, Number 152 (1980), pp. 1391-1417,
           https://doi.org/10.1090%2FS0025-5718-1980-0583518-6
           http://mpqs.free.fr/LucasPseudoprimes.pdf
    .. [2] OEIS A217120: Lucas Pseudoprimes
           https://oeis.org/A217120
    .. [3] https://en.wikipedia.org/wiki/Lucas_pseudoprime

    Examples
    ========

    >>> from sympy.ntheory.primetest import isprime, is_lucas_prp
    >>> for i in range(10000):
    ...     if is_lucas_prp(i) and not isprime(i):

Review comment (suggestion):
The main thing to do here is to add an explicit type annotations to the functions rather than adding code so that a type checker infers the types.

Code after:

    Returns
    =======

    D, P, Q: "extra strong" parameters.
             ``(0, 0, 0)`` if we find a nontrivial divisor of ``n``.

    Examples
    ========

    >>> from sympy.ntheory.primetest import _lucas_extrastrong_params
    >>> _lucas_extrastrong_params(101)
    (12, 4, 1)
    >>> _lucas_extrastrong_params(15)
    (0, 0, 0)

    References
    ==========
    .. [1] OEIS A217719: Extra Strong Lucas Pseudoprimes
           https://oeis.org/A217719
    .. [2] https://en.wikipedia.org/wiki/Lucas_pseudoprime

    """
    for P in count(3):
        D = P**2 - 4
        j = jacobi(D, n)
        if j == -1:
            return (D, P, 1)
        elif j == 0 and D % n:
            return (0, 0, 0)
    return (0, 0, 0)

def is_lucas_prp(n: SupportsIndex) -> bool:
    """Standard Lucas compositeness test with Selfridge parameters.  Returns
    False if n is definitely composite, and True if n is a Lucas probable
    prime.

    This is typically used in combination with the Miller-Rabin test.

    References
    ==========
    .. [1] Robert Baillie, Samuel S. Wagstaff, Lucas Pseudoprimes,
           Math. Comp. Vol 35, Number 152 (1980), pp. 1391-1417,
           https://doi.org/10.1090%2FS0025-5718-1980-0583518-6
           http://mpqs.free.fr/LucasPseudoprimes.pdf
    .. [2] OEIS A217120: Lucas Pseudoprimes
           https://oeis.org/A217120
    .. [3] https://en.wikipedia.org/wiki/Lucas_pseudoprime

    Examples
    ========