|
Bill Allombert on Sat, 18 Nov 2023 10:18:30 +0100
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: question on finding exhaustive search algorithm for a^2+b^2 = N
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: question on finding exhaustive search algorithm for a^2+b^2 = N
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Sat, 18 Nov 2023 10:18:15 +0100
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1700299097; c=relaxed/relaxed; bh=2RYnTNydD30yVM2srqA0ByEoTqz5DNn2RUaT8DGSw0Q=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=IKdRfd5yjKpiWog7WmEH/SpoZeqDOPFIedrZsmvVHnH44nIb6NCGYcxCLk/PcCC1kUpndslp7yXNNatPGaKS5C5I1bv4utymiwvdFIukfPpf3ih/GHWMY2f+pQuXSHQ2sUF8gFIeg03+nmAEGItAul2iw+wFLh5is/bq/0RMvZowhj839xI9l4s3JOih+BGEh5mPiwgHCypE9WAgtZNdhQ+GuADjhPnwytOQ2TUbuSuz6wcR+P6yAIo91wiPZ2GpHP6eDxEe2kLMxxWlNKqByuO+mP7I2azinxgZ+kg+iKpTQ11eqMIi6Apw7gcFBcp6RNJ+VBJeEGhU8lfQPz9ogNeDSF9+sjS7Eaj6oHN+5938/qWRFm0TwtFnPNiEX4e5Rl9f4Fb62txxetkE1j+SRHvm7o6K5Kkt/QV4Wi6xO0bf44iYG8ttWwAN+iDg0vS4xESoS1wTNeJKsygNnz7cmchAC6mXFzzNXP0yW4Avmarofc/l2E1iWhjLXCZfU0sCkAxuXqBVSN4rWMMoR6CBkYMIvZaBBpI+zg2Xbvbf4+ONHFxmC35BrTv/zRNnBRiFBHyhjo4+lJmqHZzsASu9Rw7emmwIxKZorRUKMoR743mEyYDDCnxgpLByj3cYtr8KGIyRMiCW75b4+RMOBU34C8A0r3LUSL8bZV7H4VJ+7LA=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1700299097; cv=none; b=gagK5ZhSdopLtbYZ8NZ60uALxn2CnBd0eX/XC6ConCBGPqiUrcihS9TNRkHgzDm2Ep9/Z7H8b9teOsiM0Tlv7relBzXkOXQBo995rUXFgnqhCGBqHnljQe3fzSerxkBbecl5s8+iioj0frXQ3JnXbdKcYMbbFqT9uOUpY0yXBkbVgpj1dj/utBD70IOlUW/zH0gCACDe4l8yHO/MxvHK29GmCv73j8MOWzQakrqdQz9FvyGRZXZiVdJBDSHAv4QdAaAH7CCzGKrF9A2eK68Fs1GnLI1occpiXEJ9BMDHfn3kqplAU35rO+FQ0UD7IPwVFiB/3x6vZtx30f75QjDgMpya+DBC0ufSZwPALpnZTw9U5y7GP2mCBmCMhcBmpb6Gi6tJWUQgO6cp4KI+3AotFM4GTWB5UH9QHeHFc0uciEvHIT8z3S/VjoVDtZ8E4ndwnSJSsIIP7hknkkMK8pyy1hsAXz1LJDZCpiJllCQPexktW7jbJUTFO6JZl9v4mikiVdX3R7aK3YnoESZwSwy3F5eoGMIiI0Kba8x4cTdCnrTRvHzOZHe6i4KHedYaBVuXHSJp3r6QriUywbybqObd3teN6coU138VbNHRmZ5bqKbPBDgal/Ixg3lrPw11Moz3ABZHujtonRNpbTLjCTKJWcVyAlRb2u5SAcFemCdqV6E=
- Authentication-results: smail; arc=none
- Delivery-date: Sat, 18 Nov 2023 10:18:31 +0100
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1700299097; bh=2RYnTNydD30yVM2srqA0ByEoTqz5DNn2RUaT8DGSw0Q=; h=Date:From:To:Subject:References:In-Reply-To:From; b=kRcHfenR6SWNnG3Tq1aoJslpknRfc2CzO0CMddSF512/4gBjsGMvpXjQJAEZwT0bT hHgcEulAiabd9W0zY6xyxye6II38npzeIh1oSebtliqy2ALYQuYE642AIgZi7TFchH LiNV86+2YMMc51gvlK525xsBPfmoSROEQQBjjeHwqrD2JaZ/LcfCtcgeb7LAT2wkno vunaVpUSA/gkefJ7ZZHkrLyIDqTW/1pzulRe/7c8AIO5xgQup/FzIAl08Rt1I0iGJm JciB7/+ZmEn/eoscb48pz++cts4nfaUE8ul9+Q59XIWOKSQIkdohRmLuIdSKvUmgcr K1FbO3WNBg7ZxiT3J8vA2+TcAvaQfQ3NUFnCeGZ7ziGeegDDoOq7yXX25ec6KQ2I9L DVgJCtxTrj0zloOY6sXg1PuL28HHa6m8OSjBmpcpR/rUyvncOtP+P4Ba6l5WEifUty Lhz386ei75CjZRGWdMa5+7AX7oO0alQDzph/fgpR92e1kudnM24PhCSTG3H2KZkYGM H7VnX2z3gC94TwpQF2lClyzNzah1z6uP5sEgizufIKTEHbh3PP12AeWMMoQPloXiKj D02bl2tmJUozdBw2cUbcdZuxDApLUDPt+yt8k2e3AlEtC8flCjhNK0lQxm5oHGswq7 fszERAJ14lwyQII8c1ZDyWf0=
- In-reply-to: <11FC24D5-8FBD-424E-9F46-DCAA0C68C1E7@earthlink.net>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <c7cf4c64-6785-4a19-82f3-cd68c0ee4d52@gmail.com> <11FC24D5-8FBD-424E-9F46-DCAA0C68C1E7@earthlink.net>
On Fri, Nov 17, 2023 at 09:19:22PM -0600, Kurt Foster wrote:
> On Nov 17, 2023, at 7:11 PM, American Citizen wrote:
>
> > My goal is an exhaustive search of 2 squares = N algorithm
>
> I dashed off some code which may be overkill (it absolutely clobbers the
> problem) but seems to get the job done. I used your example as a test.
>
> ? K=bnfinit(x^2+1);
> ? N=5*13*17*29*37;
> ? v=bnfisintnorm(K,N);
> ? w=vecsort(vector(#v,i,abs([polcoeff(v[i],0),polcoeff(v[i],1)])),1)
> %4 = [[64, 1087], [103, 1084], [167, 1076], [191, 1072], [236, 1063], [281,
> 1052], [292, 1049], [359, 1028], [449, 992], [512, 961], [568, 929], [601,
> 908], [607, 904], [664, 863], [673, 856], [743, 796], [796, 743], [856,
> 673], [863, 664], [904, 607], [908, 601], [929, 568], [961, 512], [992,
> 449], [1028, 359], [1049, 292], [1052, 281], [1063, 236], [1072, 191],
> [1076, 167], [1084, 103], [1087, 64]]
Interesting! It seems to work, but according to the documentation
"Computes a complete system of solutions (modulo units of positive norm)"
you should have had the same issue as with qfbsolve.
bnfisintnorm returns both 103*x-1084 and 1084*x-103 (with x=I)
but since I is a unit of positive norm, you could get in theory
103*x-1084 and x*(1084*x-103) = -103+1084*x
which would be identical after taking the absolute values.
Cheers,
Bill.