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

On Fri, Nov 29, 2019 at 06:19:46PM +0100, Bill Allombert wrote:
> On Fri, Nov 29, 2019 at 06:29:36PM +0200, Georgi Guninski wrote:
> > > Sorry, I mean quadratic in log(n).
> > 
> > Are you sure you can bound the complexity only with n
> > without a?
> 
> I said, if the factorisation of a is given. If a has k primes factors
> the cost will be about O~(2^k*log(max(P,n))^2) when P is the largest of
> the prime factors.
> Note that there might be up to O(2^k) solutions.

This is an example (with four solutions):

setrand(1)
P=randomprime(2^128);Q=randomprime(2^128);N=P*Q
vN=sqrtint(N);until(ispseudoprime(p),p=random(vN)^2+random(vN)^2*N);p
vN=sqrtint(N);until(ispseudoprime(q),q=random(vN)^2+random(vN)^2*N);q
qfbsolve(Qfb(1,0,N),[p,1;q,1])
##
  ***   last result computed in 0 ms.

Cheers,
Bill.