|
Bill Allombert on Fri, 29 Nov 2019 18:19:48 +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: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Fri, 29 Nov 2019 18:19:46 +0100
- Delivery-date: Fri, 29 Nov 2019 18:19:48 +0100
- In-reply-to: <CAGUWgD93n=5m8TWEFpL9GMEgg4PYC3q5qybfHwBhUrLAk5vvOg@mail.gmail.com>
- Mail-followup-to: pari-dev@pari.math.u-bordeaux.fr
- References: <CAGUWgD-GHjDcR=-uiwAEW4ezZ64O1s5X-x=zGKt0ni=MpAMSGA@mail.gmail.com> <20191128163502.4q43rvadseq7zcy3@yellowpig> <CAGUWgD-66YrU2c7of+9wKLsX4BOPJq_+r8ft7QtbnY76d0RG=w@mail.gmail.com> <CAGUWgD93n=5m8TWEFpL9GMEgg4PYC3q5qybfHwBhUrLAk5vvOg@mail.gmail.com>
- User-agent: NeoMutt/20170113 (1.7.2)
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