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

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.

Cheers,
Bill