|
Georgi Guninski on Fri, 29 Nov 2019 17:29:53 +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 18:29:36 +0200
- Delivery-date: Fri, 29 Nov 2019 17:29:53 +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=/T+uAZhnL9DqfQJygz0enBm4UBB7QaWZ62qHx/aRKAg=; b=aFD8wSSNSdU9Lp8v7VXSHF4TpqLCOd670gts/fs0OGhk2FtRcBuJljmk3V6mn0XuGn uOMKBMT0BwuYgqp+K9elwOFx8LOrw+2U/txKg7f9JHt/eiqy+tAFfA1+UnjQyzsG1vPn o8oo2QeNuZXJVM0BZy7HIxcy/Vzy2ZAwBxrZzqVXjiwFmpD77tnztl+Nyo1F8yung4te DXsVZUjg3wvdI6lTJU5sciVuTK8275xt/T5NaIiptgScc1NHqgUsDGaoixxF1CV536Fk P+bFwvN4fmHGpTB/t8tMZEc3D7kr74ZZIZonuGja+6ntt4M2xJZLFxqtTcFWa2ZmrbhO yctA==
- In-reply-to: <CAGUWgD-66YrU2c7of+9wKLsX4BOPJq_+r8ft7QtbnY76d0RG=w@mail.gmail.com>
- References: <CAGUWgD-GHjDcR=-uiwAEW4ezZ64O1s5X-x=zGKt0ni=MpAMSGA@mail.gmail.com> <20191128163502.4q43rvadseq7zcy3@yellowpig> <CAGUWgD-66YrU2c7of+9wKLsX4BOPJq_+r8ft7QtbnY76d0RG=w@mail.gmail.com>
> 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.