The Linear Code Equivalence ( \(\textsf{LCE}\) ) problem asks, for two given linear codes \(\mathcal {C}, \mathcal {C}'\) , to find a monomial \(\textbf{Q}\) mapping \(\mathcal {C}\) into \(\mathcal {C}'\) . Algorithms solving \(\textsf{LCE}\) crucially rely on a (heuristic) subroutine, which recovers the secret monomial from \(\varOmega (\log n)\) pairs of codewords \((\textbf{v}_i, \textbf{w}_i)\in \mathcal {C} \times \mathcal {C}'\) satisfying \(\textbf{w}_i = \textbf{v}_i\textbf{Q}\) . We greatly improve on this known bound by giving a constructive algorithm that provably recovers the secret monomial from any two pairs of such codewords for fields of sufficiently large prime order q. Furthermore, we demonstrate that in practice this algorithm remains effective even for small prime fields. We then show that this reduction in the number of required pairs enables the design of a more efficient algorithm for solving the \(\textsf{LCE}\) problem. Our asymptotic analysis shows that this algorithm outperforms previous approaches for a wide range of parameters. Our concrete analysis reveals significant improvements as well. Most notably, in the context of the LESS signature scheme, a second-round contender in the ongoing NIST standardization effort, we achieve bit security reductions of up to 24 bits.