O25 — Solving binary quadratic congruences

Definitions and mathematical statement

Let $n\ge3$ be odd and let $k,m$ be integers satisfying $\gcd(km,n)=1$. Reduce $k$ and $m$ modulo $n$, so both represent units in $\mathbb Z/n\mathbb Z$. The input is the binary encoding of this data. We seek a pair of residues $x,y$, represented between $0$ and $n-1$, for which \[ x^2-ky^2\equiv m\pmod n. \] No condition of being nonzero or coprime to $n$ is imposed separately on $x$ or $y$.

Can a deterministic classical algorithm produce such a pair for every input in the stated domain in time polynomial in the total binary length? The oddness and unit hypotheses give the norm-form setting of the source problem. Solutions exist: over each odd prime dividing $n$, the split or nonsplit quadratic norm represents every nonzero residue, and nonsingular solutions lift to prime powers and combine by the Chinese remainder theorem.

This existence description is not supplied to the algorithm as factored input. In particular, a factorization of $n$ is not available at no cost. The algorithm is free to output any solution and need not enumerate them all or minimize their integer representatives.

The required bound must be unconditional, deterministic, and uniform in all three parameters. A randomized method, or a procedure whose running time is polynomial in the numerical modulus rather than its bit length, does not give the requested result.

Short English statement

Can every admissible binary quadratic norm congruence be solved deterministically in polynomial bit complexity?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400029 (AMR-083-0029), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O25, p18 / LNCS p308. Original source indexed by AMR-083-0029. https://mccurley.org/papers/open.ps.gz.