Welcome to the resource topic for 2025/2083
Title:
Improvements to Lucas-sequence modular square roots and primality testing
Authors: Mike Hamburg
Abstract:Lucas sequences are a helpful tool in mathematical and cryptographic calculations, providing in particular an efficient way to exponentiate in a quotient ring R[x]/(x^2 - Px + Q). As with exponentiation in other finite rings and fields, we can use the periodic nature of these sequences to find roots of polynomials. Since they behave differently in the ring \mathbb{Z}/N depending on whether N is prime, Lucas sequences are also useful for primality testing. In this paper, we discuss improvements to Lucas-sequence algorithms for square roots and heuristic primality testing.
Our first application is modular square roots. It is straightforward to take square roots modulo primes p\equiv \{3,5,7\} mod 8. When p\equiv 1 mod 8, and especially when p-1 is divisible by many powers of 2, Müller’s algorithm and Kim-Koo-Kwon are attractive options. Both of these use Lucas sequences. Here we show how to simplify and speed up Kim-Koo-Kwon. We also show a variant on Müller’s algorithm which works even when p\equiv 3 mod 4, which would be useful if p were secret.
Our second application is heuristic primality testing. The Baillie-PSW primality test combines a strong Fermat test with a strong Lucas test. The recent Baillie-Fiori-Wagstaff variant strengthens Baillie-PSW. Here we show an improved variant, \mathtt{SuperBFPSW}, which is stronger than Baillie-Fiori-Wagstaff, but also faster than the original Ballie-PSW.
ePrint: https://eprint.iacr.org/2025/2083
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .