Could efficient solutions of $x^2+n y^2=A$ be related to integer factorization?

Question

Let $n$ be positive integer with unknown factorization and $A$ integer with known factorization.

According to pari/gp developers pari can efficiently find all solutions of:

$$x^2+n y^2=A \qquad (1)$$

To achieve this, we need the factorization of $A$. $A$ is prime with probability $\log{A}$ and also with high probability we can find $A$ which is product of small primes and one additional large prime.

We can choose $(x,y)=(x_0,y_0)$ which guarantees one solution and experimentally sometimes there are more than one solution up to sign, but our experimental data is not enough.

There is the obvious congruence $x_0^2 \equiv A \pmod{n}$ and if we have second solution $(x_1,y_1)$ with $x_0 \ne \pm x_1 \pmod{n}$ we can find proper factor of $n$.

The pari code is sol=qfbsolve(Qfb(1,0,n),A,3)

Q1 Can efficient solutions of this form lead to subexponential integer factorization algorithm?

Answer 1

Short answer: no, what you propose does not work. A related method does work, and is already well-known.

Full answer:

Since the goal is factorisation, let us assume $n$ has no small prime factors and $A,n$ are coprime.

The standard algorithm to solve $x^2+ny^2=A$ goes as follows:

1. factor $A$
2. find all square roots of $-n$ modulo $A$ (using the factorisation)
3. for each such square root $s$, look for solutions $(x,y)$ such that $x-sy\equiv 0 \bmod A$ by computing a short vector in the corresponding lattice.

All those steps can be performed efficiently, except possibly for the factorisation of $A$. So if you feed the algorithm with integers $A$ that are easy to factor, then it will be efficient.

The reason why the method does not work is because there will almost never be a solution. Indeed, square roots $s$ in the algorithm above correspond exactly to ideals of norm $A$ in the ring $R=\mathbb{Z}[\sqrt{-n}]$, and the last step is a test for principality of such an ideal. However, the size of the class group of $R$ is about $\sqrt{n}$, so the probability that you will find a solution is about $\frac{1}{\sqrt{n}}$, exponentially small, a fact that you probably observed if you tested your method.

The variant that does work comes from the last interpretation in terms of ideals and the class group of $R$. A nice class of $A$ that are easy to factor are smooth numbers: choose a smoothness bound $Y$, and take $A$ all of whose prime factors are less than $Y$. As explained above, fixing $A$ and looking for solutions does not work. However, what does work is to draw many random pairs $(x,y)$ until $x^2+ny^2$ is smooth. This way, one produces relations among the prime ideals of $R$ of norm at most $Y$, and assuming those ideals generate the class group, one can eventually compute the class group of $R$. This is essentially the algorithm of Hafner and McCurley, which indeed runs in subexponential time $\exp(O(\sqrt{\log n \log\log n}))$. Once this is done, one can factor $n$ as follows: $2$-torsion elements in the class group will give you squarefree numbers $A$ such that your equation has no solution for $A$, but has one for $A^2$, yielding $(x,y)$ such that $x^2+ny^2 = A^2$, and therefore $(x-A)(x+A) \equiv 0 \bmod n$. Gauss's genus theory tells you that there will be enough $2$-torsion elements to factor $n$ this way. The resulting method is closely related to the quadratic sieve factoring algorithm.

Edit to substantiate my claim that this is well-known: this is Seysen's algorithm in the paper A probabilistic factorization algorithm with quadratic forms of negative discriminant. Math. Comput. 48, 757-780 (1987) (DOI link).