Open AccessFinding small roots for bivariate polynomials over the ring of integers
Author(s) -
Jiseung Kim,
Changmin Lee
Publication year - 2024
Publication title -
advances in mathematics of communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.601
H-Index - 26
eISSN - 1930-5346
pISSN - 1930-5338
DOI - 10.3934/amc.2022012
Subject(s) - mathematics , modulo , polynomial , combinatorics , bivariate analysis , integer (computer science) , ring of integers , discrete mathematics , univariate , algebraic number field , mathematical analysis , multivariate statistics , statistics , computer science , programming language
In this paper, we propose the first heuristic algorithm for finding small roots for a bivariate equation modulo an ideal \begin{document}$ \mathcal{I} $\end{document} over the ring of integers \begin{document}$ \mathcal{R} $\end{document} . Existing algorithms for solving polynomial equations with size constraints only work for bivariate modular equations over integers, and univariate modular equation over number fields. Both previous algorithms use a relation between the short vector in a skillfully structured lattice and a size constrained solution. Our algorithm also follows this framework, but we additionally use a polynomial factoring algorithm over number fields to recover a 'ring' root of a bivariate polynomial equation. As a result, when an LLL algorithm is employed to find a short vector, we can recover all small roots of a bivariate polynomial modulo \begin{document}$ \mathcal{I} $\end{document} in polynomial time under some constraint.