Enhanced Algorithms for the Representation of integers by Binary Quadratic forms: Reduction to Subset Sum

Abstract

In this paper, we present efficient algorithms for solving the Diophantine equation $f(x,y)=m$ for an arbitrary definite binary quadratic form $f$, given the factorization of $m$. While Cornacchia's algorithm to solve $x^2+d{y}^2=m$ is efficient in many cases, its runtime becomes exponentially large when $m$ is highly composite and encounters subtleties when generalized to arbitrary forms $f$. To address these issues, we give a reduction from our problem to an instance of the Subset sum, a weakly NP complete problem, allowing for more efficient solutions. Leveraging this approach, we develop deterministic algorithms that adapt to different cases based on $\mathrm{disc}(f)$ and $m$. In particular, when $|\mathrm{disc}(f)|=\mathrm{polylog}(m)$, we provide a polynomial time solution that remains efficient regardless of the structure of $m$. For more general cases, we present an algorithm that improves upon Cornacchia's method, achieving a quadratic speedup. Recently, the problem of representing integers by a form $f$ found important applications in elliptic curves and isogeny based cryptography, where these algorithms are central to solving norm form equations.

This is a new version of the paper, that generalized the previous version to arbitrary form. It also enhanced the follow and the structure