Re: Solving x^2+n*y^2=a without factoring positive $n$?

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Thu, Nov 28, 2019 at 05:51:54PM +0200, Georgi Guninski wrote:
> thue() appears to solve x^2+n*y^2=a without factoring
> positive $n$ when we declare n as prime via addprimes():
> 
> ? p=nextprime(2*10^8);q=nextprime(3*p);n=p*q;a=(p-1)^2+n*200^2;addprimes([n]);K=
> thue(thueinit(x^2+n,0),a)
> 
> Given n and factored a, what is the complexity of solving the
> equation? (the solution is bounded by sqrt(a))
 
With PARI 2.12, you should use qfbsolve(Qfb(1,0,n),a) which will run in
quadratic time in n (assuming n>0), given the factorisation of a.
There is no need to factor n.

However it returns only the solution (x,y) with x,y coprime.
In this case a is divisible by 8^2, you can do
? qfbsolve(Qfb(1,0,n),a/64)*8
%12 = [[200000032,200],[-200000032,200]]

Cheers,
Bill