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