Computing Asymptotic Bounds for the Automated Coppersmith Method via Linear Programming

본문 미리보기

Coppersmith's method is a foundational technique for finding small roots of modular equations, and determining asymptotic bounds for the recoverable roots is a central and challenging part of its analysis. In this paper, we transform the computation of asymptotic bounds for the Automated Coppersmith method, proposed by Meers and Nowakowski (ASIACRYPT 2023), into a linear programming problem, thereby obtaining a provably correct and explicitly computable formula. As applications of our method, we