Theorem 1 (Brillhart 2009). Let $N \gt 1$ be an odd integer expressed in two different ways as $$N=ma^2+nb^2=mc^2+nd^2,$$ where $a,b,c,d,m,n \in \mathbb{Z}^{+},b \lt d$, and $(ma,nb)=(mc,nd)=1$. Then $$N=(N,ad-bc) \cdot \frac{N}{(N,ad-bc) },$$ where the factors are non-trivial.
Proof. See (Brillhart 2009). ∎
In trying to factor a $N$ using this method, we want to find two lattice points on the ellipse $N = m x^2 + n y^2$ and then use the theorem to factor $N$.
I use the following approach:
We can choose $a,b \in \mathbb{Z}$ such that $(a,b) = 1$ and then find $m, n \in \mathbb{Z}$ by solving $m a^2 + n b^2 = N$ using the Euclidean algorithm.
This gives the first lattice point $P_1(a,b) \in \mathbb{Z} \times \mathbb{Z}$ on the ellipse.
We can try to find other rational points on this ellipse by taking any rational direction $(f,g)$ with $f,g$ relatively prime (using the definition of GCD extended to rational numbers). We look for solutions $(x,y)=(a,b)+t(f,g)$ and substitute them in the equation of the ellipse:
$$ \begin{align} N &= m(a+ft)^2+n(b+gt)^2 \newline &= m(a^2+2aft+f^2 t^2 )+n(b^2+2bgt+g^2 t^2 ) \newline &=\overbrace{ma^2+nb^2}^{N}+2maft+mf^2 t^2+2nbgt+ng^2 t^2 \end{align} $$
i.e.,
$$ 2maf+2nbg=-(mf^2+ng^2 )t $$
and solve for $t$ giving
$$ t=-2\frac{maf+nbg}{mf^2+ng^2} $$
Question: How do we choose $f, g \in \mathbb{Q}$ such that we obtain a non-trivial lattice point $P_2(a + ft, b + gt) \in \mathbb{Z} \times \mathbb{Z}$ on the ellipse?
Note the constraint that $f,g, t$ are rational but $ft,gt \in \mathbb{Z}$ if $P_2 \in \mathbb{Z} \times \mathbb{Z}$.
Most choices of $f,g$ yield trivial lattice points (i.e., $(\pm a,\pm b)$).
Some choices of $(f,g)$ that I tried: $(a,b), (\frac{1}{b}, \frac{1}{a})$ and also $p,q,r,s \in \mathbb{Z}$ such that $a = \pm ps, b = \pm qr, (f,g) = (\frac{p}{q},\frac{r}{s})$.
References:
[Brillhart 2009]: Brillhart, John. “A Note on Euler’s Factoring Problem.” The American Mathematical Monthly, vol. 116, no. 10, 2009, pp. 928–31. JSTOR, http://www.jstor.org/stable/40391253. Accessed 19 July 2023.
Related:
This MSE Question: A generalization of Euler Factorization with $N = m a^2 + n b^2 = m c^2 + n d^2$.