TL;DR
This paper introduces a probabilistic algorithm to compute the greatest common divisor (GCD) of polynomials more efficiently. It tackles a known issue in polynomial GCD computation where intermediate results can grow excessively large, by proposing a method to correctly determine a crucial variant (τ) that helps manage coefficient growth, achieving high accuracy in most cases.
What Problem Does This Paper Address?
The Euclidean algorithm is a cornerstone for finding the greatest common divisor (GCD) of polynomials. However, when working with polynomials over integers (Z[x]), a naive application of the Euclidean algorithm, or even its improved versions like the subresultant algorithm, can lead to a dramatic increase in the size of the coefficients of the intermediate polynomials. This phenomenon, known as coefficient growth, can make computations computationally expensive and impractical.
Previous work by Knuth and Brown attempted to mitigate this by introducing subresultant algorithms and variants. Knuth's subresultant algorithm aimed to reduce coefficient growth, but the resulting polynomials could still contain small, removable factors. Brown's subsequent work introduced a variant (τ) to address this, but his method for determining τ wasn't always correct. This leaves a gap in efficiently computing polynomial GCDs while keeping intermediate coefficients manageable, especially for applications like lattice-based cryptography which rely on these computations.
Methods
The core of this paper is a probabilistic algorithm designed to correctly determine the variant τ in the context of polynomial GCD computation. The authors build upon existing subresultant algorithms and introduce a new approach to compute τ. Instead of directly computing a potentially problematic term t(x), their method involves adding a few steps to determine τ.
Key aspects of their approach include:
- Leveraging Subresultant Polynomial Remainder Sequences (PRS): The algorithm is rooted in the theory of subresultant PRS, which are sequences of polynomials generated during a modified Euclidean algorithm designed to control coefficient growth.
- Probabilistic Determination of τ: The novelty lies in how they handle the variant τ. Rather than a deterministic calculation that might fail, they employ a probabilistic approach that is highly likely to yield the correct τ. This involves analyzing the relationship between the leading coefficients and contents of intermediate polynomials.
- Focus on Primitive Polynomial Remainder Sequences (PPRSOL): The ultimate goal is to obtain PPRSOLs, which are remainders from the Euclidean algorithm that are "primitive" (no common factors) and have minimal coefficients. Their probabilistic algorithm aims to achieve this.
- Algorithm 3 (Probabilistic Subresultant Algorithm): This algorithm outlines the steps for computing the probabilistic subresultant PRS. It involves iterative pseudo-division and a specific method for calculating and applying the variant τ.
Datasets
Not discussed in the paper. The paper focuses on theoretical algorithm development and provides experimental results for specific, commonly used polynomials in ideal lattice-based cryptography.
Key Insights and Ideas
- The "variant τ" is crucial for controlling coefficient growth: The paper highlights that correctly determining this variant is key to making polynomial GCD computations efficient, especially when dealing with integer coefficients.
- Probabilistic methods can be effective for difficult deterministic problems: The authors demonstrate that a probabilistic approach can overcome the limitations of deterministic methods for finding τ, achieving high accuracy in practice.
- Managing intermediate coefficient size is critical for practical polynomial algebra: The persistent challenge of coefficient growth underscores the need for sophisticated algorithms like subresultant PRS, particularly for applications requiring precise polynomial arithmetic.
- Connection to Ideal Lattice Cryptography: The paper explicitly links the problem of polynomial GCD computation to its importance in constructing ideal lattice-based cryptosystems, motivating the need for efficient algorithms.
Key Results
The paper proposes a probabilistic subresultant algorithm that computes polynomial GCDs and outputs correct remainders with high probability.
Experimental results are presented for two common polynomials used in ideal lattice-based cryptography:
- For $x^n + 1$, the algorithm achieved 97.88% correctness.
- For $x^n - x - 1$, the algorithm achieved 99.73% correctness.
These results suggest that the probabilistic approach is effective in practice, though not entirely deterministic.
Limitations and Future Work
The authors acknowledge that their proposed algorithm is not deterministic. The probabilistic nature means there's a small chance of failure in determining the variant τ correctly.
Future work will focus on:
- Exact expression of τᵢ: Finding a precise mathematical expression for the variant τᵢ.
- Relationship between lc(tᵢ) and cont(rᵢ(x)): Further investigating the connection between the leading coefficient of a polynomial tᵢ and the content of a remainder rᵢ(x).
- Deterministic Improved Subresultant Algorithm: The ultimate goal is to leverage these insights to develop a deterministic algorithm that guarantees correct results for all cases.
Summary updated