=Paper= {{Paper |id=Vol-3754/paper03 |storemode=property |title=Some applications of Chinese Remainder Theorem codes with error-correction |pdfUrl=https://ceur-ws.org/Vol-3754/paper03.pdf |volume=Vol-3754 |authors=Jesse Elliott,Eric Schost |dblpUrl=https://dblp.org/rec/conf/sycss/ElliottS24 }} ==Some applications of Chinese Remainder Theorem codes with error-correction== https://ceur-ws.org/Vol-3754/paper03.pdf

Some Applications of Chinese Remainder Theorem
Codes with Error-Correction
Jesse Elliott1 , Éric Schost1
1
University of Waterloo, David R. Cheriton School of Computer Science, Waterloo, Ontario, Canada

Abstract
Modular techniques with rational reconstruction improve complexity when computing over a ground
field 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 ℤ/𝑝 𝑘 ℤ for sufficiently large 𝑝 𝑘 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 different 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 [1, 2] and Pernet [3].
To our knowledge, the consequences we derive, while relatively straightforward, are new. We give
explicit sufficient conditions on the number of primes and their size to guarantee an arbitrary probability
of success, assuming we can pick primes uniformly at random in a given interval. We also describe a
number of applications.

Keywords
Chinese remainder theorem codes, polynomial system solving, modular algorithms

1. Background and previous work
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 coefficients 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 coefficients. In many situations,
we can give reasonably sharp a priori bounds on the bit size of the coefficients in the output

SCSS 2024: 10th International Symposium on Symbolic Computation in Software Science, August 28–30, 2024, Tokyo,
Japan
Envelope-Open jakellio@uwaterloo.ca (J. Elliott); eschost@uwaterloo.ca (É. Schost)
GLOBE 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
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)

CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings

13
(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 coefficients 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 coefficient 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 coefficient-wise, in
order to recover an output with rational coefficients.
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 sufficiently
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 differs 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 [1, 2] and Pernet [3], the former in the context of algorithms for algebraic
geometry, and the latter mentioning applications to linear algebra. The decoding algorithms and
the sufficient conditions for success given in these two families of references are distinct, but
similar; both follow an iterative reduction procedure, stated as a variant of Euclid’s algorithm
in Pernet’s work, and as a variant of Gaussian lattice reduction by Böhm et al. Our presentation
will follows Pernet’s.
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

14
numbers (typically as coefficients 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.

2. Our contribution
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 conse-
quences, while relatively straightforward, are new. We provide a quantitative analysis which
gives explicit sufficient 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.
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
contain at least 𝜂 primes.

Proposition 1. Let 𝑟, 𝐻 , 𝐶 be as above. For 𝜖 > 0, let 𝜎 and 𝜂 be integers such that 𝜎 ≥
max(16, 16𝐶
𝜖
, 16𝐻 ) and 𝜂 = ⌈ log4𝐻(𝜎) ⌉. Select pairwise distinct primes 𝑝1 , … , 𝑝𝜂 independently
2
and uniformly at random from the set Σ = {𝜎 , … , 2𝜎 }. Then, with probability at least 1 − 𝜖, given
(𝑟(𝑝1 ), … , 𝑟(𝑝𝜂 )), one can reconstruct 𝑟.

Proof. Let 𝒟 denote the set {𝑝 ∣ 𝑝 ∈ Σ and 𝑈 mod 𝑝 = 0}, and notice that the product ∏𝑝∈𝒟 𝑝
also divides 𝑈, so that in particular ∏𝑝∈𝒟 𝑝 ≤ 𝑈. Each prime in Σ is at least equal to 𝜎, so that

15
#𝒟 ≤ log𝐶(𝜎) . On the other hand, the number of primes in Σ is at least 2 log𝜎 (𝜎) [4, Ex. 18.18], so
2 2
(𝐶/ log (𝜎))
that for a prime 𝑝 chosen at random in Σ, ℙ(𝑝|𝑈 ) ≤ (𝜎/(2 log2 (𝜎))) = 2𝐶
𝜎
.
2
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𝜂𝐶/𝜎. Now,
for any choice of 𝜂 distinct primes (𝑝𝑖 ) in Σ, the quantities 𝑁 and 𝐿 defined above satisfy
𝜂
𝑁 = ∑𝑖=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
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
by Markov’s inequality is at most 𝔼[𝑋 ]/ (Δ/ log2 (2𝜎 )). We deduce

2𝜂𝐶 2 log2 (2𝜎 ) 8𝐶 𝜂 log2 (𝜎 ) 8𝐶 1
ℙ(fail) ≤ ( )( )≤ = .
𝜎 𝜂 log2 (𝜎 ) − 2𝐻 + 1 𝜎 𝜂 log2 (𝜎 ) − 2𝐻 𝜎 1 − 2𝐻
𝜂 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
at least 𝜎 /2 log2 (𝜎 ) such primes, and that 𝜂 is at most 4𝐻 / log2 (𝜎 ) + 1, and one checks that if
𝜎 ≥ 16 and 𝜎 ≥ 16𝐻, this is indeed less than or equal to 𝜎 /2 log2 (𝜎 ).

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 (𝜎 ) ≤ ( log4𝐻(𝜎) + 1) log2 (𝜎 ) = 4𝐻 + log2 (𝜎 ). In other words,
2
the boolean cost involves both the output size 𝐻, which is as expected, together with log2 (𝜎 ), which
will increase if we take 𝜖 close to zero.

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

2𝐶 𝜂 2𝜂𝐶
1 − (1 − ( )) ≤ .
𝜎 𝜎

16
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.

3. Applications
We end this note with a quick description of possible use cases of this work.

Computing Hermite forms over ℚ[𝑥]. In [5], Storjohann gives a modular algorithm to
compute Hermite forms for matrices with entries in ℚ[𝑥], together with bounds 𝐻 on the output
size and 𝐶 on the unlucky primes. Our work applies directly to this situation. We are not aware
of alternative methods that would rely on Newton iteration.

Computing lexicographic Gröbner bases in ℚ[𝑥, 𝑦]. In [6], St-Pierre and Schost provide
similar bounds 𝐻 and 𝐶 for the computation of bivariate Gröbner bases; again, our work applies
directly. In this case, an alternative approach based on Newton iteration exists, but has rather
high complexity.

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.

References
[1] J. Böhm, W. Decker, C. Fieker, G. Pfister, The use of bad primes in rational reconstruction,
Math. Comput. 84 (2012) 3013–3027.
[2] J. Böhm, W. Decker, C. Fieker, S. Laplagne, G. Pfister, Bad primes in computational algebraic
geometry, in: Mathematical Software – ICMS 2016, Springer, 2016, pp. 93–101.
[3] C. Pernet, High Performance and Reliable Algebraic Computing, HDR, Université Joseph
Fourier, Grenoble 1, 2014. URL: https://theses.hal.science/tel-01094212.
[4] J. von zur Gathen, J. Gerhard, Modern Computer Algebra, third ed., Cambridge University
Press, 2013.
[5] Storjohann, A., Computation of Hermite and Smith Normal Forms of Matrices, Master’s
thesis, University of Waterloo, 1994.
[6] E. Schost, C. St-Pierre, p-adic algorithm for bivariate gröbner bases, in: ISSAC’23, ACM,
2023, p. 508–516. doi:10.1145/3597066.3597086 .

17
[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.