Electronics Science Technology and Application

A more efffcient algorithm for Chinese remainder theorem of sparse polynomials

Mingjun Ouyang

Keystone Academy

DOI: https://doi.org/10.59429/esta.v12i4.12676

Keywords: Chinese remainder theorem; sparse polynomial; interpolation

---

Abstract

The Chinese Remainder Theorem (CRT) for polynomials is an extension of the well-known theorem in number theory, which deals with the existence and uniqueness of solutions to a system of congruences. One formulation of CRT involves recovering an unknown polynomial f given its reductions modulo a se- quence of polynomials g_i , i = 1, 2, ...,s. In the classical setting, the polynomials g_i are required to be coprime, and the sum of their degrees ∑=1 degg_i must exceed degf. In this paper, we present a sparse algorithm tailored for the case where the number of terms in f is no more than T, and the polynomials g_i have the form gi = x^pi − 1. Our algorithm demonstrates that under these conditions, the sum of the degrees of gi needs only satisfy ∑^s_i=1 degg_i ≥ O~ (T² log² D) to uniquely determine f, where degf is at most D. This smaller degree sum con- dition provides an advantage over traditional Polynomial Chinese Remainder Theorem approaches when T² log² D < D, particularly when f is sparse. Our sparse algorithm thus offers an efficient way to recover sparse polynomials.

---

References

[1] A. Arnold, M. Giesbrecht, and D. S. Roche. Sparse interpolation over finite fields via low-order roots of unity. In Proceedings of the 39th International Sym- posium on Symbolic and Algebraic Computation, ISSAC '14, page 27–34, New York, NY, USA, 2014. Association for Computing Machinery.

[2] A. Arnold, M. Giesbrecht, and D. S. Roche. Faster sparse multivariate polyno- mial interpolation of straight-line programs. Journal of Symbolic Computa- tion, 75:4–24, 2016. Special issue on the conference ISSAC 2014: Symbolic computation and computer algebra.

[3] S. Garg and . Schost. Interpolation of polynomials given by straight-line programs. Theoretical Computer Science, 410(27-29):2659–2662, 2009.

[4] M. Giesbrecht and D. S. Roche. Diversification improves interpolation. In Pro- ceedings of the 36th International Symposium on Symbolic and Algebraic Computation, ISSAC '11, page 123–130, New York, NY, USA, 2011. Asso- ciation for Computing Machinery.

[5] J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, USA, 1999.