(2026-03) Coppersmith's Method for Solving Modular Inversion Hidden Number Problem via Determinant-Based Elimination
2026-03-02
The selection of shift polynomials is a pivotal yet challenging step in Coppersmith's method for computing modular roots of multivariate polynomials. We propose a novel, determinant-based strategy for generating these polynomials, thereby presenting an improved variant of Coppersmith's method tailored for certain multivariate modular equations. Our approach is first validated on solving the Modular Inversion Hidden Number Problem (MIHNP) and predicting the Inversive Congruential Generator (ICG), where it is shown to outperform prior methods both in theory and in practice. Furthermore, when applied to the Modular Inversion Double Hidden Numbers Problem (MIDHNP), our analysis reveals that MIDHNP is not harder than MIHNP, thereby disproving a conjecture by Boneh et al. (Asiacrypt 2001).