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

> Sorry, I mean quadratic in log(n).

(I am having some problems with gmail's filters).

Are you sure you can bound the complexity only with n
without a?

Fix n and set X=2^2^2^n, Y=X+1, a=X^2+n Y^2

I think you can't express X with only log(n)^2 operations.