  The strong Lucas test is a widely used probabilistic primality test in
cryptographic libraries. When combined with the Miller-Rabin primality test, it
forms the Baillie-PSW primality test, known for its absence of false positives,
undermining the relevance of a complete understanding of the strong Lucas test.
In primality testing, the worst-case error probability serves as an upper bound
on the likelihood of incorrectly identifying a composite as prime. For the
strong Lucas test, this bound is $4/15$ for odd composites, not products of
twin primes. On the other hand, the average-case error probability indicates
the probability that a randomly chosen integer is inaccurately classified as
prime by the test. This bound is especially important for practical
applications, where we test primes that are randomly generated and not
generated by an adversary. The error probability of $4/15$ does not directly
carry over due to the scarcity of primes, and whether this estimate holds has
not yet been established in the literature. This paper addresses this gap by
demonstrating that an integer passing $t$ consecutive test rounds, alongside
additional standard tests of low computational cost, is indeed prime with a
probability greater than $1-(4/15)^t$ for all $t\geq 1$. Furthermore, we
introduce error bounds for the incremental search algorithm based on the strong
Lucas test, as there are no established bounds up to date as well. Rather than
independent selection, in this approach, the candidate is chosen uniformly at
random, with subsequent candidates determined by incrementally adding 2. This
modification reduces the need for random bits and enhances the efficiency of
trial division computation further.
