Enhanced Algorithms for the Representation of integers by Binary Quadratic forms: Reduction to Subset Sum
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917942228156416 |
|---|---|
| author | Mamah, Maher |
| author_facet | Mamah, Maher |
| contents | 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 + dy^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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11402 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Enhanced Algorithms for the Representation of integers by Binary Quadratic forms: Reduction to Subset Sum Mamah, Maher Number Theory Combinatorics 11Y16 (primary), 11Y40 (secondary) 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 + dy^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. |
| title | Enhanced Algorithms for the Representation of integers by Binary Quadratic forms: Reduction to Subset Sum |
| topic | Number Theory Combinatorics 11Y16 (primary), 11Y40 (secondary) |
| url | https://arxiv.org/abs/2502.11402 |