Enum LucasCheck

pub enum LucasCheck {
    Strong,
    AlmostExtraStrong,
    ExtraStrong,
    LucasV,
}

The checks to perform in the Lucas test.

Given the Lucas sequence built from some base (P, Q) (see LucasBase) up to the elements V(d), U(d), where d * 2^s == n - (D/n), d odd, and D = P^2 - 4Q, the checks are defined as follows:

Variants

Strong

Introduced by Baillie & Wagstaff¹. If either of the following is true:

• any of V(d*2^r) == 0 for 0 <= r < s,
• U(d) == 0,

report the number as prime.

If the base is SelfridgeBase, known false positives constitute OEIS:A217255².

R. Baillie, S. S. Wagstaff, “Lucas pseudoprimes”, Math. Comp. 35 1391-1417 (1980), DOI: 10.2307/2006406, http://mpqs.free.fr/LucasPseudoprimes.pdf

---

1.  ↩

2. https://oeis.org/A217255 ↩

AlmostExtraStrong

A LucasCheck::ExtraStrong without checking for U(d). That is, if either of the following is true:

• any of V(d*2^r) == 0 for 0 <= r < s,
• V(d) == ±2,

report the number as prime.

Note: the second condition is only checked if Q == 1, otherwise it is considered to be true.

If the base is BruteForceBase, some known false positives are listed by Jacobsen¹.

Note: this option is intended for testing against known pseudoprimes; do not use unless you know what you are doing.

D. Jacobsen, “Pseudoprime Statistics, Tables, and Data”, http://ntheory.org/pseudoprimes.html

---

1.  ↩

ExtraStrong

Introduced by Mo¹, and also described by Grantham². If either of the following is true:

• any of V(d*2^r) == 0 for 0 <= r < s,
• U(d) == 0 and V(d) == ±2,

report the number as prime.

Note that this check only differs from LucasCheck::Strong if Q == 1.

If the base is BruteForceBase, known false positives constitute OEIS:A217719³.

Zhaiyu Mo, “Diophantine equations, Lucas sequences and pseudoprimes”, graduate thesis, University of Calgary, Calgary, AB (1993) DOI: 10.11575/PRISM/10820

J. Grantham, “Frobenius pseudoprimes”, Math. Comp. 70 873-891 (2001), DOI: 10.1090/S0025-5718-00-01197-2

---

1.  ↩
2.  ↩

3. https://oeis.org/A217719 ↩

LucasV

Introduced by Baillie et al¹. If V(n+1) == 2 Q, report the number as prime.

If the base is AStarBase, some known false positives are provided by Baillie et al¹.

---

1. R. Baillie, A. Fiori, S. S. Wagstaff, “Strengthening the Baillie-PSW primality test”, Math. Comp. 90 1931-1955 (2021), DOI: 10.1090/mcom/3616 ↩

Trait Implementations

impl Clone for LucasCheck

fn clone(&self) -> LucasCheck

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for LucasCheck

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for LucasCheck

fn eq(&self, other: &LucasCheck) -> bool

Tests for self and other values to be equal, and is used by ==.

const fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for LucasCheck

impl Eq for LucasCheck

impl StructuralPartialEq for LucasCheck