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

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

On Fri, Nov 29, 2019 at 11:45:30AM +0200, Georgi Guninski wrote:
> 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).

Sorry, I mean quadratic in log(n).

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

This is just too hard to be done by thue.

Cheers,
Bill.