On the solution of \(x^2+dy^2=m\) (Q1764322)

This work is an interesting contribution to the algorithmic analysis of Diophantine equations. In fact, in 1908, G. Cornacchia gave a fast algorithm for solving the Diophatine equation \(x^2+dy^2=4p\), for \(p\) prime using continued fractions. More generally, the same algorithm can be used to solve the Diophantine equation \(x^2+dy^2=m\), where \(1\leq d \leq m\). The importance of this algorithm is undeniable as it is widely used and implemented (see \texttt{MATHEMATICA, PARI, MAGMA}, \dots). So many proofs of the validity of this algorithm are given. A modified version of this algorithm can be found in \textit{H. Cohen's} book [A course in computational algebraic number theory. Graduate Texts in Mathematics. 138. Berlin: Springer-Verlag (1993; Zbl 0786.11071)]. In 1990, \textit{F. Morain} and \textit{J.-L. Nicolas} gave a proof of the validity of the Cornacchia's algorithm using continued fractions and Diophantine approximation [On Cornacchia's algorithm for solving the Diophantine equation \(u^2+dv^2=m\). Courbes elliptiques et tests de primalité. Thèse, Université de Lyon, 20 Septembre (1990)]. In 1995, \textit{R. Schoof} reported a proof, due to H. W. Lenstra, of the validity of the algorithm [Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordx. 7, No.1, 219--254 (1995; Zbl 0852.11073)]. The algorithm is used to count the number of points on an elliptic curve \(E\), where the endomorphism ring of \(E\) is known. In the present article, a different strategy is applied and a simpler proof is given. The proof is based on lattice theory. In fact, the author proves that if \(L_t:=\langle (m, 0), \, (t, 1) \rangle_{\mathbb Z}\), where \(t\) is an integer such that \(0\leq t \leq m\) and \(t^2\equiv -d\) (mod \(m\)), then a primitive solution \((x_0,\, y_0)\) to \(x^2+dy^2=m\) belongs to \(L_t\). Moreover, he solves completely the case \(d=1\), i.e. the equation \(x^2+y^2=m\).