From Worst to Average Case to Incremental Search Bounds of the Strong Lucas Test

Semira Einsele, Gerhard Wunder

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 primali…