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

[Georgi Guninski <gguninski@gmail.com>]

On Thu, Nov 28, 2019 at 6:35 PM Bill Allombert
<Bill.Allombert@math.u-bordeaux.fr> wrote:
>

>
> 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.
>

Do you really mean quadratic in n? If n is over 2^100 this
will be infeasible and bruteforce is time sqrt(a).

FYI in 2.11.1 on debian 10 (and pari online):

? p=nextprime(2^150);q=nextprime(3*p);n=p*q;a=(p-1)^2+n*sqrtint(q-200)^2;K=
thue(thueinit(x^2+n,1),a)
  ***   at top-level: ...)^2+n*sqrtint(q-200)^2;K=thue(thueinit(x^2+n,1
  ***                                             ^---------------------
  *** thue: overflow in thue (SmallSols): y <= 65435029442324541857792.
  ***   Break loop: type 'break' to go back to GP prompt