Average Case Error Estimates of the Strong Lucas Test
From MaRDI portal
Abstract: Reliable probabilistic primality tests are fundamental in public-key cryptography. In adversarial scenarios, a composite with a high probability of passing a specific primality test could be chosen. In such cases, we need worst-case error estimates for the test. However, in many scenarios the numbers are randomly chosen and thus have significantly smaller error probability. Therefore, we are interested in average case error estimates. In this paper, we establish such bounds for the strong Lucas primality test, as only worst-case, but no average case error bounds, are currently available. This allows us to use this test with more confidence. We examine an algorithm that draws odd -bit integers uniformly and independently, runs independent iterations of the strong Lucas test with randomly chosen parameters, and outputs the first number that passes all consecutive rounds. We attain numerical upper bounds on the probability on returing a composite. Furthermore, we consider a modified version of this algorithm that excludes integers divisible by small primes, resulting in improved bounds. Additionally, we classify the numbers that contribute most to our estimate.
Recommendations
- Average Case Error Estimates for the Strong Probable Prime Test
- An extended quadratic Frobenius primality test with average- and worst-case error estimate
- An extended quadratic Frobenius primality test with average and worst case error estimates.
- The Rabin-Monier theorem for Lucas pseudoprimes
- Primality testing with fewer random bits
Cited in
(2)
This page was built for publication: Average Case Error Estimates of the Strong Lucas Test
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6440470)
