TL;DR
This paper refines and corrects existing algorithms for computing cube roots in finite fields, specifically addressing issues in the Padró-Sáez algorithm. The authors present a new, faster algorithm that outperforms established methods like Adleman-Manders-Miller and Cipolla-Lehmer, particularly for larger fields.
What Problem Does This Paper Address?
Finding cube roots in finite fields (denoted as $\mathbb{F}_q$, where $q$ is a prime power) is a fundamental problem in computational number theory and has applications in cryptography. While several algorithms exist, such as the Adleman-Manders-Miller (AMM) and Cipolla-Lehmer (CM) algorithms, this paper focuses on improving and correcting the Pocklington and Padró-Sáez algorithms. The authors identify and fix errors in a previous work by Padró and Sáez, and then generalize the Pocklington result. They also aim to provide a comprehensive comparison of these algorithms' practical performance.
Methods
The core of this paper involves theoretical analysis and algorithmic refinement. The authors:
- Correct Errors: They identify and rectify flaws in Proposition 3.5 of the Padró-Sáez paper, particularly concerning cases that were incorrectly assumed to be possible.
- Generalize Results: They extend the Pocklington and Padró-Sáez cube root algorithms to a more general form.
- Introduce a Refined Algorithm: Based on their corrected theoretical findings, they propose a new algorithm (Algorithm 1) that leverages ring arithmetic in $\mathbb{F}_q[X]/(X^3 - a)$, which is isomorphic to $\mathbb{F}_q \times \mathbb{F}_q \times \mathbb{F}_q$. This approach is contrasted with the Cipolla-Lehmer algorithm, which uses arithmetic in an extension field $\mathbb{F}_{q^3}$.
- Performance Comparison: They implement their proposed algorithm alongside the AMM and CM algorithms and compare their running times on prime fields of varying sizes.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithms and their performance evaluation on generated finite fields.
Key Insights and Ideas
- Subtle Errors in Existing Work: The paper highlights that even well-cited algorithms can contain subtle errors, which can have implications for their practical implementation and theoretical guarantees.
- Ring Isomorphism Advantage: The key insight is that the isomorphism $\mathbb{F}_q[X]/(X^3 - a) \cong \mathbb{F}_q \times \mathbb{F}_q \times \mathbb{F}_q$ allows for a more efficient computation of cube roots compared to algorithms relying on higher extension fields. This is because the Pocklington-Padró-Sáez approach primarily involves computing $z^{q-1}$ (or related exponents), whereas Cipolla-Lehmer involves $z^{q^2+q+1}$.
- Performance Gains: The theoretical advantage of the ring isomorphism translates into significant practical speedups, especially for larger fields.
Key Results
- Corrected Proposition: The paper provides a corrected and extended version of Proposition 3.5 from Padró-Sáez, clarifying which cases are possible and under what conditions.
- Faster Algorithm: The proposed refined algorithm (Algorithm 1) is shown to be consistently faster than the Cipolla-Lehmer algorithm and faster than the Adleman-Manders-Miller algorithm for large values of $s$ (where $q-1 = 3st$).
- Empirical Evidence: Tables 1 and 2 demonstrate concrete performance improvements. For instance, with $p \approx 2^{3000}$, the proposed algorithm achieves an average timing of 0.648 seconds, while the Cipolla-Lehmer algorithm (Williams' version) takes 0.796 seconds, representing a 20% speedup.
Limitations and Future Work
- Error Probability: While the algorithm is generally robust, there's a small error probability (approximately $1/q$) if the step of checking for invertible elements ($N(z) \neq 0$) is omitted. The authors note this is negligible for large fields.
- Quadratic Case: The paper mentions that for the quadratic case, the performance difference between the Pocklington-style algorithm and Cipolla-Lehmer is not as pronounced.
- First Comprehensive Comparison: The authors claim this is the first paper to compare implementations of these three major cube root algorithms. This suggests future work could involve further optimizations or comparisons with other algorithms.
Summary updated