O34 — Solvability of the negative Pell equation

Definitions and mathematical statement

For a positive integer $d$, the negative Pell equation is \[ x^2-dy^2=-1,\qquad x,y\in\mathbb Z. \] The input is the binary expansion of $d$, and the required output is a decision bit indicating whether at least one integral pair $(x,y)$ satisfies this equation. Signs of the coordinates are immaterial for existence, and zero coordinates are allowed when they satisfy the equation.

Is there a deterministic classical algorithm deciding solvability for every $d$ in time polynomial in $\ell(d)=\lfloor\log_2d\rfloor+1$? The parameter $d$ is not assumed squarefree, and no factorization is supplied. The simple square cases can be separated: $d=1$ admits $(0,1)$, while a positive square greater than one admits no integral solution. The substantive remaining domain is positive nonsquare $d$.

Only existence is to be decided. In particular, the algorithm need not output a smallest positive solution, whose coordinate lengths can be much larger than the input length. This distinction prevents the size of such a witness from being mistaken for an immediate obstruction to efficient decision.

Continued fractions of $\sqrt d$ give a finite decision procedure, but a polynomial bound in $d$ itself or in the period length is not the requested polynomial bound in binary length. All computations and any auxiliary factorizations must be charged to one uniform, unconditional deterministic time bound.

Short English statement

Can solvability of the negative Pell equation be decided deterministically in polynomial time without writing a potentially enormous solution?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400039 (AMR-083-0039), 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), O34, p22 / LNCS p312. Original source indexed by AMR-083-0039. https://mccurley.org/papers/open.ps.gz.