Title: From Worst to Average Case to Incremental Search Bounds of the Strong Lucas Test Show Chinese title

Title: 从最坏情况到平均情况再到增量搜索的强卢卡斯测试边界

Abstract: 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. Show Chinese abstract

Abstract: 强Lucas测试是一种在密码库中广泛使用的概率素性测试。 当与Miller-Rabin素性测试结合时，它形成了Baillie-PSW素性测试，该测试以没有假阳性而著称，这削弱了完全理解强Lucas测试的相关性。 在素性测试中，最坏情况下的错误概率作为将合数错误识别为素数的可能性的上界。 对于强Lucas测试，这个界限是$4/15$，适用于奇合数，不包括孪生素数的乘积。 另一方面，平均情况下的错误概率表示随机选择的整数被测试错误地分类为素数的概率。 这个界限对于实际应用尤其重要，在实际应用中，我们测试的是随机生成的素数，而不是由对手生成的素数。 $4/15$的错误概率不能直接转移，因为素数数量稀少，且该估计是否成立尚未在文献中得到证实。 本文通过证明通过$t$次连续测试轮次，并结合其他计算成本低的标准测试，该整数实际上是素数的概率大于$1-(4/15)^t$，从而弥补了这一空白，对所有$t\geq 1$而言。 此外，由于目前尚无已建立的界限，我们还引入了基于强Lucas测试的增量搜索算法的误差界限。 在此方法中，候选数是均匀随机选择的，后续的候选数通过逐步增加2来确定。 这种修改减少了对随机位的需求，并进一步提高了试除法计算的效率。