|
Bill Allombert on Fri, 06 Oct 2023 10:39:02 +0200
|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|
Re: efficient foursquare() and/or threesquare1m4() functions
|
- To: pari-users@pari.math.u-bordeaux.fr
- Subject: Re: efficient foursquare() and/or threesquare1m4() functions
- From: Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>
- Date: Fri, 6 Oct 2023 10:38:53 +0200
- Arc-authentication-results: i=1; smail; arc=none
- Arc-message-signature: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1696581530; c=relaxed/relaxed; bh=/xP+1A9WmMNLnJVCtqwbnn1gT2twHw4NcU34XT0PdWY=; h=DKIM-Signature:Date:From:To:Subject:Message-ID:Mail-Followup-To: References:MIME-Version:Content-Type:Content-Disposition: In-Reply-To; b=nMVgGdzXD3bDW79XDf8AjTaln6kzgrOgn+PuEZcOKyPEyusHU3e023NW6kLLDnXaAAoZdIKVxoCc/l6nPm03iNPH8aO5Z65099DP7eOsK9dVemjkRcui+LE96c+/H+dfUks4cd5IofKmILQSJIit75cS81gvgsWInkcI5/PwM3de9oU441UnJxOuhWBa6v7DDZPbFnccN/u34aNCgKSH35l831+BLfXwKTHGYADEmr7/im9eiBW+08MUc7z9yInuWfGWF0Jg1o9Ibg1B++rYRdyGqa3O43lE8X6gPc1A8ml3YnL3iQn1C1RYsBqzNMhxbtkSsCN41gbVTehC9BsvyrioDU/nVfqm0EqGCYOZ/dF1W6al8nVdxPXxBOY3LYB7CBLbCVNqqQG1m5Zh0YnPSCp6QJ1uVVQ92K7mF9Seg3NkwxrYKP3rPvq1a/zft5pPwYAsO3SqfX917345cGgc9F6M7JDFyrC7VA3QmAqn4WMGE+HQTUAy1QMzqZL1AF2/HB2BnCAoA2itomhSKoVblQl+i0PkZcJHhvS/1+DHuzBJJgnzKBO83m9XWqehWz3QVBfOdzv3Es7afILNzD47pR+Hwfyw+H3wql7ZFr4Dmlm49/3DFQg4CC/qvl5+6PC5ep6Iucrj4hBJx4KuMXPwwhKrZKUzrJxK6aB04uWRJSw=
- Arc-seal: i=1; a=rsa-sha256; d=math.u-bordeaux.fr; s=openarc; t=1696581530; cv=none; b=dQS5x6ymUOple8Bc6M+6pSSDTi2vBNRQkvF6NKya8bALNnROK1Kog5yi7Vwv6ZYbN+ofjsLeFJSK0G0GKGcOkcrZJRCNp9pyDSul4mwho4sgK3AlX8ZtROr5cLmwt/UE4ia9a7Nj01+H5th3Xik/oLLgTFl6TYE0WMWCI8j2RLliDQ7d0Yn8+akQfC78JuzDY3qqlWLYXKL8l/oRimxl+EBJcoq6Tbg0lM0qv+fCFK4v5b7fT9mmgkOI0eMIhT39a+bJbt5j9NRFOOOR8Flij250uE43dhb4CL7W6One2KaHLEAaLuITtpmhYLMfsStVQ01hXEHk9MuUwFn5LNK62V3PvT/JBXLWTnGd6OlKodxgxbfBIjF2Ze+uI63n8A++QZrA+Qi6CQbvTleG1av71lW0EHtdeWdGKyRXOuwSOnzrg9qanvWDXLYQvsep608fAMR5vKwuPz3PEP36sucwI7Kda264VmEaQ2s0I0yEHNXcdSZRmvU7PpYtKCyGm17lAvjhzJUltqreh07sTVcPR6DjKwsg/Prx3EAlisvRN5B1F9d9Qdqeykm5SR0hMb3hyIvVhaZusjIdwSv/FVgtfYMTdR4BUE6ZzYsRV9hrq0dymltqhY9xJCjJq2HqZhKtfZCW8mdNp9oL8rP6Wdb2W2FqIpd4l81mJIGIgclGt+Q=
- Authentication-results: smail; arc=none
- Delivery-date: Fri, 06 Oct 2023 10:39:02 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=math.u-bordeaux.fr; s=2022; t=1696581529; bh=/xP+1A9WmMNLnJVCtqwbnn1gT2twHw4NcU34XT0PdWY=; h=Date:From:To:Subject:References:In-Reply-To:From; b=S7Of2HFrlwIfXxeQse+udjILXupela6hpjn4DGe+D4kK6vWGVl5akrFomjBre+LPx 40QPkHUdQcXE0pUuXkeZQotyCrLv4xhru12qe7Doo0MLrK1PwhWRLGNwWSe9SzTHdO C10M5wzSEiHAww9Z8O6va16DKKytGbVvroQpQDU9Ow0k4qMyV0wEc5mVAuW+iqLnkK 12zutYEzp8ippyG5OZ8sVy0Yr98yHh42pKLZC2Ofn6lF6We1VIPUDoZwwzlVEwWpJd 98XdPfzk86Bngs9lmOlkM9VVaA8MXUPRf4YWYQ4ZUK5Q9Khgd+2fPRRNEHDCureUK1 TYPbLbdFOKB24o0GLB7Yqq7miSubwsANnCpxM8R7HVwu68ZAd3IxR/6vV5hv3F1AJL ABNhYKP3CF67Vn1OqqUhoTHoDEHU8/Z6PXoBD4j+gMPo/LnR9HDnN8htJiV57vmueP MAgUVXir4MOZrk4YfYRbEegfQAVLcOMdHZmwgdsNkWAwswSkQoRrp7tC1YyITKAIvS cZheSjUB6Mvpvp8XcQjySyBqm/Deof2PvQb6CPY5iMFEPpSte4RKXU7ScyxF39WKhz gv+ZXQzLGNv2j3Ho7PQtccUngmr9ywmTGEpmhAxjKZbe4orEtl8Oao/WtV8vugxWSX UFOZC5fGqCQ9TOr93nO3YjJ4=
- In-reply-to: <ZR/CnVFCjw69Ukyc@seventeen>
- Mail-followup-to: pari-users@pari.math.u-bordeaux.fr
- References: <d1c78430066dfb66eb8919b4cde59d9c@stamm-wilbrandt.de> <ZR/CnVFCjw69Ukyc@seventeen>
On Fri, Oct 06, 2023 at 10:17:33AM +0200, Bill Allombert wrote:
> You could use
>
> threesquare(n) = abs(qfsolve(matdiagonal([1,1,1,-n]))[1..3]);
>
> but it is not faster.
>
> But you can try this one:
>
> foursquarep(n)=
> {
> for(i=1,sqrtint(n),
> if(ispseudoprime(n-i^2),return(concat(i,threesquare(P-i^2)))))
> }
Sorry, I mixed P and n, it should be
foursquarep(n)=
{
for(i=1,sqrtint(n),
my(P=n-i^2);
if(P%8!=7 && ispseudoprime(P),return(concat(i,threesquare(P)))))
}
> foursquaref(n)=
> {
> for(i=1,sqrtint(n),
> my(P=n-i^2, v = valuation(P,2)\2);
> if (P/4^v%8!=7,
> my(F=factor(P,2^20)[,1]);
> if(ispseudoprime(F[#F]),
> return(concat(i,threesquare(P))))));
> }
This one is OK.
Cheers,
Bill.