Modular techniques with rational reconstruction improve complexity when computing over a ground ifeld such as ℚ by controlling the growth of intermediate expressions. Working modulo a single prime ∈ ℕ , one can solve the problem modulo and lift the solution to
using -adic lifting techniques, when applicable. Alternatively, computations can be done modulo several small primes 1, … , . One can then obtain a solution modulo their product 1 ⋯ using the Chinese remainder theorem. We say primes are “unlucky” when the procedure modulo is not well-defined or returns a result that is diferent from the modulo reduction of the rational output. Otherwise we say primes are “lucky.” For some applications (solving zero-dimensional polynomial systems, for instance), testing if a prime is lucky may be prohibitively expensive. However, it is often possible to bound the number of unlucky primes by proving the existence of a nonzero ∈ ℤ with all unlucky primes dividing , and bounding the height of . Using -adic lifting requires the initial prime to be lucky, with a high probability of success that is determined by an upper bound on . On the other hand, the Chinese remainder theorem requires that all primes are lucky, and to guarantee this with high probability usually requires larger primes. We report on work-in-progress that uses error correction techniques with Chinese remaindering that allows us to tolerate a few unlucky primes. Our hope is to then guarantee a high probability of success while using primes of moderate size.
We base our work on independent results from Böhm, Decker, Fieker and Pfister [
Chinese remainder theorem codes, polynomial system solving, modular algorithms
Solving algebraic problems over a ground field such as ℚ, considering only algebraic complexity (the number of base field operations) is hardly a good predictor of practical runtime: a precise analysis should take into account the size of the coeficients in the output, and the number of boolean operations throughout the execution of the algorithm.
One major challenge in such algorithms is the growth of coeficients. In many situations, we can give reasonably sharp a priori bounds on the bit size of the coeficients in the output Japan https://uwaterloo.ca/scholar/jakellio/home (J. Elliott); https://cs.uwaterloo.ca/~eschost/ (É. Schost) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR CEUR Workshop Proceedings
ceur-ws.org ISSN1613-0073 (a typical recipe being understanding them as determinants built from the input problem). Precisely, we will assume below that we know an upper bound on the height of all rational numbers appearing in the output, where in this note the height ℎ() of a rational number is the maximum of the base-2 logarithms of the absolute values of its minimal numerator and denominator. However, such insight should not be expected for intermediate results of our algorithm. As the algorithm progresses, the size of these coeficients may increase, before possibly collapsing when we reach the end result.
Modular techniques are used to avoid intermediate expression swell. They involve performing computations modulo one or several small primes (ideally, machine primes), thereby avoiding intermediate coeficient growth, the objective being to compute the requested output (typically, a set of polynomials, or a matrix thereof) modulo a certain large integer . If is large enough (precisely, if log2( ) ≥ + 1 ), rational reconstruction can then be applied coeficient-wise, in order to recover an output with rational coeficients.
On one end of the spectrum, one can consider working modulo a single prime , solve the problem modulo and lift the solution to ℤ/ ℤ , for = large enough, by means of Newton / Hensel techniques, if applicable. The obvious alternative is to compute modulo suficiently many “small” primes ( )1≤≤ and use the Chinese remainder theorem to obtain a solution modulo = 1 ⋯ .
For most problems of interest, there exist primes for which the procedure modulo is not well-defined, or returns a result that difers from the modulo reduction of the rational output; we will call these primes unlucky, and lucky otherwise. In the problems we have in mind, such as solving systems of polynomial equations, testing whether a prime is lucky may be prohibitively expensive. However, it is often possible to bound the number of unlucky primes: this is usually done by proving the existence of a nonzero ∈ ℤ such that all unlucky primes divide , and bounding the height of .
Using -adic lifting techniques, we need to ensure that the initial prime is lucky; knowing the upper bound on , we can determine what interval to pick from in order to guarantee a high probability of success, say at least 1 − for a given tolerance . For Chinese remaindering algorithms, though, the direct approach requires all primes being lucky, and guaranteeing that this is the case with probability 1 − usually requires us to use larger primes (we discuss this further below). In this short note, we report on work-in-progress that uses error correction techniques (very loosely speaking, analogues of Reed-Solomon decoding, but for rational number reconstruction), where we tolerate that a few primes return wrong results (or no results at all). Our hope is then to be able to guarantee high probability of success, while using primes of moderate size.
We base our work on recent (independent) introductions of this idea, by Böhm, Decker,
Fieker and Pfister [
The core of our discussion concerns the reconstruction of a single rational number. We also point out that in the contexts we are interested in, algorithms usually return several such numbers (typically as coeficients of polynomials), and we can often predict that all these rationals admit a small common denominator. Taking this specificity into account would lead us toward error-tolerant vector rational number reconstruction; ideally, we could hope to reduce the number of primes by up to two, but as of now, this appears to be quite challenging.
Let us first review the key result regarding Chinese remaindering for rational reconstruction in the presence of errors. We consider a sequence of prime moduli 1, … , and a rational number = /
, with > 0 . The goal is to recover from a vector ( )1≤≤ , where = mod for a certain number of lucky primes . We tolerate a number of errors or missing values (e.g., for which divides ), for which we write = ∞, for a new symbol ∞; the corresponding primes are unlucky. Consider the following integers: • = • =
∑=1 log2( ) ∑1≤≤, unlucky prime log2( ).
• is a given upper bound on the height of , that is, log2(| |), log2() ≤ Then, Pernet proved in [3, Lemma 2.5.4] that if < ( − 2 + 1)/2 , one can reconstruct given the ’s [3, Algorithm 2 p.38]. Böhm et al. proved similar results.
Although these statements are well-established, to our knowledge, the following consequences, while relatively straightforward, are new. We provide a quantitative analysis which gives explicit suficient conditions on the number of primes and their size to guarantee an arbitrary probability of success, in a model where we assume we can pick primes uniformly at random in a given interval.
Stating this result requires us to take all primes into consideration. Thus, and the upper bound are as above, and to each prime ∈ ℕ
corresponds a value () (possibly ∞); is called lucky when () =
mod and unlucky otherwise. We assume that there are finitely many unlucky primes and let be their product. In addition to the output size bound , we then need a bound such that log2( ) ≤ . Both and are problem-dependent (we discuss a few examples in the next section); once bounds on and are available, the following propositions apply. contain at least primes.
In what follows, for simplicity, given an interval Σ = { , … , 2 } , we assume that we can sample primes in Σ uniformly without replacement, as long as this interval is known to Proposition 1. Let , ,
be as above. For > 0 , let and be integers such that ≥ max(16, 16 , 16 ) and = ⌈ log42() ⌉. Select pairwise distinct primes 1, … , independently and uniformly at random from the set Σ = { , … , 2 } . Then, with probability at least 1 − , given ( ( 1), … , ( )), one can reconstruct .
Proof. Let denote the set { ∣ ∈ Σ also divides , so that in particular ∏∈ and mod = 0} , and notice that the product ∏∈ ≤ . Each prime in Σ is at least equal to , so that # ≤
log2() . On the other hand, the number of primes in Σ is at least 2 log2() that for a prime chosen at random in Σ, ℙ(| ) ≤
Now, we choose distinct primes 1, … , uniformly at random in Σ, and for = 1, … , , we let be the indicator variable defined as = { 1 if ∣ 0 otherwise, so that [ ] = ℙ( = 1) ≤ 2/ . Define further = ∑=1 , so that [ ] ≤ 2/ for any choice of distinct primes ( ) in Σ, the quantities and defined above satisfy . Now, = ∑=1 log2( ) ≥ log2( ) and = ∑1≤≤, unlucky prime log2( ) ≤ log2(2 ) . From [3, Lemma 2.5.4] as cited above, we know that the error-tolerant rational reconstruction algorithm by Markov’s inequality is at most [ ]/
(Δ/ log2(2 ) ). We deduce succeeds as soon as ≤ ( − 2 + 1)/2
, and in particular as soon as log2(2 ) ≤ Δ = ( log2( ) − 2 + 1)/2 . We will point out below that for our choice of , Δ is positive.
Then, the probability of failure is at most ℙ (log2(2 ) > Δ ) = ℙ ( > Δ/ log2(2 ) ), which ℙ(fail) ≤ (
) ( 2
2 log2(2 ) log2( ) − 2 + 1 ) ≤ 8
log2( ) log2( ) − 2 = 8 1
2 1 − log2() .
Now, take = ⌈4/ log2( )⌉, so that in particular ≥ 4 / log2( ) , and thus 2 /( log2( )) ≤ 1/2, in which case the right-most factor in the inequality above is at most 2. Besides, this choices ensures Δ > 0. To summarize, in this case, we have ℙ(fail) ≤ 16/ , and this can be made less than as soon as ≥ 16/.
It remains to verify that our interval Σ contains at least primes. We know that there are ≥ 16 and ≥ 16 , this is indeed less than or equal to /2 log2( ) . at least /2 log2( ) such primes, and that is at most 4 / log2( ) + 1 , and one checks that if will increase if we take close to zero.
Remark 2. In the context of a modular algorithm, the most important component in the cost analysis is the total time spent solving the problem modulo the primes . In rough approximation, one can assume that each such execution takes operations modulo , where is independent of . It follows that the total boolean cost is softly-linear in ∑1≤≤ log2( ) ∈ Θ( log( )).
In our construction, we have log2( ) ≤ ( log42() + 1)log2( ) = 4 + log2( ). In other words, the boolean cost involves both the output size , which is as expected, together with log2( ) , which Remark 3. Assume that we do not use error-correction. In this case, in order to be able to reconstruct , we need all primes to be lucky. With notation as in the proposition, we saw that the probability that a single prime is unlucky is at most 2/ , so when choosing primes, the probability that at least one of them is unlucky is at most 1 − (1 − ( 2
)) ≤ 2
. Assuming we choose as above, let us derive a bound on that ensures 2/ < . We proceed informally and take = 4/ log2( ) , so our inequality is satisfied when 8/( log2( )) < . Hence we require that log2( ) ≥ 8 / ; this gives ≥ (8 /) , where is the reciprocal function of ↦ log2() . This function grows like / ln() , for → ∞ , which gives asymptotically ≥ 8 /( ln(8 /)) . As expected, this is inferior to the bound given in the previous proposition.
We end this note with a quick description of possible use cases of this work.
Computing Hermite forms over ℚ[] . In [
Computing lexicographic Gröbner bases in ℚ[, ] . In [
Solving zero-dimensional systems in ℚ[ 1, … , ]. The main application we have in mind is the solution of zero-dimensional polynomial systems (by means of a data-structure known as a zero-dimensional parametrization, see [7] for a definition and references). When the complex solutions have multiplicity one, a simple form of Newton iteration is applicable [8], but without this assumption, lifting techniques are complex to analyze. In this case, a bound on the output size is available by means of the arithmetic Bézout theorem, but the unlucky primes are harder to describe. The reference [9] quantifies primes for which the number of solutions changes modulo , but further arguments are needed to control other possible degeneracies. [7] E. Schost, M. S. E. Din, Bit complexity for multi-homogeneous system solving application to polynomial minimization, Journal of Symbolic Computation 87 (2018) 176–206. [8] W. Trinks, On improving approximate results of buchberger’s algorithm by newton’s method, SIGSAM Bull. 18 (1984) 7–11. [9] C. D’Andrea, A. Ostafe, I. Shparlinski, M. Sombra, Reductions modulo primes of systems of polynomial equations and algebraic dynamical systems, Trans. Amer. Math. Soc. 371 (2019) 1169–1198.