|
Georgi Guninski on Fri, 29 Nov 2019 10:45:45 +0100
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: Solving x^2+n*y^2=a without factoring positive $n$?
|
- To: pari-dev@pari.math.u-bordeaux.fr
- Subject: Re: Solving x^2+n*y^2=a without factoring positive $n$?
- From: Georgi Guninski <gguninski@gmail.com>
- Date: Fri, 29 Nov 2019 11:45:30 +0200
- Delivery-date: Fri, 29 Nov 2019 10:45:45 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=ttW/++y86KlK7pMbmhq+hDEaicpzTXc/dM2blmUNGJE=; b=ecosiymOUkxZFU6OG59I2M042mhBKBNfjV/CGysZwNHmnj9uwXDVUBdPpJRbtZwcfq UGd79AZ6oA5H1YOcnA0su1Tyyj3sP7k6UTNQNdegPN69HgXMQfohbDCc+9jUhNRFe64X 9r/Cot/O/VcJkQY2kco19YwQ7BhVI0wXOQfVcOpCALQFG9rmNUiJC+6H0jkJKDz15zLp AI/wHXJenlnJdMI7aWEPzMhpjGdSLajg6767ZmlT4D4YPExOx7NzHKVpQ1rw+fNVgJdU vaumy9UHiwOmeVX0ZHsrsxXBGgbhZJNGgRuJ2ReYEAZ/ZALzkUzwjS1iSw8Lq+Yo/xEN PiZg==
- In-reply-to: <20191128163502.4q43rvadseq7zcy3@yellowpig>
- References: <CAGUWgD-GHjDcR=-uiwAEW4ezZ64O1s5X-x=zGKt0ni=MpAMSGA@mail.gmail.com> <20191128163502.4q43rvadseq7zcy3@yellowpig>
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